Upper bounds on recognition of a hierarchy of non-context-free languages

DOI10.1016/0304-3975(92)90005-ZzbMath0761.68051OpenAlexW1992315343MaRDI QIDQ1193884

Sunil M. Shende, Michael A. Palis

Publication date: 27 September 1992

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(92)90005-z

zbMATH Keywords

computational linguisticscontrol grammarscontrol language hierarchygrammatical models for natural language

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42)

Related Items (6)

Pumping lemmas for the control language hierarchy ⋮ Linear time parsers for classes of non context free languages ⋮ Parallel parsing of tree adjoining grammars on the connection machine ⋮ An NC algorithm for recognizing tree adjoining languages ⋮ A geometric hierarchy beyond context-free languages ⋮ DECISION PROBLEMS ON PATH-CONTROLLED GRAMMARS

Cites Work

• Unnamed Item
• Unnamed Item
• Space-bounded hierarchies and probabilistic computations
• Tree-size bounded alternation
• On uniform circuit complexity
• A geometric hierarchy of languages
• The polynomial-time hierarchy
• A hierarchy between context-free and context-sensitive languages
• Alternation
• Description of developmental languages using recurrence systems
• Programmed Grammars and Classes of Formal Languages
• Studies in abstract families of languages
• Simple matrix languages
• Matrix grammars with a leftmost restriction

This page was built for publication: Upper bounds on recognition of a hierarchy of non-context-free languages