Logic, semigroups and automata on words

DOI10.1007/BF02127803zbMath0860.68071MaRDI QIDQ1817074

Jean-Eric Pin

Publication date: 1 December 1996

Published in: Annals of Mathematics and Artificial Intelligence (Search for Journal in Brave)

zbMATH Keywords

sequential calculus

Mathematics Subject Classification ID

Related Items (24)

Closure properties of locally finite \(\omega\)-languages ⋮ Efficient algorithms for membership in Boolean hierarchies of regular languages ⋮ Tameness of Some Locally Trivial Pseudovarieties ⋮ Polynomial closure of group languages and open sets of the Hall topology ⋮ Polynomial closure and unambiguous product ⋮ On the Topological Complexity of Infinitary Rational Relations ⋮ Undecidability of Topological and Arithmetical Properties of Infinitary Rational Relations ⋮ A game theoretical approach to the algebraic counterpart of the Wagner hierarchy : Part I ⋮ On ideals of quasi-commutative semigroups ⋮ Unnamed Item ⋮ The Algebraic Counterpart of the Wagner Hierarchy ⋮ On the continuity set of an Omega rational function ⋮ A SURVEY ON SMALL FRAGMENTS OF FIRST-ORDER LOGIC OVER FINITE WORDS ⋮ The Ideal Approach to Computing Closed Subsets in Well-Quasi-orderings ⋮ Topological complexity of locally finite \(\omega\)-languages ⋮ ALGEBRAIC CHARACTERIZATION OF LOGICALLY DEFINED TREE LANGUAGES ⋮ Theme and Variations on the Concatenation Product ⋮ The Model Checking Problem for Prefix Classes of Second-Order Logic: A Survey ⋮ A note on partially ordered tree automata ⋮ Locally finite languages ⋮ Expressive power of existential first-order sentences of Büchi's sequential calculus ⋮ Locally finite ω-languages and effective analytic sets have the same topological complexity ⋮ Algebraic tools for the concatenation product. ⋮ Star-free sets of words on ordinals

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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finite-model theory -- A personal perspective
• Bilimites de langages reconnaissables
• On the expressive power of temporal logic for infinite words
• Finite-automaton aperiodicity is PSPACE-complete
• Factorization forests of finite height
• A syntactic congruence for rational \(\omega\)-languages
• Characterizations of some classes of regular events
• First-order logic and star-free sets
• The method of forced enumeration for nondeterministic automata
• Semigroups and languages of dot-depth two
• Partially ordered finite monoids and a theorem of I. Simon
• On a natural extension of Jacob's ranks
• Inverse monoids of dot-depth two
• Classifying regular events in symbolic logic
• Languages and scanners
• Polynomial operations and hierarchies of concatenation
• On a conjecture concerning dot-depth two languages
• Some results on the dot-depth hierarchy
• The polynomial-time hierarchy
• The dot-depth hierarchy of star-free languages is infinite
• Büchi's monadic second order successor arithmetic.
• Aperiodic homomorphisms and the concatenation product of recognizable sets
• Graph congruences and wreath products
• Implicit operations on finite \({\mathcal J}\)-trivial semigroups and a conjecture of I. Simon
• On the expressive power of temporal logic
• Characterizations of locally testable events
• Weak Second‐Order Arithmetic and Finite Automata
• Complexity of some problems from the theory of automata
• Ensembles Reconnaissables de Mots Biinfinis
• Languages that Capture Complexity Classes
• Nondeterministic Space is Closed under Complementation
• Decision Problems of Finite Automata Design and Related Arithmetics
• ON CERTAIN EXTENSIONS OF THE ARITHMETIC OF ADDITION OF NATURAL NUMBERS
• A combinatorial approach to the theory of ω-automata
• Application of model theoretic games to discrete linear orders and finite automata
• Star-free regular sets of ω-sequences
• INVERSE MONOIDS OF DOT-DEPTH TWO
• AN ALGEBRAIC THEORY FOR REGULAR LANGUAGES OF FINITE AND INFINITE WORDS
• Algebraic decision procedures for local testability
• On finite monoids having only trivial subgroups
• Decision problems forω-automata
• Definability in the monadic second-order theory of successor
• Testing and generating infinite sequences by a finite automaton
• Concatenation as a basis for arithmetic

This page was built for publication: Logic, semigroups and automata on words