ENGLISH

Finite-State Techniques: Automata, Transducers and Bimachines

By Stoyan Mihov , Klaus U. Schulz

Book information

Publisher
Cambridge University Press
Year
2019
ISBN
9781108756945
Language
english
Format
PDF
Filesize
4 MB (3731809 bytes)
Series
Cambridge Tracts in Theoretical Computer Science 60
Pages
315\315
Time added
2020-01-04 07:49:12

Description

Finite-state techniques provide theoretically elegant and computationally effi- cient solutions for various (hard, non-trivial) problems in text and natural language processing. Due to its importance in many fundamental applications, the theory of finite-state automata and related finite-state machines has been extensively studied and its development still continues. Contents......Page 5 Preface......Page 9 PART I FORMAL BACKGROUND......Page 12 1.1 Sets, Functions and Relations......Page 14 1.2 Lifting Functions to Sets and Tuples......Page 19 1.3 Alphabets, Words and Languages......Page 21 1.4 Word Tuples, String Relations and String Functions......Page 24 1.5 The General Monoidal Perspective......Page 27 1.6 Summing Up......Page 31 1.7 Exercises for Chapter 1......Page 32 2.1 Basic Concept and Examples......Page 34 2.2 Closure Properties of Monoidal Finite-State Automata......Page 41 2.3 Monoidal Regular Languages and Monoidal Regular Expressions......Page 44 2.4 Equivalence Between Monoidal Regular Languages and Monoidal Automaton Languages......Page 46 2.5 Simplifying the Structure of Monoidal Finite-State Automata......Page 48 2.7 Exercises for Chapter 2......Page 52 3.1 Deterministic Finite-State Automata......Page 54 3.2 Determinization of Classical Finite-State Automata......Page 57 3.3 Additional Closure Properties for Classical Finite-State Automata......Page 59 3.4 Minimal Deterministic Finite-State Automata and the Myhill–Nerode Equivalence Relation......Page 61 3.5 Minimization of Deterministic Finite-State Automata......Page 68 3.6 Coloured Deterministic Finite-State Automata......Page 73 3.7 Pseudo-Determinization and Pseudo-Minimization of Monoidal Finite-State Automata......Page 78 3.9 Exercises for Chapter 3......Page 80 4.1 Monoidal Multi-Tape Automata......Page 83 4.2 Additional Closure Properties of Monoidal Multi-Tape Automata......Page 86 4.3 Classical Multi-Tape Automata and Letter Automata......Page 88 4.4 Monoidal Finite-State Transducers......Page 91 4.5 Classical Finite-State Transducers......Page 94 4.6 Deciding Functionality of Classical Finite-State Transducers......Page 96 4.7 Summing Up......Page 101 4.8 Exercises for Chapter 4......Page 102 5.1 Deterministic Transducers and Subsequential Transducers......Page 105 5.2 A Determinization Procedure for Functional Transducers with the Bounded Variation Property......Page 111 5.3 Deciding the Bounded Variation Property......Page 119 5.4 Minimal Subsequential Finite-State Transducers: Myhill–Nerode Relation for Subsequential Transducers......Page 126 5.5 Minimization of Subsequential Transducers......Page 134 5.6 Numerical Subsequential Transducers......Page 144 5.8 Bibliographic Notes......Page 146 5.9 Exercises for Chapter 5......Page 147 6.1 Basic Definitions......Page 149 6.2 Equivalence of Regular String Functions and Classical Bimachines......Page 156 6.3 Pseudo-Minimization of Monoidal Bimachines......Page 160 6.4 Direct Composition of Classical Bimachines......Page 162 6.6 Exercises for Chapter 6......Page 167 PART II FROM THEORY TO PRACTICE......Page 170 7 The C(M) language......Page 171 7.1 Basics and Simple Examples......Page 172 7.2 Types, Terms and Statements in C(M)......Page 179 8.1 C(M) Implementations for Automata Algorithms......Page 188 8.2 C(M) Programs for Classical Finite-State Transducers......Page 205 8.3 C(M) Programs for Deterministic Transducers......Page 222 8.4 C(M) Programs for Bimachines......Page 233 9.1 Formal Construction – First Version......Page 247 9.2 Linear Computation of the Aho–Corasick Automaton......Page 255 9.3 Space-Efficient Variant – Construction of the Aho–Corasick f-Automaton......Page 257 10.1 Formal Construction......Page 264 10.2 C(M) Implementation of the Construction – First Version......Page 269 10.3 Efficient Construction of the Minimal Dictionary Automaton......Page 273 10.4 Adapting the Language of Minimal Dictionary Automata......Page 276 10.5 The Minimal Subsequential Transducer for a Finite Two-Sided Dictionary......Page 281 11 Constructing Finite-State Devices for Text Rewriting......Page 290 11.1 Simple Text Rewriting Based on Regular Relations......Page 291 11.2 Using Deterministic Machines for Simple Text Rewriting......Page 293 11.3 Leftmost-Longest Match Text Rewriting......Page 299 11.4 Regular Relations for Leftmost-Longest Match Rewriting......Page 301 References......Page 309 Index......Page 313

