×

Normalformen im Turingmonoid. (Normal forms in the Turing monoid). (German) Zbl 0682.20045

A Turing monoid \(Q:=<0,1,R,L>\) is generated by elements 0,1,R,L subject to the relations: (i) \(01=0\); (ii) \(10=1\); (iii) \(00=0\); (iv) \(11=1\); (v) \(LR=\lambda\); (vi) \(RL=\lambda\); (vii) \(L^ iBR^ iA=AL^ iBR^ i\) (i\(\geq 1)\); (viii) \(R^ iBL^ iA=AR^ iBL^ i\) (A,B\(\in \{0,1\})\). Let M be the factor monoid (up to isomorphism) of the free monoid by the congruence generated by the relations (i)-(viii). Order words in the free monoid by length and inversely lexicographically within words of the same length, starting with \(0<1<R<L\). The normal form of a word is the smallest representative in its congruence class relative to this ordering. This paper is concerned with the computation of normal forms in the Turing monoid based on previous results based on four other papers of the (first) author. A BASIC program is given that computes normal forms, but no analysis of the complexity of the algorithm is given.
Reviewer: M.Garzon

MSC:

20M05 Free semigroups, generators and relations, word problems
20M35 Semigroups in automata theory, linguistics, etc.
68Q70 Algebraic theory of languages and automata
03D10 Turing machines and related notions
06F05 Ordered semigroups and monoids
20-04 Software, source code, etc. for problems pertaining to group theory
68Q05 Models of computation (Turing machines, etc.) (MSC2010)