Classification of finite monoids: the language approach
From MaRDI portal
Publication:1157412
DOI10.1016/0304-3975(81)90057-8zbMath0471.20055OpenAlexW2019522567MaRDI QIDQ1157412
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)90057-8
Formal languages and automata (68Q45) Algebraic theory of languages and automata (68Q70) Semigroups in automata theory, linguistics, etc. (20M35)
Related Items
Some complexity results for polynomial rational expressions., Efficient algorithms for membership in Boolean hierarchies of regular languages, Polynomial closure and unambiguous product, Semigroups and languages of dot-depth two, Partially ordered finite monoids and a theorem of I. Simon, Concatenation hierarchies: new bottle, old wine, Varieties of finite categories, The half-levels of the \(\mathrm {FO}_2\) alternation hierarchy, Alternation Hierarchies of First Order Logic with Regular Predicates, Unnamed Item, Unnamed Item, 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, Efficiency of automata in semi-commutation verification techniques, Products of languages with counter, A SURVEY ON SMALL FRAGMENTS OF FIRST-ORDER LOGIC OVER FINITE WORDS, On shuffle products, acyclic automata and piecewise-testable languages, Circuit complexity of regular languages, The \(\omega\)-inequality problem for concatenation hierarchies of star-free languages, Theme and Variations on the Concatenation Product, \(NC^ 1\): The automata-theoretic viewpoint, On Rough Approximations of Languages under Infinite Index Indiscernibility Relations, Closure of varieties of languages under products with counter, Languages of dot-depth 3/2, Circuit complexity of regular languages, AROUND DOT-DEPTH ONE, Descriptional and computational complexity of finite automata -- a survey, Finite semigroup varieties of the form V*D, Complexity of universality and related problems for partially ordered NFAs, On Shuffle Ideals, Machines that can output empty words, The pseudovariety of semigroups of triangular matrices over a finite field, Imre Simon: an exceptional graduate student, The Power of Diversity, Descriptional and Computational Complexity of Finite Automata, Unnamed Item, Separating regular languages with two quantifier alternations, Generic results for concatenation hierarchies, Varieties, One quantifier alternation in first-order logic with modular predicates, On semidirect products of two finite semilattices, Languages and formations generated by \(D_4\) and \(Q_8\), Unnamed Item, Characterizing level one in group-based concatenation hierarchies, Algebraic tools for the concatenation product., Languages defined with modular counting quantifiers, Non-uniform automata over groups, A conjecture on the concatenation product, State complexity of permutation and related decision problems on alphabetical pattern constraints
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Families of recognizable sets corresponding to certain varieties of finite monoids
- Languages of R-trivial monoids
- A generalization of the Schützenberger product of finite monoids
- On finite monoids having only trivial subgroups
- The Invalidity of Markoff's Schema
