Amalgams of finite inverse semigroups and deterministic context-free languages.

DOI10.1007/s00233-012-9399-xzbMath1275.20066OpenAlexW2067396744MaRDI QIDQ1758227

C. Nuccio, A. Cherubini Spoletini, Emanuele Rodaro

Publication date: 8 November 2012

Published in: Semigroup Forum (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00233-012-9399-x

zbMATH Keywords

word problemdecidabilityfinite inverse semigroupscontext-free languagesamalgams of inverse semigroupsSchützenberger automatacontext-free graphs

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

Decidability Versus Undecidability of the Word Problem in Amalgams of Inverse Semigroups ⋮ Amalgams of inverse semigroups and reversible two-counter machines. ⋮ An amalgam of inverse semigroups is embedded into an amalgam with a lower bounded core ⋮ Algorithmic properties of inverse monoids with hyperbolic and tree-like Schützenberger graphs ⋮ Maximal subgroups of amalgams of finite inverse semigroups. ⋮ Normal forms for semigroup amalgams

Cites Work

• Unnamed Item
• Unnamed Item
• Presentations of inverse monoids
• Amalgams of free inverse semigroups.
• Decidability of the word problem in Yamamura's HNN extensions of finite inverse semigroups.
• The theory of ends, pushdown automata, and second-order logic
• A graph-based regularity test for deterministic context-free languages
• Free products with amalgamation of inverse semigroups
• Amalgams of finite inverse semigroups.
• MULTILINEAR EQUATIONS IN AMALGAMS OF FINITE INVERSE SEMIGROUPS
• Amalgams vs Yamamura's HNN-Extensions of Inverse Semigroups
• FINITE IDEMPOTENT INVERSE MONOID PRESENTATIONS
• BICYCLIC SUBSEMIGROUPS IN AMALGAMS OF FINITE INVERSE SEMIGROUPS
• Inverse Monoids, Trees, and Context-Free Languages
• Free Inverse Semigroups
• Regularity Problems for Visibly Pushdown Languages
• Amalgamated free products of inverse semigroups

This page was built for publication: Amalgams of finite inverse semigroups and deterministic context-free languages.