Paper Info
Title
Termination and derivational complexity of confluent one-rule string-rewriting systems
Abstract
It is not known whether the termination problem is decidable for one-rule string-rewriting systems, though the confluence of such systems is decidable by Wrathall (in: Word Equations and Related Topics, Lecture Notes in Computer Science, vol. 572, 1992, pp. 237–246). In this paper we develop techniques to attack the termination and complexity problems of confluent one-rule string-rewriting systems. With given such a system we associate another rewriting system over another alphabet. The behaviour of the two systems is closely related and the termination problem for the new system is sometimes easier than for the original system. We apply our method to systems of the special type {a p b q →t} , where t is an arbitrary word over {a,b} , and give a complete characterization for termination. We also give a complete analysis of the derivational complexity for the system {a p b q →b n a m } .
Year
DOI
Venue
2001
10.1016/S0304-3975(00)00367-4
Theor. Comput. Sci.
Keywords
DocType
Volume
Derivation complexity,derivational complexity,String rewriting system,confluent one-rule,Termination problem
Journal
262
Issue
ISSN
Citations 
1-2
Theoretical Computer Science
8
PageRank 
References 
Authors
0.73
1
3
Name
Order
Citations
PageRank
Yui Kobayashi1567.13
M. Katsura25810.49
Kayoko Shikishima-Tsuji3305.61