Bob Carpenter

in The Oxford Handbook of Computational Linguistics

Published in print January 2005 | ISBN: 9780199276349
Published online September 2012 | e-ISBN: 9780191743573 | DOI:

Series: Oxford Handbooks in Linguistics


Show Summary Details


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.  8400 words. 

Subjects: Computational Linguistics

Full text: subscription required

How to subscribe Recommend to my Librarian

Buy this work at Oxford University Press »

Users without a subscription are not able to see the full content. Please, subscribe or login to access all content.