A generalization of the Schützenberger product of finite monoids
From MaRDI portal
Publication:1150445
DOI10.1016/0304-3975(81)90036-0zbMath0456.20048OpenAlexW2076872551MaRDI QIDQ1150445
Publication date: 1981
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(81)90036-0
free monoiddot-depth hierarchysyntactic monoidrecognizable subsetconcatenation productproduct of finite monoids
Free semigroups, generators and relations, word problems (20M05) Artificial intelligence (68T99) Semigroups in automata theory, linguistics, etc. (20M35)
Related Items (55)
Unnamed Item ⋮ A property of the Schützenberger product ⋮ Efficient algorithms for membership in Boolean hierarchies of regular languages ⋮ Polynomial closure and unambiguous product ⋮ Semigroups and languages of dot-depth two ⋮ Concatenation hierarchies: new bottle, old wine ⋮ Inverse monoids of dot-depth two ⋮ The half-levels of the \(\mathrm {FO}_2\) alternation hierarchy ⋮ Alternation Hierarchies of First Order Logic with Regular Predicates ⋮ Unnamed Item ⋮ Schützenberger-like products in non-free monoids ⋮ State Complexity of Permutation and the Language Inclusion Problem up to Parikh Equivalence on Alphabetical Pattern Constraints and Partially Ordered NFAs ⋮ Sur le produit avec compteur modulo un nombre premier ⋮ A Trichotomy for Regular Trail Queries ⋮ Separability by piecewise testable languages is \textsc{PTime}-complete ⋮ The omega-reducibility of pseudovarieties of ordered monoids representing low levels of concatenation hierarchies ⋮ Classification of finite monoids: the language approach ⋮ Unnamed Item ⋮ Products of languages with counter ⋮ Complete rewriting system for the Schützenberger product of n groups ⋮ A SURVEY ON SMALL FRAGMENTS OF FIRST-ORDER LOGIC OVER FINITE WORDS ⋮ Topologies for the free monoid ⋮ The product of rational languages ⋮ The \(\omega\)-inequality problem for concatenation hierarchies of star-free languages ⋮ Theme and Variations on the Concatenation Product ⋮ Games, equations and dot-depth two monoids ⋮ Closure of varieties of languages under products with counter ⋮ Languages of dot-depth 3/2 ⋮ IDEMPOTENT POINTLIKE SETS ⋮ Circuit complexity of regular languages ⋮ Gröbner-Shirshov bases of some monoids. ⋮ Some results on the dot-depth hierarchy ⋮ AROUND DOT-DEPTH ONE ⋮ Irreducibility of certain pseudovarieties1 ⋮ Complexity of universality and related problems for partially ordered NFAs ⋮ On dot-depth two ⋮ Machines that can output empty words ⋮ An application of the Ehrenfeucht-Fraisse game in formal language theory ⋮ The globals of pseudovarieties of ordered semigroups containingB2and an application to a problem proposed by Pin ⋮ Expansions, free inverse semigroups, and Schützenberger product ⋮ Representation theory of finite semigroups, semigroup radicals and formal language theory ⋮ On The Schützenberger Product of Three Copies of a Free Group ⋮ Presentations of the Schützenberger Product of n Groups ⋮ Separating regular languages with two quantifier alternations ⋮ Trees, congruences and varieties of finite semigroups ⋮ Generic results for concatenation hierarchies ⋮ Sur les monoides dont tous les groupes sont resolubles ⋮ One quantifier alternation in first-order logic with modular predicates ⋮ Unnamed Item ⋮ Characterizing level one in group-based concatenation hierarchies ⋮ An application of the matrix representation of transductions ⋮ Algebraic tools for the concatenation product. ⋮ Almost finite expansions of arbitrary semigroups ⋮ A conjecture on the concatenation product ⋮ State complexity of permutation and related decision problems on alphabetical pattern constraints
Cites Work
This page was built for publication: A generalization of the Schützenberger product of finite monoids
