Fragments of first-order logic over infinite words

DOI10.1007/s00224-010-9266-7zbMath1258.03045OpenAlexW2122269913MaRDI QIDQ537914

Manfred Kufleitner, Volker Diekert

Publication date: 23 May 2011

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2009/1818/

zbMATH Keywords

automata theorysemigroupsfirst-order logictopologyregular languagesinfinite words

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05) Subsystems of classical logic (including intuitionistic logic) (03B20)

Related Items (9)

Deciding \(\mathrm{FO}^2\) alternation for automata over finite and infinite words ⋮ Level two of the quantifier alternation hierarchy over infinite words ⋮ PARTIALLY ORDERED TWO-WAY BÜCHI AUTOMATA ⋮ Forbidden Patterns for FO² Alternation Over Finite and Infinite Words ⋮ Topology, monitorable properties and runtime verification ⋮ Well-Quasi Orders and Hierarchy Theory ⋮ Level Two of the Quantifier Alternation Hierarchy over Infinite Words ⋮ Quantifier Alternation for Infinite Words ⋮ Shift-invariant topologies for the Cantor space \(X^{\omega}\)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On generalized locally testable languages
• The complementation problem for Büchi automata with applications to temporal logic
• Locally trivial categories and unambiguous concatenation
• Upper and lower bounds for first order expressibility
• Classifying regular events in symbolic logic
• Some results on the dot-depth hierarchy
• Sur le produit de concatenation non ambigu
• First-order logic with two variables and unary temporal logic
• Piecewise testable tree languages
• A SURVEY ON SMALL FRAGMENTS OF FIRST-ORDER LOGIC OVER FINITE WORDS
• Polynomials, Fragments of Temporal Logic and the Variety DA over Traces
• Logic Meets Algebra: the Case of Regular Languages
• Mathematical Foundations of Computer Science 2004
• Fragments of First-Order Logic over Infinite Words.
• The Common Fragment of ACTL and LTL
• Tree Languages Defined in First-Order Logic with One Quantifier Alternation

This page was built for publication: Fragments of first-order logic over infinite words