Lexicalized non-local MCTAG with dominance links is NP-complete

DOI10.1007/S10849-011-9133-1zbMath1255.68087OpenAlexW2082514075MaRDI QIDQ438591

Lucas Champollion

Publication date: 31 July 2012

Published in: Journal of Logic, Language and Information (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10849-011-9133-1

zbMATH Keywords

tree adjoining grammarNP-completedominance linkslexicalizationMCTAGmildly context-sensitivescrambling

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (1)

Minimalist Grammars with Unbounded Scrambling and Nondiscriminating Barriers Are NP-Hard

Cites Work

• Membership for growing context-sensitive grammars is polynomial
• Tree adjunct grammars
• Factoring predicate argument and scope semantics: underspecified semantics with LTAG
• Scattered context grammars
• Tree-Local Multicomponent Tree-Adjoining Grammars with Shared Nodes
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Lexicalized non-local MCTAG with dominance links is NP-complete