Inverse Monoids, Trees, and Context-Free Languages

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

zbMATH Keywords

automatafree groupword problemmonoidsformal languagescontext-free languagesgrammarsrational subsetsinfinite binary treeuniverse semigroups

Mathematics Subject Classification ID

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 (30)

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

This page was built for publication: Inverse Monoids, Trees, and Context-Free Languages