Temporal logics on words with multiple data values

DOI10.4230/LIPICS.FSTTCS.2010.481MaRDI QIDQ2908879zbMATH OpenOpenAlexFDO

Authors Ahmet Kara, Thomas Schwentick, Thomas Zeume

Publication date 29 August 2012

Full work available at URL https://arxiv.org/abs/1010.1139, http://subs.emis.de/LIPIcs/frontdoor_9cd7.html

zbMATH Keywords

data wordsdecidabilityexpressivenesstemporal logic

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Temporal logic (03B44)

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 $LT{L}^{d}ownarro{w}_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.

Recommendations

• Expressiveness of hybrid temporal logic on data words
• Temporal logics with language parameters
• Extending temporal logics with data variable quantifications
• On the expressive power of temporal logic
• Temporal logics on strings with prefix relation
• Temporalizing description logics
• On temporal logics with data variable quantifications: decidability and complexity
• On the expressive power of temporal logic for infinite words
• Temporalized logics and automata for time granularity
• Multiple-valued semantics for metric temporal logic

Cited in

(13)

• Temporal multi-valued logic with lost worlds in the past
• Weak and nested class memory automata
• On freeze LTL with ordered attributes
• Reasoning about data repetitions with counter systems
• Expressiveness of hybrid temporal logic on data words
• Logics of repeating values on data trees and branching counter systems
• An automaton over data words that captures EMSO logic
• Ordered navigation on multi-attributed data words
• On temporal logics with data variable quantifications: decidability and complexity
• Walking on data words
• Reasoning about data repetitions with counter systems
• On the existential fragments of local first-order logics with data
• On the satisfiability of local first-order logics with data

This page was built for publication: Temporal logics on words with multiple data values

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2908879)