A tree-height hierarchy of context-free languages

DOI10.1142/S012905410700542XMaRDI QIDQ3401487zbMATH OpenFDO

Authors Klaus Reinhardt

Publication date 29 January 2010

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

zbMATH Keywords

context-free languagestree heightparallel derivationpush-down complexity

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Algebraic theory of languages and automata (68Q70)

Recommendations

• Publication:4934352
• Publication:3200545
• scientific article; zbMATH DE number 3850491
• Two complexity measures for context-free languages
• scientific article; zbMATH DE number 1759455

Cites work

• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 43583 (Why is no real title available?)
• scientific article; zbMATH DE number 3293666 (Why is no real title available?)
• Bounded AFLs
• Prefixes of infinite words and ambiguous context-free languages
• Substitution and bounded languages
• Time-bounded grammars and their languages

Cited in

(11)

• scientific article; zbMATH DE number 1390085 (Why is no real title available?)
• scientific article; zbMATH DE number 4176462 (Why is no real title available?)
• A context-free language for binary multinomial processing tree models
• A geometric hierarchy beyond context-free languages
• On the synchronized derivation depth of context-free grammars
• TIGHT BOUNDS FOR THE SPACE COMPLEXITY OF NONREGULAR LANGUAGE RECOGNITION BY REAL-TIME MACHINES
• Binary Tree Code Words as Context-Free Languages
• New results on the minimum amount of useful space
• Height functions and linear languages
• The Cantor-Bendixson analysis of finite trees
• On context-free trees

This page was built for publication: A tree-height hierarchy of context-free languages

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