An insertion into the Chomsky hierarchy?

MaRDI QIDQ4941161zbMATH OpenFDO

Authors Robert McNaughton

Publication date 21 February 2002

zbMATH Keywords

formal languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• Growing grammars and length-reducing automata
• On growing context-sensitive languages
• Growing context-sensitive languages and Church-Rosser languages
• scientific article; zbMATH DE number 1064117
• On ``inherently context-sensitive languages -- an application of complexity cores

Cited in

(4)

• The context-splittable normal form for Church-Rosser language systems.
• Lower bound technique for length-reducing automata
• Probabilistic length-reducing two-pushdown automata
• A shorter proof that palindromes are not a Church-Rosser language, with extensions to almost-confluent and preperfect Thue systems

This page was built for publication: An insertion into the Chomsky hierarchy?

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