Forbidden Patterns for FO2 Alternation Over Finite and Infinite Words

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

zbMATH Keywords

automataregular languageinfinite wordsfinite model theoryforbidden pattern

Mathematics Subject Classification ID

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 FO² Alternation Over Finite and Infinite Words