A complete characterization of termination of 1q→ 1r 0s

H. Zantema, A. Geser

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

14 Citaten (Scopus)
2 Downloads (Pure)


We characterize termination of one-rule string rewriting systems of the form 0 p 1 q ¿ 1 r 0 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. Keywords: String rewriting, Term rewriting, Termination, Simple termination, Transformation ordering, Dummy elimination, Derivation length.
Originele taal-2Engels
Pagina's (van-tot)1-25
Aantal pagina's25
TijdschriftApplicable Algebra in Engineering, Communication and Computing
Nummer van het tijdschrift1
StatusGepubliceerd - 2000

Vingerafdruk Duik in de onderzoeksthema's van 'A complete characterization of termination of 1q→ 1r 0s'. Samen vormen ze een unieke vingerafdruk.

Citeer dit