Logic, semigroups and automata on words

DOI10.1007/BF02127803zbMATH Open0860.68071MaRDI QIDQ1817074FDOQ1817074

Jean-Éric 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

Formal languages and automata (68Q45)

Cites Work

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

Cited In (31)

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

   Recommendations

• Expressive power of existential first-order sentences of Büchi's sequential calculus 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• A MODEL-THEORETIC CHARACTERIZATION OF MONADIC SECOND ORDER LOGIC ON INFINITE WORDS 👍 👎

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1817074)