A note on a special one-rule semi-Thue system
Copyright policy )A note on a special one-rule semi-Thue system
The quotient monoid \(G_ 1=[a,b;abba=\lambda]\) is characterized as a nontrivial semidirect product of \({\mathbb{Z}}\) by \({\mathbb{Z}}\) which is not a context-free group. The presentation of this monoid, the Thue system \(S_ 1=\{(abba,\lambda)\}\), is shown to have no equivalent finite complete (i.e. uniquely terminating) semi-Thue system on the same alphabet that generates the same congruence. This work corrects the author's work in Lect. Notes Comput. Sci. 176, 80-95 (1984; Zbl 0553.03025).
- Universität Hamburg Germany
complete rewriting system, Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science, Church-Rosser property, Thue system, Thue and Post systems, etc., Symbolic computation and algebraic computation, Word problems, etc. in computability and recursion theory, quotient monoid
complete rewriting system, Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science, Church-Rosser property, Thue system, Thue and Post systems, etc., Symbolic computation and algebraic computation, Word problems, etc. in computability and recursion theory, quotient monoid
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).25 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Top 10% impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Top 10%
Citations provided by BIP!Popularity provided by BIP!