On D0L and HDT0L sets in monoids

DOI10.1007/S002339910036MaRDI QIDQ1976433zbMATH OpenOpenAlexFDO

Authors Juha Honkala

Publication date 27 August 2001

Published in Semigroup Forum (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s002339910036

zbMATH Keywords

decidabilityfree monoidsfree partial commutative monoidsLindenmayer systemsstrong projection property

Mathematics Subject Classification ID

Free semigroups, generators and relations, word problems (20M05) Commutative semigroups (20M14) Semigroups in automata theory, linguistics, etc. (20M35)

Review text

A monoid \(M\) is said to have the projection property if there exists a finite set \(Y\), a surjective morphism \(p\colon Y^*\to M\), and morphisms \(t_1,\ldots,t_n\colon Y^*\to Y^*\) such that \(\ker p=\ker t_1\cap\cdots\cap\ker t_n\). If, furthermore, \(\ker p\) is contained in the kernel of the projection onto the free commutative monoid over~\(Y\), then \(M\) is said to have the strong projection property. The author shows that strong equivalence of HDT0L sets in a monoid with the strong projection property and equivalence of D0L sets in a monoid with the projection property are both decidable. Although these results apply to the case of free partially commutative monoids, the arguments actually allow the author to prove a stronger version in this case.

Recommendations

• Morphic congruences and D0L languages
• scientific article; zbMATH DE number 1860695
• scientific article; zbMATH DE number 4045201
• On the periodicity of morphisms on free monoids
• The language equivalence problem for HD0L systems having D0L growths

This page was built for publication: On D0L and HDT0L sets in monoids

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1976433)