The language complexity game

Eric Sven Ristad

This work elucidates the structure and complexity of human language in terms of the mathematics of information and computation. It strengthens Chomsky's early work on the mathematics of language, with the advantages of a better understanding of language and a more precise theory of structural complexity. Ristad argues that language is the process of constructing linguistic representations from the forms produced by other cognitive modules and that this process in NP-complete. This NP-completeness is defended with a phalanx of elegant and revealing proofs that rely only on the empirical facts of linguistic knowledge and on the uncontroverted assumption that these facts generalize in a reasonable manner. For this reason, these complexity results apply to all adequate linguistics theories and are the first to do so.

「Nielsen BookData」より


  • Part 1 Introduction: prior motivation
  • the language complexity game
  • summary of results - interpretation of human language, complexity thesis for human language, summary of technical results. Part 2 The anaphora problem: defining the problem
  • discussion
  • summary of anaphora results. Part 3 Anaphoric agreement: the standard agreement model, from graph coloring to anaphoric agreement, agreement reconsidered - theory of paradigm structure, paradigms for anaphoric elements
  • an upper bound on anaphoric uniqueness. Part 4 Referential dependency: the referential dependence model
  • local c-command configuration, control configuration, strong crossover configuration, invisible obviation configuration
  • from satisfiability to referential dependence. Part 5 Ellipsis: copy model of ellipsis
  • from QBF to anaphoric copying
  • ellipsis reconsidered
  • function-sharing model of ellipsis
  • an NP algorithm for anaphoric sharing. Part 6 Implications of the results: interpretation of human language - the study of language, the parsing of E-languages
  • the complexity thesis
  • the language complexity game - methodological suggestions, technical contributions to linguistics.

「Nielsen BookData」より


書名 The language complexity game
著作者等 Ristad, Eric Sven
Berwick, Robert C.
シリーズ名 The MIT Press series in artificial intelligence
出版元 MIT Press
刊行年月 c1993
ページ数 xv, 148 p.
大きさ 24 cm
ISBN 0262181479
NCID BA19718390
※クリックでCiNii Booksを表示
言語 英語
出版国 アメリカ合衆国