A tree-height hierarchy of context-free languages

DOI10.1142/S012905410700542XzbMATH Open1191.68402MaRDI QIDQ3401487FDOQ3401487

Authors: Klaus Reinhardt 

Publication date: 29 January 2010

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

Recommendations

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Time-bounded grammars and their languages
• Prefixes of infinite words and ambiguous context-free languages
• Substitution and bounded languages
• Bounded AFLs

Cited In (11)

• Title not available (Why is that?)
• Title not available (Why is that?)
• A context-free language for binary multinomial processing tree models
• A geometric hierarchy beyond context-free languages
• TIGHT BOUNDS FOR THE SPACE COMPLEXITY OF NONREGULAR LANGUAGE RECOGNITION BY REAL-TIME MACHINES
• On the synchronized derivation depth of context-free grammars
• 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)