6 citations · 6 across the 2 of their papers we have counts for
2 papers
cmp-lg1995
Assessing Complexity Results in Feature Theories
Marten Trautwein
In this paper, we assess the complexity results of formalisms that describe the feature theories used in computational linguistics. We show that from these complexity results no im…
cmp-lg1995★ 6 cited
A Note on the Complexity of Restricted Attribute-Value Grammars
Leen Torenvliet, Marten Trautwein
The recognition problem for attribute-value grammars (AVGs) was shown to be undecidable by Johnson in 1988. Therefore, the general form of AVGs is of no practical use. In this pape…