Uniform \textit{vs.} nonuniform membership for mildly context-sensitive languages: a brief survey

DOI10.3390/a9020032zbMath1461.68095OpenAlexW2350714487MaRDI QIDQ1736791

Martin Berglund, Henrik Björklund, Petter Ericson

Publication date: 26 March 2019

Published in: Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.3390/a9020032

zbMATH Keywords

formal languagesparsingparameterized complexitymildly context-sensitive languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Natural language processing (68T50) Parameterized complexity, tractability and kernelization (68Q27)

Related Items

Multiple context-free tree grammars: lexicalization and characterization

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Dependency structures and lexicalized grammars. An algebraic approach
• Tree transducers, L systems, and two-way machines
• The string generating power of context-free hypergraph grammars
• On multiple context-free grammars
• Trading independent for synchronized parallelism in finite copying parallel rewriting systems
• Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(\) and PSPACE analogues]
• Parametrized complexity theory.
• Parsing Beyond Context-Free Grammars
• Tree-Walking Automata
• The equivalence of four extensions of context-free grammars
• From Contextual Grammars to Range Concatenation Grammars
• Three models for the description of language
• Translations on a context free grammar