Abstract and Keywords
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.
Access to the complete content on Oxford Handbooks Online requires a subscription or purchase. Public users are able to search the site and view the abstracts and keywords for each book and chapter without a subscription.
If you have purchased a print title that contains an access token, please see the token for information about how to register your code.