Closure of varieties of languages under products with counter

DOI10.1016/0022-0000(92)90029-IzbMath0766.20023OpenAlexW2037411979MaRDI QIDQ1201878

Pascal Weil

Publication date: 17 January 1993

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(92)90029-i

zbMATH Keywords

wordsdecidabilitysemidirect productlanguagesSchützenberger productlanguage varietiesrational languagenumber of factorizationsrelational morphismproduct with counter

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Varieties and pseudovarieties of semigroups (20M07) Semigroups in automata theory, linguistics, etc. (20M35)

Related Items

POLYNOMIAL CLOSURE AND TOPOLOGY, Polynomial closure and unambiguous product, Two algebraic approaches to variants of the concatenation product, Locality of DS and associated varieties, Profinite categories and semidirect products, The half-levels of the \(\mathrm {FO}_2\) alternation hierarchy, Substitution Principle and semidirect products, Subsequence Counting, Matrix Representations and a Theorem of Eilenberg, Algebraic and topological theory of languages, ALGEBRAIC CHARACTERIZATION OF LOGICALLY DEFINED TREE LANGUAGES, A STRUCTURAL APPROACH TO THE LOCALITY OF PSEUDOVARIETIES OF THE FORM LH ⓜ V, WEAKLY ITERATED BLOCK PRODUCTS AND APPLICATIONS TO LOGIC AND COMPLEXITY, Theme and Variations on the Concatenation Product, THE GLOBALS OF SOME SUBPSEUDOVARIETIES OF $\mathsf{DA}$, Irreducibility of certain pseudovarieties¹, THE GLOBALS OF SOME SUBPSEUDOVARIETIES OF $\mathsf{DA}$, Representation theory of finite semigroups, semigroup radicals and formal language theory, Trees, congruences and varieties of finite semigroups, Varieties, Languages and formations generated by \(D_4\) and \(Q_8\), On semidirect and two-sided semidirect products of finite $\mathcal {J}$trivial monoids, Algebraic tools for the concatenation product.

Cites Work

• Families of recognizable sets corresponding to certain varieties of finite monoids
• Products of languages with counter
• Semigroups and languages of dot-depth two
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• Recognizable sets and power sets of finite semigroups
• A generalization of the Schützenberger product of finite monoids
• Classification of finite monoids: the language approach
• Variétés de langages et opérations
• Aperiodic homomorphisms and the concatenation product of recognizable sets
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item