Article

Complexity

Bob Carpenter

in The Oxford Handbook of Computational Linguistics

Published in print January 2005 | ISBN: 9780199276349
Published online September 2012 | | DOI: http://dx.doi.org/10.1093/oxfordhb/9780199276349.013.0009

Series: Oxford Handbooks in Linguistics

Complexity

Preview

This article deals with the study of asymptotic complexity of problems and algorithms. It introduces the mathematics of function growth, and then analyses examples of some standard problems and algorithms in natural language processing. It deals with the crucially important aspect of complexity analysis which derives from the notions of benchmarking and profiling. It considers discrete performance measures that map strings into integers, and such functions can be used to measure many aspects of real world or theoretical performance. It begins with a series of complexity analyses of problems involving regular languages, an important class of languages, which can be defined in terms of simple pattern matching via regular expressions or in terms of finite-state automata recognition. The analysis illustrates important aspects of determinism, non-determinism, and compilation. The article concludes with some reflections on the utility of complexity analysis important both to understanding language complexity and to building practical natural language processing systems.

Keywords: asymptotic complexity; algorithms; complexity analysis; processing systems; benchmarking; profiling

Article.  8105 words. 

Subjects: Linguistics ; Computational Linguistics

Full text: subscription required

How to subscribeRecommend to my Librarian

Buy this work at Oxford University Press »