The half-levels of the \(\mathrm {FO}_2\) alternation hierarchy

DOI10.1007/s00224-016-9712-2zbMath1436.03215OpenAlexW2527182206MaRDI QIDQ2411037

Manfred Kufleitner, Alexander Lauser, Lukas Fleischer

Publication date: 20 October 2017

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-016-9712-2

zbMATH Keywords

first-order logicregular languagefinite monoidpositive variety

Mathematics Subject Classification ID

Automata and formal grammars in connection with logical questions (03D05) Semigroups in automata theory, linguistics, etc. (20M35)

Related Items

Deciding \(\mathrm{FO}^2\) alternation for automata over finite and infinite words ⋮ How many times do you need to go back to the future in unary temporal logic? ⋮ Forbidden Patterns for FO² Alternation Over Finite and Infinite Words ⋮ Varieties

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Families of recognizable sets corresponding to certain varieties of finite monoids
• The kernel of monoid morphisms
• A generalization of the Schützenberger product of finite monoids
• Classification of finite monoids: the language approach
• Classifying regular events in symbolic logic
• Two-sided wreath product of categories
• Closure of varieties of languages under products with counter
• Aperiodic homomorphisms and the concatenation product of recognizable sets
• Polynomial closure and unambiguous product
• Profinite categories and semidirect products
• Decomposition techniques for finite semigroups, using categories. II
• Finite semigroup varieties of the form V*D
• Languages of dot-depth 3/2
• Dot-depth of star-free events
• The Join Levels of the Trotter-Weil Hierarchy Are Decidable
• Algebraic Characterization of the Alternation Hierarchy in FO^2[< on Finite Words]
• Quantifier Alternation in Two-Variable First-Order Logic with Successor Is Decidable
• Weak Second‐Order Arithmetic and Finite Automata
• Structure Theorem and Strict Alternation Hierarchy for FO^2 on Words
• A SURVEY ON SMALL FRAGMENTS OF FIRST-ORDER LOGIC OVER FINITE WORDS
• Decision Problems of Finite Automata Design and Related Arithmetics
• SEMIDIRECT PRODUCTS OF ORDERED SEMIGROUPS
• THE WREATH PRODUCT PRINCIPLE FOR ORDERED SEMIGROUPS
• AROUND DOT-DEPTH ONE
• Block Products and Nesting Negations in FO2
• Going Higher in the First-Order Quantifier Alternation Hierarchy on Words
• On finite monoids having only trivial subgroups