Amalgams of inverse semigroups and reversible two-counter machines.

DOI10.1016/j.jpaa.2012.08.012zbMath1277.20072arXiv1105.1905OpenAlexW2095161514MaRDI QIDQ2376520

Pedro V. Silva, Emanuele Rodaro

Publication date: 24 June 2013

Published in: Journal of Pure and Applied Algebra (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1105.1905

zbMATH Keywords

word probleminverse semigroupsdecidabilitysemigroup amalgamsSchützenberger graphsamalgamated free productscounter machinesreversible machines

Mathematics Subject Classification ID

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

Decidability Versus Undecidability of the Word Problem in Amalgams of Inverse Semigroups ⋮ Undecidability of the word problem for Yamamura's HNN-extension under nice conditions. ⋮ ON PERIODIC POINTS OF FREE INVERSE MONOID HOMOMORPHISMS ⋮ Schützenberger automata for HNN-extensions of inverse monoids and their use in algorithmic questions ⋮ Maximal subgroups of amalgams of finite inverse semigroups.

Cites Work

• Unnamed Item
• Unnamed Item
• Presentations of inverse monoids
• Decidability of the word problem in Yamamura's HNN extensions of finite inverse semigroups.
• Free products with amalgamation of inverse semigroups
• Universality of a reversible two-counter machine
• Algorithmic problems for amalgams of finite semigroups
• Amalgams of finite inverse semigroups and deterministic context-free languages.
• Amalgams of finite inverse semigroups.
• MULTILINEAR EQUATIONS IN AMALGAMS OF FINITE INVERSE SEMIGROUPS
• Note on idempotent semigroups, I
• BICYCLIC SUBSEMIGROUPS IN AMALGAMS OF FINITE INVERSE SEMIGROUPS
• Free Inverse Semigroups
• ON THE WORD PROBLEM FOR TENSOR PRODUCTS AND AMALGAMS OF MONOIDS
• Amalgamated free products of inverse semigroups
• Amalgamated free products of inverse semigroups