On normalizing, non-terminating one-rule string rewriting systems

DOI10.1016/S0304-3975(00)00167-5MaRDI QIDQ1575660zbMATH OpenFDO

Authors Alfons Geser

Publication date 21 August 2000

Published in Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

semi-Thue systemterminatingstring rewriting systeminnermost terminatingnormalizingone-rulerightmost terminatingsingle-rule

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42)

Recommendations

• On termination of confluent one-rule string-rewriting systems
• A complete characterization of termination of 0p 1q→1r 0s
• A complete characterization of termination of \(0^p1^q\to 1^r0^s\)
• Termination and derivational complexity of confluent one-rule string-rewriting systems

Cites work

• scientific article; zbMATH DE number 49211 (Why is no real title available?)
• scientific article; zbMATH DE number 108365 (Why is no real title available?)
• Calcul de longueurs de chaînes de réécriture dans le monoïde libre
• Das Identitätsproblem für Gruppen mit einer definierenden Relation
• Non-Looping String Rewriting
• On confluence of one-rule trace-rewriting systems
• On termination of confluent one-rule string-rewriting systems
• Termination of term rewriting using dependency pairs

Cited in

(5)

• A confluent rewriting system having no computable, one-step, normalizing strategy
• Termination proofs for string rewriting systems via inverse match-bounds
• Characterizing languages by normalization and termination in string rewriting (extended abstract)
• scientific article; zbMATH DE number 2043544 (Why is no real title available?)
• Adding constants to string rewriting

This page was built for publication: On normalizing, non-terminating one-rule string rewriting systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1575660)