Computation of Language: An Essay on Syntax, Semantics and Pragmatics in Natural Man-Machine Communication (Symbolic Computation / Artificial Intelligence)

This book analyzes the functioning of natural language in communication. The resulting system, called left-associative grammar (LA-grammar), incorporates the basic input-output conditions of speech as (i) a strictly time-linear (left-associative) derivation order, and (ii) a decidable, bidirectional mapping between the surface of sentences and their meaning. The new algorithm of LA-grammar computes possible continuations in contrast to most contemporary systems (e.g., phrase structure grammar), which are based on possible substitutions. The regular, context-free, and context-sensitive languages are reconstructed in LA-grammar, and questions of generative power, decidability, and computational complexity are explored in detail. It is proven that LA-grammar generates all - and only - the recursive languages, and that LA-grammar is more efficient computationally than corresponding substitution systems. The linguistic, mathematical, and computational analysis of natural (and formal) languages is followed by a philosophical discussion of communication. Topics are the theory of signs; the nature of reference; the role of ontology, truth, and the metalanguage; the nature of presuppositions and vagueness; the purpose of logic in meaning analysis; and the function of a semantically interpreted language in a speaking robot. An appendix illustrates the application of LA-grammar to natural language parsing with a large fragment of semantically interpreted English, implemented in LISP. As a comprehensive theory of grammar and the foundations of communication, this book is relevant for all applications of natural language processing, such as information retrieval, database interfaces, content analysis, database maintenance and up-scaling, dialog systems, machine translation, and foreign language teaching.