No article text was recorded for this version.
expressivity-efficiency tradeoff (expressivity-tractability tradeoff)
Version 2 of 2328 papers408 conceptsfrozen 2026-10-04
Papers in this version
- Blog: On the Complexity of Alignment Problems in Two Synchronous Grammar Formalisms
- Blog: The computational complexity of sentence derivation in functional unification grammar
- Blog: Combinatory Categorial Grammars: Generative Power and Relationship to Linear Context-Free Rewriting Systems
- Blog: Stochastic HPSG
- Blog: Formal Grammars for Linguistic Treebank Queries
- Blog: Computational Complexity and Lexical Functional Grammar
- Blog: From Strings to Trees to Strings to Trees ... (Abstract)
- Blog: Uniform Recognition for Acyclic Context-Sensitive Grammars is NP-complete
- Blog: Linear Inversion Transduction Grammar Alignments as a Second Translation Path
- Blog: Empirical Lower Bounds on Aligment Error Rates in Syntax-Based Machine Translation
- Blog: ProFIT: Prolog with Features, Inheritance and Templates
- Blog: Lean Formalisms, Linguistic Theory and Applications. Grammar Development in ALEP.
- Blog: The Complexity of Parsing With Extended Categorial Grammars
- Blog: Highly Constrained Unification Grammars
- Blog: The Use of Context-Sensitive Rules in Immediate Constituent Analysis
- Blog: LR(k)-Parsing of Coupled-Context-Free Grammars
- Blog: Compiling Language Models from a Linguistically Motivated Unification Grammar
- Blog: Converting Large On-Line Valency Dictionaries for NLP Applications: From Proton Descriptions to Metal Frames
- Blog: An Empirical Study on Rule Granularity and Unification Interleaving Toward an Efficient Unification-Based Parsing System
- Blog: Parsing for Semidirectional Lambek Grammar is NP-Complete
- Blog: Factoring Recursion and Dependencies: an Aspect of Tree Adjoining Grammars (Tag) and a Comparison of Some Formal Properties of Tags, GPSGs, Plgs, and LPGS
- Blog: Efficient Processing of Flexible Categorial Grammar
- Blog: Un analyseur LFG efficace : S XLFG
- Blog: Explicit Sentences and Syntactic Complexity
- Blog: Constraints on Strong Generative Power
- Blog: A Tractable Extension of Linear Indexed Grammars
- Blog: On the Weak Generative Capacity of Weighted Context-free Grammars
- Blog: Horn Extended Feature Structures: Fast Unification With Negation and Limited Disjunction
- Blog: Treatment of Long Distance Dependencies in LFG and TAG: Functional Uncertainty in LFG is a Corollary in TAG
- Blog: The New Grammar Formalisms - A Tutorial Survey (Abstract)
- Blog: The Use of Formal Language Models in the Typology of the Morphology of Amerindian Languages
- Blog: Balancing Clarity and Efficiency in Typed Feature Logic Through Delaying
- Blog: Multitext Grammars and Synchronous Parsers
- Blog: Efficient Algorithms for Recognizing Weighted Tree-Adjoining Languages
- Blog: Mildly Non-Projective Dependency Structures
- Blog: Reasons why I do not care grammar formalism
- Blog: The Complexity of Recognition of Linguistically Adequate Dependency Grammars
- Blog: DISCO-An HPSG-based NLP System and its Application for Appointment Scheduling Project Note
- Blog: Computational Complexity and Lexical Funtional Grammar
- Blog: On the Computational Complexity of Dominance Links in Grammatical Formalisms
- Blog: Composition of Translation Schemes with D-Trees
- Blog: Parsing to 1-Endpoint-Crossing, Pagenumber-2 Graphs
- Blog: Perspectives on Parsing Issues
- Blog: CLG(n): Constraint Logic Grammars
- Blog: Down-stream effects of tree-to-dependency conversions
- Blog: Processing English with a Generalized Phrase Structure Grammar
- Blog: Notes on LR Parser Design
- Blog: Capturing Linguistic Generalizations with Metarules in an Annotated Phrase-Structure Grammar
- Blog: Phrase Structure Grammars and Natural Languages
- Blog: Generative Power of CCGs with Generalized Type-Raised Categories
- Blog: Controlled Natural Languages for Knowledge Representation
- Blog: An alternative LR algorithm for TAGs
- Blog: Capturing CFLs with Tree Adjoining Grammars
- Blog: Kullback-Leibler Distance between Probabilistic Context-Free Grammars and Probabilistic Finite Automata
- Blog: Formal Constraints on Metarules
- Blog: Les Grammaires à Concaténation d'Intervalles (RCG) comme formalisme grammatical pour la linguistique
- Blog: A Description Language for Syntactically Annotated Corpora
- Blog: Proceedings of the 16th Meeting on the Mathematics of Language
- Blog: Lexical-Functional Grammar and Order-Free Semantic Composition
- Blog: A Corpus-based evaluation of syntactic locality in TAGs
Showing 60 of 328 papers.
History & citation
Current · Permanent link
Cite this direction
Latest version (a living page):
@misc{lacuna_expressivity_efficiency_tradeoff_express_33004849,
title = {expressivity-efficiency tradeoff (expressivity-tractability tradeoff)},
author = {{Lacuna}},
howpublished = {Lacuna research direction},
year = {2026},
url = {https://lacuna.tiptreesystems.com/direction/expressivity-efficiency-tradeoff-expressivity-tractability-tradeoff/rdr_330048492c064c5983ffb4e1228ccd3c},
note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}This exact version (version 2, frozen text):
@misc{lacuna_expressivity_efficiency_tradeoff_express_33004849_v2,
title = {expressivity-efficiency tradeoff (expressivity-tractability tradeoff)},
author = {{Lacuna}},
howpublished = {Lacuna research direction},
year = {2026},
url = {https://lacuna.tiptreesystems.com/direction/expressivity-efficiency-tradeoff-expressivity-tractability-tradeoff/rdr_330048492c064c5983ffb4e1228ccd3c/v/2},
note = {Version 2, frozen 2026-10-04. Accessed 2026-11-19},
}