Simple Search

Query:

Enter a query and click »Search«...

Format:

Display: entries per page entries

Zbl 1126.20039
Cain, Alan J.
Cancellativity is undecidable for automatic semigroups. (English)
[J] Q. J. Math. 57, No. 3, 285-295 (2006). ISSN 0033-5606; ISSN 1464-3847

Automatic semigroups were introduced by {\it C. M.~Campbell, E. F. Robertson, N. Ruškuc}, and {\it R. M. Thomas}, [in Theor. Comput. Sci. 250, No. 1-2, 365-391 (2001; Zbl 0987.20033)]. The author proves in the present paper the following algorithmic undecidability results: (1) It is undecidable whether a semigroup $S$ is left-cancellative given an automatic structure for $S$. (2) It is undecidable whether a semigroup $S$ is cancellative given an automatic structure for $S$.\par The undecidability of these problems is based on the undecidability of the modified Post correspondence problem (MPCP). Given an instance of MPCP, the author defines a semigroup $S$ with a finite presentation $\text{Sg}\langle A\mid\cal R\rangle$ such that (1) the semigroup $S$ is automatic; (2) every generator in $A-\{O\}$ is left-cancellable (where $A$ is the generator alphabet and $O\in A$); (3) The generator $\overline O$ represented by $O$ is left-cancellable if and only if the instance of the MPCP has no solution.\par Moreover, at the end the author shows that $S$ is always right cancellative, and so the undecidability claim follows also in the case of cancellation.
[Tero J. Harju (Turku)]

MSC 2000:: *20M05 Free semigroups
68Q45 Formal languages
20M35 Semigroups in automata theory, linguistics, etc.

Keywords: automatic semigroups; cancellative semigroups; Post correspondence problem; undecidability; string rewriting systems

Citations: Zbl 0987.20033

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article Journal Journal

	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.
	Elementary number theory. Primes, congruences, and secrets.

Simple Search

Zentralblatt MATH Berlin [Germany]