ONE-RULE SEMI-THUE SYSTEMS WITH LOOPS OF LENGTH-ONE, LENGTH-2 OR LENGTH-3

Authors
KURTH W
Citation
W. Kurth, ONE-RULE SEMI-THUE SYSTEMS WITH LOOPS OF LENGTH-ONE, LENGTH-2 OR LENGTH-3, Informatique theorique et applications, 30(5), 1996, pp. 415-429
Citations number
14
Categorie Soggetti
Computer Sciences","Computer Science Information Systems
Journal title
Informatique theorique et applications → ACNP
ISSN journal
09883754
Volume
30
Issue
5
Year of publication
1996
Pages
415 - 429
Database
ISI
SICI code
0988-3754(1996)30:5<415:OSSWLO>2.0.ZU;2-9
Abstract
A loop of a semi-Thue system is a reduction chain where the start word reappears as a factor of the obtained word after a finite number of r eduction steps. A rewriting system admitting a loop is clearly nonterm inating. The semi-Thue systems consisting of only one rule which admit loops of length 1, 2 or 3 are characterized. Length-1-loops are trivi al. 2-loops turn out to have a unique structure, whereas one-rule syst ems admitting a 3-loop (but no 2-loop) can belong to three structurall y different types.