Paper Info
Title
Grammar Efficiency and Complexity
Abstract
An earlier method for measuring grammar efficiency is revisited in this paper. The method is based on a finite analytic grammar which has word order as its dominant component. The grammar description uses the apparatus of set theory, whereas the measure of its efficiency requires some combinatorics and algebra tools, and is related to an optimization problem defining maximally efficient grammars. This results in a numerical representation of the grammatical structure. A simpler and improved formula for measuring grammar efficiency is proposed, enabling a wider and easier applicability of the formula. This is illustrated by many examples, both abstract and those related to natural languages. It is also shown that the reciprocal of grammar efficiency can be used to measure grammar complexity, which indicates how complex a grammar is, relative to the linguistic information it conveys.
Year
DOI
Venue
2003
10.1023/A:1026189411761
Grammars
Keywords
Field
DocType
set theory,optimization problem,word order,natural language
Attribute grammar,Regular tree grammar,Operator-precedence grammar,Emergent grammar,Affix grammar,Artificial intelligence,Natural language processing,Regular grammar,Generative grammar,Mathematics,Mildly context-sensitive grammar formalism
Journal
Volume
Issue
ISSN
6
2
1572-848X
Citations 
PageRank 
References 
0
0.34
1
Authors
1
Name
Order
Citations
PageRank
Relja Vulanovic13513.39