Inverse Monoids, Trees, and Context-Free Languages
From MaRDI portal
Publication:4038472
DOI10.2307/2154268zbMath0795.20043MaRDI QIDQ4038472
Stuart W. Margolis, John C. Meakin
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
automata; free group; word problem; monoids; formal languages; context-free languages; grammars; rational subsets; infinite binary tree; universe semigroups
68Q45: Formal languages and automata
20M05: Free semigroups, generators and relations, word problems
68Q70: Algebraic theory of languages and automata
20M35: Semigroups in automata theory, linguistics, etc.
20M18: Inverse semigroups
Related Items
McAlister'sP-Theorem via Schützenberger Graphs, HNN EXTENSIONS OF SEMILATTICES, EMBEDDING THEOREMS FOR GROUPS PRESENTED VIA PARTIAL AUTOMORPHISMS: A GENERALIZATION OF SEMIDIRECT PRODUCTS AND HNN EXTENSIONS, Expansions of inverse semigroups, On one-relator monoids and one-relator groups, Amalgamated free products of inverse semigroups, Amalgamated free products of inverse semigroups, Trees associated to inverse monoid presentations, Amalgams of free inverse semigroups., Partially commutative inverse monoids., Inverse monoids and rational Schreier subsets of the free group, The word problem of inverse monoids presented by one idempotent relator, The uniform word problem for groups and finite Rees quotients of \(E\)-unitary inverse semigroups, Amalgams of finite inverse semigroups., The word problem for nilpotent inverse monoids, Finitely presented groups and completely regular semigroups, On the decidability of the word problem for amalgamated free products of inverse semigroups., Inverse monoids: decidability and complexity of algebraic questions., A Lower Bound For Reversible Automata, Locally full HNN extensions of inverse semigroups, On free inverse monoid languages