The word problem of inverse monoids presented by one idempotent relator
From MaRDI portal
Publication:1314383
DOI10.1016/0304-3975(92)00063-WzbMath0801.20039MaRDI QIDQ1314383
Stuart W. Margolis, Jean-Camille Birget, John C. Meakin
Publication date: 27 March 1994
Published in: Theoretical Computer Science (Search for Journal in Brave)
complexityidempotentgeneratorsword probleminverse semigroupsautomatonfree inverse monoiddeterministic context-free languageMunn tree
Formal languages and automata (68Q45) Free semigroups, generators and relations, word problems (20M05) Semigroups in automata theory, linguistics, etc. (20M35) Inverse semigroups (20M18)
Related Items
PRESENTATIONS OF INVERSE SEMIGROUPS, THEIR KERNELS AND EXTENSIONS, Inverse monoids: decidability and complexity of algebraic questions., ALGORITHMIC PROBLEMS ON INVERSE MONOIDS OVER VIRTUALLY FREE GROUPS, The word problem for one-relation monoids: a survey, Amalgams of free inverse semigroups., Inverse monoids and rational subsets of related groups, Trees associated to inverse monoid presentations, The work of Douglas Munn and its legacy, Decision problems for inverse monoids presented by a single sparse relator., New results on the prefix membership problem for one-relator groups, Algorithmic properties of inverse monoids with hyperbolic and tree-like Schützenberger graphs, On growth, identities and free subsemigroups for inverse semigroups of deficiency one, On one-relator groups and units of special one-relation inverse monoids
Cites Work
