Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

 
 

 

Elements of finite order for finite monadic Church-Rosser Thue systems


Author: Friedrich Otto
Journal: Trans. Amer. Math. Soc. 291 (1985), 629-637
MSC: Primary 03D03; Secondary 03D40, 20F10, 68Q45
DOI: https://doi.org/10.1090/S0002-9947-1985-0800255-1
MathSciNet review: 800255
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: A Thue system $ T$ over $ \Sigma$ is said to allow nontrivial elements of finite order, if there exist a word $ u \in {\Sigma ^ \ast }$ and integers $ n \ge 0$ and $ k \ge 1$ such that $ u \nleftrightarrow \,_T^ \ast \lambda $ and $ {u^{n + k}} \leftrightarrow \,_T^ \ast {u^n}$. Here the following decision problem is shown to be decidable:

Instance. A finite, monadic, Church-Rosser Thue system $ T$ over $ \Sigma$.

Question. Does $ T$ allow nontrivial elements of finite order?

By a result of Muller and Schupp this implies in particular that given a finite monadic Church-Rosser Thue system $ T$ it is decidable whether the monoid presented by $ T$ is a free group or not.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC: 03D03, 03D40, 20F10, 68Q45

Retrieve articles in all journals with MSC: 03D03, 03D40, 20F10, 68Q45


Additional Information

DOI: https://doi.org/10.1090/S0002-9947-1985-0800255-1
Keywords: Thue system, Church-Rosser property, monadic system, element of finite order, Markov property, presentations of free groups, decision procedure
Article copyright: © Copyright 1985 American Mathematical Society

American Mathematical Society