Growing grammars and length-reducing automata

MaRDI QIDQ2882390zbMATH OpenFDO

Authors Tomasz Jurdziński

Publication date 4 May 2012

Published in Fundamenta Informaticae (Search for Journal in Brave)

Full work available at URL http://iospress.metapress.com/content/0rn627127t442007/fulltext.html

zbMATH Keywords

Chomsky hierarchygrowing grammarslength-reducing automata

Mathematics Subject Classification ID

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

Recommendations

• On growing context-sensitive languages
• scientific article; zbMATH DE number 3958759
• Membership for growing context-sensitive grammars is polynomial
• Growing context-sensitive languages and Church-Rosser languages
• The complexity of membership for deterministic growing context-sensitive grammars^∗

Cited in

(8)

• Lower bound technique for length-reducing automata
• scientific article; zbMATH DE number 6503311 (Why is no real title available?)
• scientific article; zbMATH DE number 3958759 (Why is no real title available?)
• scientific article; zbMATH DE number 1332661 (Why is no real title available?)
• scientific article; zbMATH DE number 1408346 (Why is no real title available?)
• On weak growing context-sensitive grammars
• On growing context-sensitive languages
• Membership for growing context-sensitive grammars is polynomial

This page was built for publication: Growing grammars and length-reducing automata

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