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

DOI10.1007/s00233-012-9399-xzbMath1275.20066MaRDI 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 problem; decidability; finite inverse semigroups; context-free languages; amalgams of inverse semigroups; Schützenberger automata; context-free graphs

Mathematics Subject Classification ID

68Q45: Formal languages and automata

20M05: Free semigroups, generators and relations, word problems

20M35: Semigroups in automata theory, linguistics, etc.

20M18: Inverse semigroups

Related Items

An amalgam of inverse semigroups is embedded into an amalgam with a lower bounded core, Maximal subgroups of amalgams of finite inverse semigroups., Normal forms for semigroup amalgams, Amalgams of inverse semigroups and reversible two-counter machines., Decidability Versus Undecidability of the Word Problem in Amalgams of Inverse Semigroups

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