Similar books

Session C11: Ancient Cultural Landscapes in South Europe – their Ecological Setting and Evolution, Session C22: Gardeners from South America, Session S04: Agro-Pastoralism and Early Metallurgy Sessions, Session WS29: The Idea of Enclosure in Recent Iberian Prehistory, Session C88: Rhytmes et causalites des dynamiques de l'anthropisation en Europe entre 6500 ET 500 BC: Hypotheses socio-culturelles et/ou climatiques: Proceedings of the XV UISPP World Congress (Lisbon 4-9 September 2006) / Actes du XV Congrès Mondial (Lisbonne 4-9 Septembre 2006) Vol.36

Session C11: Ancient Cultural Landscapes in South Europe – their Ecological Setting and Evolution, Session C22: Gardeners from South America, Session S04: Agro-Pastoralism and Early Metallurgy Sessions, Session WS29: The Idea of Enclosure in Recent Iberian Prehistory, Session C88: Rhytmes et causalites des dynamiques de l'anthropisation en Europe entre 6500 ET 500 BC: Hypotheses socio-culturelles et/ou climatiques: Proceedings of the XV UISPP World Congress (Lisbon 4-9 September 2006) / Actes du XV Congrès Mondial (Lisbonne 4-9 Septembre 2006) Vol.36

2010 · PDF

THE BRITISH ARMY IN INDIA: ITS PRESERVATION BY AN APPROPRIATE CLOTHING, HOUSING, LOCATING, RECREATIVE EMPLOYMENT, AND HOPEFUL ENCOURAGEMENT OF THE TROOPS. with AN APPENDIX ON INDIA : THE CLIMATE OP ITS HILLS ; THE DEVELOPMENT OF ITS RESODRCBS, INDUSTRY, AND ARTS ; THE ADMINISTRATION OF JUSTICE ; THE BLACK ACT ; THE PROGRESS OF CHRISTIANITY ; THE TRAFFIC IN OPIUM ; THE VALUE OF INDIA ; PERMANENT CAUSES OF DISAFFECTION, AND OF THE RECENT REBELLION ; THE TRADITIONARY POLICY; MISGOVERNMENT BY NATIVE RULERS ; ANNEXATIONS OF THEIR TERRITORY, ETC.

THE BRITISH ARMY IN INDIA: ITS PRESERVATION BY AN APPROPRIATE CLOTHING, HOUSING, LOCATING, RECREATIVE EMPLOYMENT, AND HOPEFUL ENCOURAGEMENT OF THE TROOPS. with AN APPENDIX ON INDIA : THE CLIMATE OP ITS HILLS ; THE DEVELOPMENT OF ITS RESODRCBS, INDUSTRY, AND ARTS ; THE ADMINISTRATION OF JUSTICE ; THE BLACK ACT ; THE PROGRESS OF CHRISTIANITY ; THE TRAFFIC IN OPIUM ; THE VALUE OF INDIA ; PERMANENT CAUSES OF DISAFFECTION, AND OF THE RECENT REBELLION ; THE TRADITIONARY POLICY; MISGOVERNMENT BY NATIVE RULERS ; ANNEXATIONS OF THEIR TERRITORY, ETC.

