Polynomial closure and unambiguous product
From MaRDI portal
Publication:1361889
DOI10.1007/BF02679467zbMATH Open0872.68119OpenAlexW2042177219MaRDI QIDQ1361889FDOQ1361889
Publication date: 28 July 1997
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf02679467
Recommendations
algebraic theory of automata[https://portal.mardi4nfdi.de/w/index.php?title=+Special%3ASearch&search=B%EF%BF%BD%EF%BF%BDchi%27s+sequential+calculus&go=Go B��chi's sequential calculus]
Cites Work
- Title not available (Why is that?)
- Varieties of ordered algebras
- Title not available (Why is that?)
- Title not available (Why is that?)
- Characterizations of locally testable events
- A property of the Schützenberger product
- Title not available (Why is that?)
- A topology for free groups and related groups
- Title not available (Why is that?)
- On finite monoids having only trivial subgroups
- Classifying regular events in symbolic logic
- Characterizations of some classes of regular events
- First-order logic and star-free sets
- Semigroups and languages of dot-depth two
- A generalization of the Schützenberger product of finite monoids
- Classification of finite monoids: the language approach
- Logic, semigroups and automata on words
- Finite semigroup varieties of the form V*D
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Polynomial closure of group languages and open sets of the Hall topology
- Title not available (Why is that?)
- INEVITABLE GRAPHS: A PROOF OF THE TYPE II CONJECTURE AND SOME RELATED DECISION PROCEDURES
- A Conjecture on the Hall Topology for the Free Group
- ASH'S TYPE II THEOREM, PROFINITE TOPOLOGY AND MALCEV PRODUCTS: PART I
- On The Profinite Topology on a Free Group
- Games, equations and the dot-depth hierarchy
- Topologies for the free monoid
- The Birkhoff theorem for finite algebras
- Locally trivial categories and unambiguous concatenation
- Some results on the dot-depth hierarchy
- Sur le produit de concatenation non ambigu
- Une topologie du monoide libre
- Partially ordered finite monoids and a theorem of I. Simon
- Implicit operations on finite \({\mathcal J}\)-trivial semigroups and a conjecture of I. Simon
- Equations and dot-depth one
- Title not available (Why is that?)
- Title not available (Why is that?)
- Factorization forests of finite height
- On a conjecture concerning dot-depth two languages
- Games, equations and dot-depth two monoids
- The dot-depth hierarchy of star-free languages is infinite
- On dot-depth two
- Profinite semigroups, Mal'cev products, and identities
- Title not available (Why is that?)
- Polynomial operations and hierarchies of concatenation
- A Reiterman theorem for pseudovarieties of finite first-order structures
- Aperiodic homomorphisms and the concatenation product of recognizable sets
- Closure of varieties of languages under products with counter
- Title not available (Why is that?)
- INVERSE MONOIDS OF DOT-DEPTH TWO
- Sur mon article Une topologie du monoide libre
- Inverse monoids of dot-depth two
- Some logical characterizations of the dot-depth hierarchy and applications
- Title not available (Why is that?)
- Title not available (Why is that?)
- On a complete set of generators for dot-depth two
Cited In (79)
- Regular languages and partial commutations
- Representations of relatively free profinite semigroups, irreducibility, and order primitivity
- Schreier split extensions of preordered monoids
- Perfect correspondences between dot-depth and polynomial-time hierarchies
- Some results onC-varieties
- One quantifier alternation in first-order logic with modular predicates
- PROFINITE METHODS IN SEMIGROUP THEORY
- A Reiterman theorem for pseudovarieties of finite first-order structures
- On Existentially First-Order Definable Languages and Their Relation to NP
- Hierarchies and reducibilities on regular languages related to modulo counting
- Tribute: The influence of Imre Simon's work in the theory of automata, languages and semigroups
- Quantifier Alternation for Infinite Words
- Permutation rewriting and algorithmic verification
- A Note on Decidable Separability by Piecewise Testable Languages
- Factorization forests for infinite words and applications to countable scattered linear orderings
- On Decidability of Intermediate Levels of Concatenation Hierarchies
- Some complexity results for polynomial rational expressions.
- A note on partially ordered tree automata
- The factorisation forest theorem
- Separating regular languages with two quantifier alternations
- On Shuffle Ideals
- The \(\omega\)-inequality problem for concatenation hierarchies of star-free languages
- A counterexample to a conjecture concerning concatenation hierarchies
- Two algebraic approaches to variants of the concatenation product
- Varieties
- EQUATIONAL DESCRIPTIONS OF LANGUAGES
- Pseudovarieties defining classes of sofic subshifts closed under taking shift equivalent subshifts.
- Local testability from words to traces, a suitable definition
- Efficient algorithms for membership in Boolean hierarchies of regular languages
- Varieties and pseudovarieties of ordered normal bands
- Closure of varieties of languages under products with counter
- Title not available (Why is that?)
- Generic results for concatenation hierarchies
- Polynomials, fragments of temporal logic and the variety DA over traces
- The half-levels of the \(\mathrm {FO}_2\) alternation hierarchy
- AROUND DOT-DEPTH ONE
- Unambiguity in Automata Theory
- Polynomial operations and hierarchies of concatenation
- PARTIALLY ORDERED TWO-WAY BÜCHI AUTOMATA
- Languages polylog-time reducible to dot-depth 1/2
- Factorization Forests
- Algebraic tools for the concatenation product.
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Machines that can output empty words
- Hierarchies of Piecewise Testable Languages
- Conservative groupoids recognize only regular languages
- Efficiency of automata in semi-commutation verification techniques
- Imre Simon: an exceptional graduate student
- Title not available (Why is that?)
- Relating Automata-theoretic Hierarchies to Complexity-theoretic Hierarchies
- A reducibility for the dot-depth hierarchy
- The Height of Factorization Forests
- Equations Defining the Polynomial Closure of a Lattice of Regular Languages
- Polynomial closure
- On FO 2 Quantifier Alternation over Words
- A conjecture on the concatenation product
- THE DOT-DEPTH AND THE POLYNOMIAL HIERARCHIES CORRESPOND ON THE DELTA LEVELS
- A SURVEY ON SMALL FRAGMENTS OF FIRST-ORDER LOGIC OVER FINITE WORDS
- Languages of dot-depth 3/2
- Concatenation hierarchies: new bottle, old wine
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- On the state complexity of closures and interiors of regular languages with subwords and superwords
- On fixed points of the lower set operator
- All about unambiguous polynomial closure
- Partially Ordered Two-Way Büchi Automata
- Separating Without Any Ambiguity.
- Polynomial Operators on Classes of Regular Languages
- Theme and Variations on the Concatenation Product
- The globals of pseudovarieties of ordered semigroups containingB2and an application to a problem proposed by Pin
- The omega-reducibility of pseudovarieties of ordered monoids representing low levels of concatenation hierarchies
- Two non-closure results on families ofL languages
- The regular languages of first-order logic with one alternation
- The Quantifier Alternation Hierarchy of Synchronous Relations
- How many times do you need to go back to the future in unary temporal logic?
- ON THE NON-DETERMINISTIC COMMUNICATION COMPLEXITY OF REGULAR LANGUAGES
This page was built for publication: Polynomial closure and unambiguous product
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1361889)
