Characterizing languages by normalization and termination in string rewriting (extended abstract)

DOI10.1007/978-3-642-31653-1_41MaRDI QIDQ3167518zbMATH OpenOpenAlexFDO

Authors Jeroen Ketema, Jakob Grue Simonsen

Publication date 2 November 2012

Published in Developments in Language Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-31653-1_41

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Grammars and rewriting systems (68Q42) Formal languages and automata (68Q45)

Recommendations

• A complete characterization of termination of 0p 1q→1r 0s
• On normalizing, non-terminating one-rule string rewriting systems
• Some undecidability results concerning the property of preserving regularity
• A complete characterization of termination of \(0^p1^q\to 1^r0^s\)
• Termination proofs for string rewriting systems via inverse match-bounds

Cited in

(4)

• 1-normal DRA for insertion languages
• Characterizations of re languages starting from internal contextual languages^∗
• A complete characterization of termination of 0p 1q→1r 0s
• scientific article; zbMATH DE number 7324347 (Why is no real title available?)

This page was built for publication: Characterizing languages by normalization and termination in string rewriting (extended abstract)

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