Inverse Monoids, Trees, and Context-Free Languages
From MaRDI portal
Publication:4038472
DOI10.2307/2154268zbMath0795.20043OpenAlexW4235290936MaRDI QIDQ4038472
John C. Meakin, Stuart W. Margolis
Publication date: 16 May 1993
Published in: Transactions of the American Mathematical Society (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.2307/2154268
automatafree groupword problemmonoidsformal languagescontext-free languagesgrammarsrational subsetsinfinite binary treeuniverse semigroups
Formal languages and automata (68Q45) Free semigroups, generators and relations, word problems (20M05) Algebraic theory of languages and automata (68Q70) Semigroups in automata theory, linguistics, etc. (20M35) Inverse semigroups (20M18)
Related Items
EMBEDDING THEOREMS FOR GROUPS PRESENTED VIA PARTIAL AUTOMORPHISMS: A GENERALIZATION OF SEMIDIRECT PRODUCTS AND HNN EXTENSIONS, The word problem for nilpotent inverse monoids, Inverse monoids: decidability and complexity of algebraic questions., Finitely presented groups and completely regular semigroups, A Munn tree type representation for the elements of the bifree locally inverse semigroup, The uniform word problem for groups and finite Rees quotients of \(E\)-unitary inverse semigroups, A Lower Bound For Reversible Automata, A tribute to John Meakin on the occasion of his 75th birthday, Locally full HNN extensions of inverse semigroups, Inverse monoids and rational Schreier subsets of the free group, The word problem for one-relation monoids: a survey, Amalgams of free inverse semigroups., Partially commutative inverse monoids., Amalgams of finite inverse semigroups and deterministic context-free languages., On the decidability of the word problem for amalgamated free products of inverse semigroups., On one-relator monoids and one-relator groups, Amalgamated free products of inverse semigroups, Amalgamated free products of inverse semigroups, Amalgams of finite inverse semigroups., McAlister'sP-Theorem via Schützenberger Graphs, Trees associated to inverse monoid presentations, Undecidability of the word problem for one-relator inverse monoids via right-angled Artin subgroups of one-relator groups, New results on the prefix membership problem for one-relator groups, Expansions of inverse semigroups, Algorithmic properties of inverse monoids with hyperbolic and tree-like Schützenberger graphs, On free inverse monoid languages, The word problem of inverse monoids presented by one idempotent relator, On labeled birooted tree languages: algebras, automata and logic, HNN EXTENSIONS OF SEMILATTICES, On one-relator groups and units of special one-relation inverse monoids