Computer Science – Logic in Computer Science
Scientific paper
2006-10-05
Computer Science
Logic in Computer Science
29 pages
Scientific paper
A data word is a sequence of pairs of a letter from a finite alphabet and an element from an infinite set, where the latter can only be compared for equality. To reason about data words, linear temporal logic is extended by the freeze quantifier, which stores the element at the current word position into a register, for equality comparisons deeper in the formula. By translations from the logic to alternating automata with registers and then to faulty counter automata whose counters may erroneously increase at any time, and from faulty and error-free counter automata to the logic, we obtain a complete complexity table for logical fragments defined by varying the set of temporal operators and the number of registers. In particular, the logic with future-time operators and 1 register is decidable but not primitive recursive over finite data words. Adding past-time operators or 1 more register, or switching to infinite data words, cause undecidability.
Demri Stéphane
Lazic Ranko
No associations
LandOfFree
LTL with the Freeze Quantifier and Register Automata does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with LTL with the Freeze Quantifier and Register Automata, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and LTL with the Freeze Quantifier and Register Automata will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-656260