1858 · PDF

Idries Shah 27 Books Collection : A Perfumed Scorpion, A Veiled Gazelle, Caravan of Dreams, Darkest England, Destination Mecca, Evenings with Idries Shah, Knowing How to Know, Learning How to Learn, Letters and Lectures of Idries Shah, Neglected aspects of Sufi study, Observations, Oriental Magic, Reflections, Seeker after Truth, Special Illumination, Special Problems in the study of Sufi ideas, Sufi thought and action, Tales of the Dervishes, The Dermis Probe, The Elephant in the Dark, The Englishman Handbook, Idries Shah Antology, The Magic Monastery, The natives are restless, wisdom of the Idiots PDF.

Idries Shah 27 Books Collection : A Perfumed Scorpion, A Veiled Gazelle, Caravan of Dreams, Darkest England, Destination Mecca, Evenings with Idries Shah, Knowing How to Know, Learning How to Learn, Letters and Lectures of Idries Shah, Neglected aspects of Sufi study, Observations, Oriental Magic, Reflections, Seeker after Truth, Special Illumination, Special Problems in the study of Sufi ideas, Sufi thought and action, Tales of the Dervishes, The Dermis Probe, The Elephant in the Dark, The Englishman Handbook, Idries Shah Antology, The Magic Monastery, The natives are restless, wisdom of the Idiots PDF.

2022 · PDF

The travels of Capts. Lewis and Clarke from St. Louis, by way of the Missouri and Columbia rivers, to the Pacific ocean; performed in the years 1804, 1805 & 1806, by order of the government of the United States. Containing delineations of the manners, customs, religion, &c. of the Indians, comp. from various authentic sources, and original documents, and a summary of the Statistical view of the Indian nations, from the official communication of Meriwether Lewis. Illustrated with a map of the country, inhabited by the western tribes of Indians

The travels of Capts. Lewis and Clarke from St. Louis, by way of the Missouri and Columbia rivers, to the Pacific ocean; performed in the years 1804, 1805 & 1806, by order of the government of the United States. Containing delineations of the manners, customs, religion, &c. of the Indians, comp. from various authentic sources, and original documents, and a summary of the Statistical view of the Indian nations, from the official communication of Meriwether Lewis. Illustrated with a map of the country, inhabited by the western tribes of Indians

1809 · PDF

Professional Linux kernel architecture ''Wrox programmer to programmer''--Cover. - ''What you are reading right now is the result of an evolution over more than seven years: After two years of writing, the first edition was published in German by Carl Hanser Verlag in 2003. It then described kernel 2.6.0. The test was used as a basis for the low-level design documentation for the EAL4+ security evaluation of Red Hat Enterprise Linux 5, requiring to update it to kernel 2.6.18 (if the EAL acronym does not mean anything to you, then Wikipedia is once more your friend). Hewlett-Packard sponsored the translation into English and has, thankfully, granted the rights to publish the result. Updates to kernel 2.6.24 were then performed specifically for this book''--P. ix

Professional Linux kernel architecture ''Wrox programmer to programmer''--Cover. - ''What you are reading right now is the result of an evolution over more than seven years: After two years of writing, the first edition was published in German by Carl Hanser Verlag in 2003. It then described kernel 2.6.0. The test was used as a basis for the low-level design documentation for the EAL4+ security evaluation of Red Hat Enterprise Linux 5, requiring to update it to kernel 2.6.18 (if the EAL acronym does not mean anything to you, then Wikipedia is once more your friend). Hewlett-Packard sponsored the translation into English and has, thankfully, granted the rights to publish the result. Updates to kernel 2.6.24 were then performed specifically for this book''--P. ix

2008 · PDF