Deciding FO^2 alternation for automata over finite and infinite words
From MaRDI portal
Publication:832937
DOI10.1007/978-3-030-81508-0_15OpenAlexW3196841993MaRDI QIDQ832937FDOQ832937
Authors: Viktor Henriksson, Manfred Kufleitner 
Publication date: 25 March 2022
Full work available at URL: https://doi.org/10.1007/978-3-030-81508-0_15
Recommendations
- The \(\mathrm{FO}^2\) alternation hierarchy is decidable
- The half-levels of the \(\mathrm {FO}_2\) alternation hierarchy
- On FO 2 Quantifier Alternation over Words
- Quantifier alternation in two-variable first-order logic with successor is decidable
- Structure Theorem and Strict Alternation Hierarchy for FO2 on Words
Cites Work
- Complexity of some problems from the theory of automata
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Characterizations of some classes of regular events
- On the expressive power of temporal logic
- Languages of dot-depth 3/2
- Finite-automaton aperiodicity is PSPACE-complete
- Unambiguous Büchi automata.
- A SURVEY ON SMALL FRAGMENTS OF FIRST-ORDER LOGIC OVER FINITE WORDS
- Sur le produit de concatenation non ambigu
- First-order fragments with successor over infinite words
- Fragments of first-order logic over infinite words
- Structure Theorem and Strict Alternation Hierarchy for FO^2 on Words
- Level two of the quantifier alternation hierarchy over infinite words
- Varieties
- The half-levels of the \(\mathrm {FO}_2\) alternation hierarchy
- An Effective Characterization of the Alternation Hierarchy in Two-Variable Logic
- The \(\mathrm{FO}^2\) alternation hierarchy is decidable
- Title not available (Why is that?)
- Effective characterizations of simple fragments of temporal logic using Carton-Michel automata
Cited In (2)
This page was built for publication: Deciding \(\mathrm{FO}^2\) alternation for automata over finite and infinite words
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q832937)
