Deciding \(\mathrm{FO}^2\) alternation for automata over finite and infinite words

DOI10.1007/978-3-030-81508-0_15OpenAlexW3196841993MaRDI QIDQ832937

Manfred Kufleitner, Viktor Henriksson

Publication date: 25 March 2022

Full work available at URL: https://doi.org/10.1007/978-3-030-81508-0_15

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (1)

Forbidden Patterns for FO² Alternation Over Finite and Infinite Words

Cites Work

• Fragments of first-order logic over infinite words
• Finite-automaton aperiodicity is PSPACE-complete
• Characterizations of some classes of regular events
• Sur le produit de concatenation non ambigu
• Unambiguous Büchi automata.
• Level two of the quantifier alternation hierarchy over infinite words
• Varieties
• On the expressive power of temporal logic
• The half-levels of the \(\mathrm {FO}_2\) alternation hierarchy
• Languages of dot-depth 3/2
• Structure Theorem and Strict Alternation Hierarchy for FO^2 on Words
• A SURVEY ON SMALL FRAGMENTS OF FIRST-ORDER LOGIC OVER FINITE WORDS
• Complexity of some problems from the theory of automata
• An Effective Characterization of the Alternation Hierarchy in Two-Variable Logic
• Effective Characterizations of Simple Fragments of Temporal Logic Using Carton--Michel Automata
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Deciding \(\mathrm{FO}^2\) alternation for automata over finite and infinite words