The context-splittable normal form for Church-Rosser language systems.

DOI10.1016/S0890-5401(03)00035-XMaRDI QIDQ1401938zbMATH OpenFDO

Authors Jens R. Woinowski

Publication date 19 August 2003

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0890-5401(03)00035-X

zbMATH Keywords

Church-Rosser languagesConfluenceGrowing context-sensitive languagesString-rewriting

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42) Formal languages and automata (68Q45)

Recommendations

• scientific article; zbMATH DE number 1722715
• When Church-Rosser becomes context free
• Church-Rosser controlled rewriting systems and equivalence problems for deterministic context-free languages
• Church-Rosser systems with respect to formal languages
• scientific article; zbMATH DE number 2050944

Cites work

• An \(O(| T| ^ 3)\) algorithm for testing the Church-Rosser property of Thue systems
• Church-Rosser Thue systems and formal languages
• Confluent and Other Types of Thue Systems
• Growing context-sensitive languages and Church-Rosser languages
• scientific article; zbMATH DE number 1722715 (Why is no real title available?)
• scientific article; zbMATH DE number 1189300 (Why is no real title available?)
• scientific article; zbMATH DE number 42096 (Why is no real title available?)
• scientific article; zbMATH DE number 3639163 (Why is no real title available?)
• scientific article; zbMATH DE number 2087223 (Why is no real title available?)
• scientific article; zbMATH DE number 789389 (Why is no real title available?)
• scientific article; zbMATH DE number 1408346 (Why is no real title available?)
• McNaughton families of languages.
• Membership for growing context-sensitive grammars is polynomial
• On certain formal properties of grammars

Cited in

(4)

• The Church-Rosser languages are the deterministic variants of the growing context-sensitive languages
• Lower bound technique for length-reducing automata
• scientific article; zbMATH DE number 1722715 (Why is no real title available?)
• Computing by observing: simple systems and simple observers

This page was built for publication: The context-splittable normal form for Church-Rosser language systems.

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