Languages of R-trivial monoids

DOI10.1016/0022-0000(80)90003-3zbMath0446.68066OpenAlexW2094423121MaRDI QIDQ1146010

Faith E. Fich, Janusz A. Brzozowski

Publication date: 1980

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(80)90003-3

zbMATH Keywords

finite automataregular languagessyntactic monoidsR-trivial monoids

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Algebraic theory of languages and automata (68Q70) Semigroups in automata theory, linguistics, etc. (20M35)

Related Items (30)

Constrained synchronization and subset synchronization problems for weakly acyclic automata ⋮ Left and right negatively orderable semigroups and a one-sided version of Simon's theorem ⋮ Two algebraic approaches to variants of the concatenation product ⋮ Learning from positive and negative examples: dichotomies and parameterized algorithms ⋮ The \(\kappa\)-word problem over \(\mathsf{DRH}\) ⋮ Unnamed Item ⋮ State Complexity of Permutation and the Language Inclusion Problem up to Parikh Equivalence on Alphabetical Pattern Constraints and Partially Ordered NFAs ⋮ Large Aperiodic Semigroups ⋮ Finite semigroups, feedback, and the Letichevsky criteria on non-empty words in finite automata. ⋮ Languages of R-trivial monoids ⋮ Catalan monoids inherently nonfinitely based relative to finite \(\mathscr{R}\)-trivial semigroups ⋮ Classification of finite monoids: the language approach ⋮ Products of languages with counter ⋮ Recognizable languages and congruences ⋮ On shuffle products, acyclic automata and piecewise-testable languages ⋮ Theme and Variations on the Concatenation Product ⋮ \(NC^ 1\): The automata-theoretic viewpoint ⋮ SYNTACTIC COMPLEXITY OF ℛ- AND 𝒥-TRIVIAL REGULAR LANGUAGES ⋮ Complexity of universality and related problems for partially ordered NFAs ⋮ A sufficient condition to polynomially compute a minimum separating DFA ⋮ Learning in varieties of the form \(\mathbf {V^{*}LI}\) from positive data ⋮ Complexity of deciding detectability in discrete event systems ⋮ Synchronization problems in automata without non-trivial cycles ⋮ On generalized locally testable languages ⋮ On verification of D-detectability for discrete event systems ⋮ Geometrically closed positive varieties of languages ⋮ On semidirect and two-sided semidirect products of finite $\mathcal {J}$trivial monoids ⋮ Directed nonabelian sandpile models on trees ⋮ Synchronizing series-parallel deterministic finite automata with loops and related problems ⋮ State complexity of permutation and related decision problems on alphabetical pattern constraints

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Languages of R-trivial monoids
• A generalization of finiteness
• Dot-depth of star-free events
• On the structure of semigroups
• On finite monoids having only trivial subgroups
• Remarks on algebraic decomposition of automata
• A Note on Fast Cyclic Convolution

This page was built for publication: Languages of R-trivial monoids