Expressive power of existential first-order sentences of Büchi's sequential calculus

DOI10.1016/j.disc.2004.04.027zbMath1058.03038OpenAlexW2119414381MaRDI QIDQ1772275

Jean-Eric Pin

Publication date: 18 April 2005

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disc.2004.04.027

zbMATH Keywords

Semigroupsexpressive powerAutomatafinite wordsfirst-order theory of one successorquantifier alternations

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05) Algebraic theory of languages and automata (68Q70) Semigroups in automata theory, linguistics, etc. (20M35)

Related Items (4)

A new algorithm for testing if a regular language is locally threshold testable ⋮ On FO 2 Quantifier Alternation over Words ⋮ A SURVEY ON SMALL FRAGMENTS OF FIRST-ORDER LOGIC OVER FINITE WORDS ⋮ AROUND DOT-DEPTH ONE

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
• Unnamed Item
• Finite-automaton aperiodicity is PSPACE-complete
• First-order logic and star-free sets
• Classifying regular events in symbolic logic
• Languages and scanners
• Automata, languages and programming. 16th international colloquium, Stresa, Italy, July 11-15, 1989. Proceedings
• Logic, semigroups and automata on words
• Graph congruences and wreath products
• On the expressive power of temporal logic
• Characterizations of locally testable events
• Complexity of some problems from the theory of automata
• Algebraic decision procedures for local testability
• On the Ehrenfeucht-Fraïssé game in theoretical computer science
• On finite monoids having only trivial subgroups

This page was built for publication: Expressive power of existential first-order sentences of Büchi's sequential calculus