Deciding FO^2 alternation for automata over finite and infinite words
From MaRDI portal
Publication:832937
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
- scientific article; zbMATH DE number 3561239 (Why is no real title available?)
- scientific article; zbMATH DE number 1775408 (Why is no real title available?)
- scientific article; zbMATH DE number 2206109 (Why is no real title available?)
- A SURVEY ON SMALL FRAGMENTS OF FIRST-ORDER LOGIC OVER FINITE WORDS
- An Effective Characterization of the Alternation Hierarchy in Two-Variable Logic
- Characterizations of some classes of regular events
- Complexity of some problems from the theory of automata
- Effective characterizations of simple fragments of temporal logic using Carton-Michel automata
- Finite-automaton aperiodicity is PSPACE-complete
- First-order fragments with successor over infinite words
- Forbidden patterns for ordered automata
- Fragments of first-order logic over infinite words
- Languages of dot-depth 3/2
- Level two of the quantifier alternation hierarchy over infinite words
- On the expressive power of temporal logic
- Structure Theorem and Strict Alternation Hierarchy for FO^2 on Words
- Sur le produit de concatenation non ambigu
- The \(\mathrm{FO}^2\) alternation hierarchy is decidable
- The half-levels of the \(\mathrm {FO}_2\) alternation hierarchy
- Unambiguous Büchi automata.
- Varieties
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)
