Polynomial closure and unambiguous product
From MaRDI portal
Publication:1361889
DOI10.1007/BF02679467zbMath0872.68119OpenAlexW2042177219MaRDI QIDQ1361889
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
Related Items
Some complexity results for polynomial rational expressions. ⋮ PROFINITE METHODS IN SEMIGROUP THEORY ⋮ Relating Automata-theoretic Hierarchies to Complexity-theoretic Hierarchies ⋮ On Decidability of Intermediate Levels of Concatenation Hierarchies ⋮ Efficient algorithms for membership in Boolean hierarchies of regular languages ⋮ Factorization forests for infinite words and applications to countable scattered linear orderings ⋮ On FO 2 Quantifier Alternation over Words ⋮ Languages polylog-time reducible to dot-depth 1/2 ⋮ Two algebraic approaches to variants of the concatenation product ⋮ Permutation rewriting and algorithmic verification ⋮ Concatenation hierarchies: new bottle, old wine ⋮ Pseudovarieties defining classes of sofic subshifts closed under taking shift equivalent subshifts. ⋮ A Reiterman theorem for pseudovarieties of finite first-order structures ⋮ Polynomials, fragments of temporal logic and the variety DA over traces ⋮ The half-levels of the \(\mathrm {FO}_2\) alternation hierarchy ⋮ Regular languages and partial commutations ⋮ Unnamed Item ⋮ A Note on Decidable Separability by Piecewise Testable Languages ⋮ Unnamed Item ⋮ PARTIALLY ORDERED TWO-WAY BÜCHI AUTOMATA ⋮ How many times do you need to go back to the future in unary temporal logic? ⋮ On the state complexity of closures and interiors of regular languages with subwords and superwords ⋮ Unnamed Item ⋮ The omega-reducibility of pseudovarieties of ordered monoids representing low levels of concatenation hierarchies ⋮ Efficiency of automata in semi-commutation verification techniques ⋮ Hierarchies of Piecewise Testable Languages ⋮ A SURVEY ON SMALL FRAGMENTS OF FIRST-ORDER LOGIC OVER FINITE WORDS ⋮ Conservative groupoids recognize only regular languages ⋮ Perfect correspondences between dot-depth and polynomial-time hierarchies ⋮ Tribute: The influence of Imre Simon's work in the theory of automata, languages and semigroups ⋮ Hierarchies and reducibilities on regular languages related to modulo counting ⋮ Separating Without Any Ambiguity. ⋮ The \(\omega\)-inequality problem for concatenation hierarchies of star-free languages ⋮ Theme and Variations on the Concatenation Product ⋮ Languages of dot-depth 3/2 ⋮ EQUATIONAL DESCRIPTIONS OF LANGUAGES ⋮ AROUND DOT-DEPTH ONE ⋮ ON THE NON-DETERMINISTIC COMMUNICATION COMPLEXITY OF REGULAR LANGUAGES ⋮ A note on partially ordered tree automata ⋮ On Shuffle Ideals ⋮ Machines that can output empty words ⋮ The globals of pseudovarieties of ordered semigroups containingB2and an application to a problem proposed by Pin ⋮ Some results onC-varieties ⋮ Imre Simon: an exceptional graduate student ⋮ The Height of Factorization Forests ⋮ A counterexample to a conjecture concerning concatenation hierarchies ⋮ Local testability from words to traces, a suitable definition ⋮ Schreier split extensions of preordered monoids ⋮ Partially Ordered Two-Way Büchi Automata ⋮ Unnamed Item ⋮ THE DOT-DEPTH AND THE POLYNOMIAL HIERARCHIES CORRESPOND ON THE DELTA LEVELS ⋮ Quantifier Alternation for Infinite Words ⋮ Representations of relatively free profinite semigroups, irreducibility, and order primitivity ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Separating regular languages with two quantifier alternations ⋮ Factorization Forests ⋮ On Existentially First-Order Definable Languages and Their Relation to NP ⋮ Generic results for concatenation hierarchies ⋮ The Quantifier Alternation Hierarchy of Synchronous Relations ⋮ Varieties ⋮ The factorisation forest theorem ⋮ Varieties and pseudovarieties of ordered normal bands ⋮ One quantifier alternation in first-order logic with modular predicates ⋮ Unambiguity in Automata Theory ⋮ On fixed points of the lower set operator ⋮ Unnamed Item ⋮ A reducibility for the dot-depth hierarchy ⋮ Algebraic tools for the concatenation product. ⋮ A conjecture on the concatenation product
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
- Equations and dot-depth one
- Factorization forests of finite height
- Characterizations of some classes of regular events
- First-order logic and star-free sets
- A property of the Schützenberger product
- Locally trivial categories and unambiguous concatenation
- Semigroups and languages of dot-depth two
- Partially ordered finite monoids and a theorem of I. Simon
- Inverse monoids of dot-depth two
- Une topologie du monoide libre
- A generalization of the Schützenberger product of finite monoids
- Sur mon article Une topologie du monoide libre
- Classification of finite monoids: the language approach
- The Birkhoff theorem for finite algebras
- Classifying regular events in symbolic logic
- Topologies for the free monoid
- Polynomial operations and hierarchies of concatenation
- On a conjecture concerning dot-depth two languages
- Games, equations and dot-depth two monoids
- Closure of varieties of languages under products with counter
- Some results on the dot-depth hierarchy
- Varieties of ordered algebras
- The dot-depth hierarchy of star-free languages is infinite
- Sur le produit de concatenation non ambigu
- Aperiodic homomorphisms and the concatenation product of recognizable sets
- On a complete set of generators for dot-depth two
- Polynomial closure of group languages and open sets of the Hall topology
- Logic, semigroups and automata on words
- Games, equations and the dot-depth hierarchy
- Some logical characterizations of the dot-depth hierarchy and applications
- A Reiterman theorem for pseudovarieties of finite first-order structures
- Profinite semigroups, Mal'cev products, and identities
- Finite semigroup varieties of the form V*D
- Implicit operations on finite \({\mathcal J}\)-trivial semigroups and a conjecture of I. Simon
- Characterizations of locally testable events
- 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
- INVERSE MONOIDS OF DOT-DEPTH TWO
- On The Profinite Topology on a Free Group
- On finite monoids having only trivial subgroups
- On dot-depth two
- A topology for free groups and related groups
