License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2010.481
URN: urn:nbn:de:0030-drops-28883
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2010/2888/
Go to the corresponding LIPIcs Volume Portal

Kara, Ahmet ; Schwentick, Thomas ; Zeume, Thomas

Temporal Logics on Words with Multiple Data Values

pdf-format:
42.pdf (0.5 MB)

Abstract

The paper proposes and studies temporal logics for attributed words, that is, data words with a (finite) set of (attribute,value)-pairs at each position. It considers a basic logic which is a semantical fragment of the logic $\LTL^\downarrow_1$ of Demri and Lazic with operators for navigation into the future and the past. By reduction to the emptiness problem for data automata it is shown that this basic logic is decidable. Whereas the basic logic only allows navigation to positions where a fixed data value occurs, extensions are studied that also allow navigation to positions with different data values. Besides some undecidable results it is shown that the extension by a certain UNTIL-operator with an inequality target condition remains decidable.

BibTeX - Entry

@InProceedings{kara_et_al:LIPIcs:2010:2888,
  author =	{Ahmet Kara and Thomas Schwentick and Thomas Zeume},
  title =	{{Temporal Logics on Words with Multiple Data Values}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)},
  pages =	{481--492},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-23-1},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{8},
  editor =	{Kamal Lodaya and Meena Mahajan},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2010/2888},
  URN =		{urn:nbn:de:0030-drops-28883},
  doi =		{10.4230/LIPIcs.FSTTCS.2010.481},
  annote =	{Keywords: Expressiveness, Decidability, Temporal Logic, Data words}
}

Keywords: Expressiveness, Decidability, Temporal Logic, Data words
Collection: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)
Issue Date: 2010
Date of publication: 14.12.2010

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI