On the expressive power of temporal logic

DOI10.1016/0022-0000(93)90005-HzbMath0784.03014OpenAlexW2052706627MaRDI QIDQ2366686

Joëlle Cohen, Dominique Perrin, Jean-Eric Pin

Publication date: 18 August 1993

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(93)90005-h

zbMATH Keywords

linear logicformal languagesyntactic semigroupdeterministic automatonrational languagepropositional linear temporal logicrestriction of temporal logic

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Modal logic (including the logic of norms) (03B45) Automata and formal grammars in connection with logical questions (03D05) Specification and verification (program logics, model checking, etc.) (68Q60)

Related Items (26)

Deciding \(\mathrm{FO}^2\) alternation for automata over finite and infinite words ⋮ Vectorial languages and linear temporal logic ⋮ Efficient algorithms for membership in Boolean hierarchies of regular languages ⋮ Pure future local temporal logics are expressively complete for Mazurkiewicz traces ⋮ EF+EX Forest Algebras ⋮ Unnamed Item ⋮ Unnamed Item ⋮ The state complexity of \(\overline{\varSigma ^*\overline{L}}\) and its connection with temporal logic ⋮ Forbidden Patterns for FO² Alternation Over Finite and Infinite Words ⋮ On the translation of automata to linear temporal logic ⋮ A SURVEY ON SMALL FRAGMENTS OF FIRST-ORDER LOGIC OVER FINITE WORDS ⋮ Descriptional Complexity of the Forever Operator ⋮ MONOIDS AND COMPUTATIONS ⋮ Algebraic recognizability of regular tree languages ⋮ Characterizing CTL-like logics on finite trees. ⋮ On Shuffle Ideals ⋮ Expressive power of existential first-order sentences of Büchi's sequential calculus ⋮ Unnamed Item ⋮ Matching Trace Patterns with Regular Policies ⋮ AN NP-COMPLETE FRAGMENT OF LTL ⋮ Logic, semigroups and automata on words ⋮ A new proof of the locality of R ⋮ An until hierarchy and other applications of an Ehrenfeucht-Fraïssé game for temporal logic ⋮ Cascade Products and Temporal Logics on Finite Trees ⋮ On the expressive power of temporal logic for infinite words ⋮ Logic over words on denumerable ordinals

Cites Work

• Finite-automaton aperiodicity is PSPACE-complete
• First-order logic and star-free sets
• Finite semigroup varieties of the form V*D
• Dot-depth of star-free events
• Complexity of some problems from the theory of automata
• “Sometimes” and “not never” revisited
• On finite monoids having only trivial subgroups
• A Note on Star-Free Events
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On the expressive power of temporal logic