Unlocking potential with the best learning and research solutions

Look Inside Finite-State Techniques

Finite-State Techniques
Automata, Transducers and Bimachines

Part of Cambridge Tracts in Theoretical Computer Science

Authors:
Stoyan Mihov, Bulgarian Academy of Sciences
Klaus U. Schulz, Ludwig-Maximilians-Universität Munchen

Date Published: September 2019
availability: Available
format: Hardback
isbn: 9781108485418

Rate & review

Hardback

Add to wishlist

Other available formats:
eBook

Looking for an examination copy?

This title is not currently available for examination. However, if you are interested in the title for your course we can consider offering an examination copy. To register your interest please contact [email protected] providing details of the course you are teaching.

Description

Contents

Resources

Courses

About the Authors

Finite-state methods are the most efficient mechanisms for analysing textual and symbolic data, providing elegant solutions for an immense number of practical problems in computational linguistics and computer science. This book for graduate students and researchers gives a complete coverage of the field, starting from a conceptual introduction and building to advanced topics and applications. The central finite-state technologies are introduced with mathematical rigour, ranging from simple finite-state automata to transducers and bimachines as 'input-output' devices. Special attention is given to the rich possibilities of simplifying, transforming and combining finite-state devices. All algorithms presented are accompanied by full correctness proofs and executable source code in a new programming language, C(M), which focuses on transparency of steps and simplicity of code. Thus, by enabling readers to obtain a deep formal understanding of the subject and to put finite-state methods to real use, this book closes the gap between theory and practice.
- Goes beyond 'read-only' devices to cover the transformational devices that are of central interest in the field
- End-of-chapter exercises enable readers to implement complex finite-state based procedures for interesting tasks
- Provides executable source code in the new C(M) language, designed to focus on the high-level mathematical steps of a construction
Read more
Reviews & endorsements
‘… this volume is well written and very detailed. It is thus a nice reference for those results for the interested graduate or researcher …’ Andreas Maletti, ZB Math Reviews

Customer reviews

Not yet reviewed
Be the first to review

Log in to review

Review was not posted due to profanity
×

, create a review

(If you're not , sign out)

Please enter the right captcha value

Please enter a star rating.

Your review must be a minimum of 12 words.

How do you rate this item?

Reviews must contain at least 12 words about the product.

×

Product details
- Date Published: September 2019
- format: Hardback
- isbn: 9781108485418
- length: 314 pages
- dimensions: 234 x 158 x 21 mm
- weight: 0.57kg
- contains: 46 b/w illus. 3 tables 45 exercises
- availability: Available
Table of Contents
Part I. Formal Background:
1. Formal preliminaries
2. Monoidal finite-state automata
3. Classical finite-state automata and regular languages
4. Monoidal multi-tape automata and finite-state transducers
5. Deterministic transducers
6. Bimachines
Part II. From Theory to Practice:
7. The C(M) language
8. C(M) implementation of finite-state devices
9. The Aho–Corasick algorithm
10. The minimal deterministic finite-state automaton for a finite language
11. Constructing finite-state devices for text rewriting
Bibliography
Index.
Look Inside

General Resources

Resources

Find resources associated with this title

Back to resources home

Type	Name	Unlocked *	Format	Size

Showing of

This title is supported by one or more locked resources. Access to locked resources is granted exclusively by Cambridge University Press to instructors whose faculty status has been verified. To gain access to locked resources, instructors should sign in to or register for a Cambridge user account.

Please use locked resources responsibly and exercise your professional discretion when choosing how you share these materials with your students. Other instructors may wish to use locked resources for assessment purposes and their usefulness is undermined when the source files (for example, solution manuals or test banks) are shared online or via social networks.

Supplementary resources are subject to copyright. Instructors are permitted to view, print or download these resources for use in their teaching, but may not change them or use them for commercial gain.

If you are having problems accessing these resources please contact [email protected].

Authors
Stoyan Mihov, Bulgarian Academy of Sciences
Stoyan Mihov is Associate Professor at the Bulgarian Academy of Sciences (IICT) and a lecturer at Sofia University. He has published several efficient automata constructions and approximate search methods, which are widely used for natural language processing and information retrieval. Dr Mihov has led the development of multiple award-winning systems for language and speech processing.
Klaus U. Schulz, Ludwig-Maximilians-Universität Munchen
Klaus U. Schulz is Professor of Information and Language Processing at the Ludwig-Maximilians-Universität Munchen. He has published over 100 articles in distinct fields of computer science, with contributions in approximate search and transducer technology. He was head of many projects in text-correction and digital humanities, on both a national and European level.