Decision problems on path-controlled grammars

DOI10.1142/S0129054107005364MaRDI QIDQ3401481zbMATHOpenAlexFDO

Authors Carlos Martín-Vide, Victor Mitrana

Publication date 29 January 2010

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

Full work available at URL https://doi.org/10.1142/s0129054107005364

zbMATH Keywords

recognitionclosure propertiespath-controlled grammar

Mathematics Subject Classification ID

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

Recommendations

• Parsing based on \(n\)-path tree-controlled grammars
• A DEFINITION OF PARIKH CONTROLLED CONTEXT-FREE GRAMMARS AND SOME PROPERTIES OF THEM
• Tree-controlled grammars with restrictions placed upon cuts and paths
• On grammars controlled by Parikh vectors
• Upper bounds on recognition of a hierarchy of non-context-free languages

Cites work

• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• A geometric hierarchy beyond context-free languages
• A geometric hierarchy of languages
• Characterizing derivation trees of context-free grammars through a generalization of finite automata theory
• Control sets on grammars
• Finite Automata Computing Real Functions
• Pumping lemmas for the control language hierarchy
• Recognition and parsing of context-free languages in time n3
• Relational phrase structure grammar and its tentative applications
• Upper bounds on recognition of a hierarchy of non-context-free languages

Cited in

(4)

• Parsing based on \(n\)-path tree-controlled grammars
• scientific article; zbMATH DE number 5722791 (Why is no real title available?)
• Decidability problems in grammar systems
• Selected Decision Problems for Square-Refinement Collage Grammars

This page was built for publication: Decision problems on path-controlled grammars

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