Zantema, Hans; Geser, Alfons A complete characterization of termination of \(0^p1^q\to 1^r0^s\). (English) Zbl 0962.68086 Appl. Algebra Eng. Commun. Comput. 11, No. 1, 1-25 (2000). Summary: We characterize termination of one-rule string rewriting systems of the form \(0^p1^q\to 1^r0^s\) for every choice of positive integers \(p\), \(q\), \(r\), and \(s\). In doing so we introduce a termination proof method that applies to some hard examples. For the simply terminating cases, i.e. string rewriting systems that can be ordered by a division order, we give the precise complexity of derivation lengths. Cited in 7 Documents MSC: 68Q42 Grammars and rewriting systems Keywords:string rewriting systems PDFBibTeX XMLCite \textit{H. Zantema} and \textit{A. Geser}, Appl. Algebra Eng. Commun. Comput. 11, No. 1, 1--25 (2000; Zbl 0962.68086) Full Text: DOI