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

DOI10.1016/j.disc.2004.04.027zbMath1058.03038MaRDI 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

Semigroups; expressive power; Automata; finite words; first-order theory of one successor; quantifier alternations

Mathematics Subject Classification ID

68Q45: Formal languages and automata

03D05: Automata and formal grammars in connection with logical questions

68Q70: Algebraic theory of languages and automata

20M35: Semigroups in automata theory, linguistics, etc.

Related Items

AROUND DOT-DEPTH ONE, 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

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