Forbidden Patterns for FO2 Alternation Over Finite and Infinite Words
From MaRDI portal
Publication:6169964
DOI10.1142/s0129054123440021arXiv2105.09291OpenAlexW4321498545MaRDI QIDQ6169964
Manfred Kufleitner, Viktor Henriksson
Publication date: 15 August 2023
Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2105.09291
Formal languages and automata (68Q45) Model theory of finite structures (03C13) Descriptive complexity and finite models (68Q19)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Fragments of first-order logic over infinite words
- Finite-automaton aperiodicity is PSPACE-complete
- Deciding \(\mathrm{FO}^2\) alternation for automata over finite and infinite words
- Characterizations of some classes of regular events
- 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
- On finite monoids having only trivial subgroups
This page was built for publication: Forbidden Patterns for FO2 Alternation Over Finite and Infinite Words
