×

A complete characterization of termination of \(0^p1^q\to 1^r0^s\). (English) Zbl 0962.68086

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.

MSC:

68Q42 Grammars and rewriting systems
PDFBibTeX XMLCite
Full Text: DOI