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

DOI10.1007/S10849-011-9133-1MaRDI QIDQ438591zbMATH OpenOpenAlexFDO

Authors 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

NP-completedominance linkslexicalizationMCTAGmildly context-sensitivescramblingtree adjoining grammar

Mathematics Subject Classification ID

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

Recommendations

• Minimalist Grammars with Unbounded Scrambling and Nondiscriminating Barriers Are NP-Hard
• Tree-local multicomponent tree-adjoining grammars with shared nodes
• On the Relation between Multicomponent Tree Adjoining Grammars with Tree Tuples (TT-MCTAG) and Range Concatenation Grammars (RCG)
• scientific article; zbMATH DE number 1941335
• NP-completeness of grammars based upon products of free pregroups

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 475427 (Why is no real title available?)
• scientific article; zbMATH DE number 569754 (Why is no real title available?)
• Factoring predicate argument and scope semantics: underspecified semantics with LTAG
• Membership for growing context-sensitive grammars is polynomial
• Phrase structure composition and syntactic dependencies
• Scattered context grammars
• Tree adjunct grammars
• Tree-local multicomponent tree-adjoining grammars with shared nodes

Cited in

(3)

• Computational complexity of syntactic agreement and lexical ambiguity
• Tree-local multicomponent tree-adjoining grammars with shared nodes
• Minimalist Grammars with Unbounded Scrambling and Nondiscriminating Barriers Are NP-Hard

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

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