Decision problems on path-controlled grammars

DOI10.1142/S0129054107005364zbMATH Open1186.68238OpenAlexW1999807683MaRDI QIDQ3401481FDOQ3401481

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

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

zbMATH Keywords

recognitionclosure propertiespath-controlled grammar

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (4)

• Selected Decision Problems for Square-Refinement Collage Grammars
• Title not available (Why is that?)
• Parsing based on \(n\)-path tree-controlled grammars
• Decidability problems in grammar systems

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)