Algorithms for computational biology : 8th international conference, AlCoB 2021 Missoula, MT, USA, June 7-11, 2021 proceedings / / Carlos Martin-Vide, Miguel A. Vega-Rodriguez, Travis Wheeler, editors |
Pubbl/distr/stampa | Cham, Switzerland : , : Springer, , [2021] |
Descrizione fisica | 1 online resource (177 pages) |
Disciplina | 570.285 |
Collana | Lecture Notes in Computer Science |
Soggetto topico |
Computational biology
Algorithms |
ISBN | 3-030-74432-9 |
Formato | Materiale a stampa |
Livello bibliografico | Monografia |
Lingua di pubblicazione | eng |
Nota di contenuto |
Intro -- Preface -- Organization -- Contents -- Biological Dynamical Systems and Other Biological Processes -- Learning Molecular Classes from Small Numbers of Positive Examples Using Graph Grammars -- 1 Introduction -- 2 Related Work -- 3 Learning the Graph Grammar -- 3.1 Learning a Graph-Grammar -- 4 Experiments -- 4.1 Comparison to Machine Learning on SMILES -- 4.2 Comparison to Standard Machine Learning Using Graph-Grammar Rules as Features -- 5 Conclusion -- References -- Can We Replace Reads by Numeric Signatures? Lyndon Fingerprints as Representations of Sequencing Reads for Machine Learning -- 1 Introduction -- 2 Lyndon Factorizations and Overlapping Reads -- 3 Probabilistic Behaviour of Fingerprints -- 4 Methodology and Experiments -- 4.1 Fingerprint-Based Approach -- 4.2 k-Finger-Based Approach -- 5 Discussion -- References -- Exploiting Variable Sparsity in Computing Equilibria of Biological Dynamical Systems by Triangular Decomposition -- 1 Introduction -- 2 Preliminaries -- 2.1 Autonomous Biological Dynamical Systems and Their Equilibria -- 2.2 Polynomial Sets and Associated Graphs -- 2.3 Triangular Sets and Sparse Triangular Decomposition -- 3 Variable Sparsity in Biological Dynamical Systems -- 3.1 Original Variable Sparsity -- 3.2 Variable Sparsity After Chordal Completion -- 4 Sparse Triangular Decomposition for Computing Equilibria -- 5 Concluding Remarks -- References -- A Recovery Algorithm and Pooling Designs for One-Stage Noisy Group Testing Under the Probabilistic Framework -- 1 Introduction -- 2 Methods -- 2.1 Noisy Group Testing Under the Probabilistic Framework -- 2.2 A Group Testing Protocol -- 2.3 Recovery Algorithm -- 3 Results -- 3.1 Performance of the Recovery Algorithm -- 3.2 Pooling Matrices -- 4 Discussion -- References -- Phylogenetics -- Novel Phylogenetic Network Distances Based on Cherry Picking.
1 Introduction -- 2 Preliminaries -- 2.1 Network Definitions -- 2.2 Cherry Operations -- 3 Distances Based on Cherry-Picking Sequences -- 4 Computing the Tail Distance Between Two Trees -- 4.1 Computing an LR-MAST -- 5 NP-hardness of dtail Between a Tree and a Network -- 6 Discussion and Future Work -- 1 Proof of Lemma 1 (Page 6) -- 2 Proof of Theorems in Sect.3 (Theorem 2 Page 7, Theroem 3 Page 8, Theorem 4 Page 8, Theorem 5 Page 8) -- 3 Proof of Lemma 6, 7 and Theorem 8 (Page 9) -- 4 LR-MAST Algorithm, and Associated Theorem (Page 9) -- 5 Proof of Theorem 10 (Page 12) and Theorem 11 (Page 12) -- References -- Best Match Graphs with Binary Trees -- 1 Introduction -- 2 Best Match Graphs -- 3 Binary Trees Explaining a BMG in Near Cubic Time -- 4 The Binary-Refinable Tree of a BMG -- 5 Simulation Results -- 6 Concluding Remarks -- References -- Scalable and Accurate Phylogenetic Placement Using pplacer-XR -- 1 Introduction -- 2 pplacer-XR -- 3 Experimental Study Design -- 4 Results -- 4.1 Query Placement Accuracy -- 4.2 Time Analysis -- 5 Conclusions -- References -- Comparing Methods for Species Tree Estimation with Gene Duplication and Loss -- 1 Introduction -- 2 Experimental Design -- 3 Results -- 4 Discussion and Conclusion -- References -- Sequence Alignment and Genome Rearrangement -- Reversal Distance on Genomes with Different Gene Content and Intergenic Regions Information -- 1 Introduction -- 2 Background -- 3 Labeled Intergenic Breakpoint Graph -- 4 3-Approximation Algorithm -- 5 Conclusions -- References -- Reversals Distance Considering Flexible Intergenic Regions Sizes -- 1 Introduction -- 2 Definitions -- 2.1 Flexible Weighted Cycle Graph -- 3 Results -- 3.1 Lower Bound -- 3.2 Approximation Algorithm -- 4 Conclusion -- References -- Improved DNA-versus-Protein Homology Search for Protein Fossils -- 1 Introduction -- 2 Methods. 2.1 Alignment Elements -- 2.2 Scoring Scheme -- 2.3 Finding a Maximum-Score Local Alignment -- 2.4 Probability Model -- 2.5 Sum over All Alignments Passing Through (i,j) -- 2.6 Significance Calculation -- 2.7 Seed-and-Extend Heuristic -- 2.8 Fitting Substitution and Gap Parameters to Sequence Data -- 3 Results -- 3.1 Software -- 3.2 Parameter Fitting -- 3.3 Significance Calculation and Simple Sequences -- 3.4 Comparison to Blastx -- 3.5 Discovery of Missing TE Orders in the Human Genome -- 4 Discussion -- References -- The Maximum Weight Trace Alignment Merging Problem -- 1 Introduction -- 2 Maximum Weight Trace Alignment Merging -- 3 Graph Clustering Merger (GCM) -- 4 Experimental Study -- 5 Results -- 6 Conclusions -- References -- Author Index. |
Record Nr. | UNISA-996464503403316 |
Cham, Switzerland : , : Springer, , [2021] | ||
Materiale a stampa | ||
Lo trovi qui: Univ. di Salerno | ||
|
Algorithms for computational biology : 8th international conference, AlCoB 2021 Missoula, MT, USA, June 7-11, 2021 proceedings / / Carlos Martin-Vide, Miguel A. Vega-Rodriguez, Travis Wheeler, editors |
Pubbl/distr/stampa | Cham, Switzerland : , : Springer, , [2021] |
Descrizione fisica | 1 online resource (177 pages) |
Disciplina | 570.285 |
Collana | Lecture Notes in Computer Science |
Soggetto topico |
Computational biology
Algorithms |
ISBN | 3-030-74432-9 |
Formato | Materiale a stampa |
Livello bibliografico | Monografia |
Lingua di pubblicazione | eng |
Nota di contenuto |
Intro -- Preface -- Organization -- Contents -- Biological Dynamical Systems and Other Biological Processes -- Learning Molecular Classes from Small Numbers of Positive Examples Using Graph Grammars -- 1 Introduction -- 2 Related Work -- 3 Learning the Graph Grammar -- 3.1 Learning a Graph-Grammar -- 4 Experiments -- 4.1 Comparison to Machine Learning on SMILES -- 4.2 Comparison to Standard Machine Learning Using Graph-Grammar Rules as Features -- 5 Conclusion -- References -- Can We Replace Reads by Numeric Signatures? Lyndon Fingerprints as Representations of Sequencing Reads for Machine Learning -- 1 Introduction -- 2 Lyndon Factorizations and Overlapping Reads -- 3 Probabilistic Behaviour of Fingerprints -- 4 Methodology and Experiments -- 4.1 Fingerprint-Based Approach -- 4.2 k-Finger-Based Approach -- 5 Discussion -- References -- Exploiting Variable Sparsity in Computing Equilibria of Biological Dynamical Systems by Triangular Decomposition -- 1 Introduction -- 2 Preliminaries -- 2.1 Autonomous Biological Dynamical Systems and Their Equilibria -- 2.2 Polynomial Sets and Associated Graphs -- 2.3 Triangular Sets and Sparse Triangular Decomposition -- 3 Variable Sparsity in Biological Dynamical Systems -- 3.1 Original Variable Sparsity -- 3.2 Variable Sparsity After Chordal Completion -- 4 Sparse Triangular Decomposition for Computing Equilibria -- 5 Concluding Remarks -- References -- A Recovery Algorithm and Pooling Designs for One-Stage Noisy Group Testing Under the Probabilistic Framework -- 1 Introduction -- 2 Methods -- 2.1 Noisy Group Testing Under the Probabilistic Framework -- 2.2 A Group Testing Protocol -- 2.3 Recovery Algorithm -- 3 Results -- 3.1 Performance of the Recovery Algorithm -- 3.2 Pooling Matrices -- 4 Discussion -- References -- Phylogenetics -- Novel Phylogenetic Network Distances Based on Cherry Picking.
1 Introduction -- 2 Preliminaries -- 2.1 Network Definitions -- 2.2 Cherry Operations -- 3 Distances Based on Cherry-Picking Sequences -- 4 Computing the Tail Distance Between Two Trees -- 4.1 Computing an LR-MAST -- 5 NP-hardness of dtail Between a Tree and a Network -- 6 Discussion and Future Work -- 1 Proof of Lemma 1 (Page 6) -- 2 Proof of Theorems in Sect.3 (Theorem 2 Page 7, Theroem 3 Page 8, Theorem 4 Page 8, Theorem 5 Page 8) -- 3 Proof of Lemma 6, 7 and Theorem 8 (Page 9) -- 4 LR-MAST Algorithm, and Associated Theorem (Page 9) -- 5 Proof of Theorem 10 (Page 12) and Theorem 11 (Page 12) -- References -- Best Match Graphs with Binary Trees -- 1 Introduction -- 2 Best Match Graphs -- 3 Binary Trees Explaining a BMG in Near Cubic Time -- 4 The Binary-Refinable Tree of a BMG -- 5 Simulation Results -- 6 Concluding Remarks -- References -- Scalable and Accurate Phylogenetic Placement Using pplacer-XR -- 1 Introduction -- 2 pplacer-XR -- 3 Experimental Study Design -- 4 Results -- 4.1 Query Placement Accuracy -- 4.2 Time Analysis -- 5 Conclusions -- References -- Comparing Methods for Species Tree Estimation with Gene Duplication and Loss -- 1 Introduction -- 2 Experimental Design -- 3 Results -- 4 Discussion and Conclusion -- References -- Sequence Alignment and Genome Rearrangement -- Reversal Distance on Genomes with Different Gene Content and Intergenic Regions Information -- 1 Introduction -- 2 Background -- 3 Labeled Intergenic Breakpoint Graph -- 4 3-Approximation Algorithm -- 5 Conclusions -- References -- Reversals Distance Considering Flexible Intergenic Regions Sizes -- 1 Introduction -- 2 Definitions -- 2.1 Flexible Weighted Cycle Graph -- 3 Results -- 3.1 Lower Bound -- 3.2 Approximation Algorithm -- 4 Conclusion -- References -- Improved DNA-versus-Protein Homology Search for Protein Fossils -- 1 Introduction -- 2 Methods. 2.1 Alignment Elements -- 2.2 Scoring Scheme -- 2.3 Finding a Maximum-Score Local Alignment -- 2.4 Probability Model -- 2.5 Sum over All Alignments Passing Through (i,j) -- 2.6 Significance Calculation -- 2.7 Seed-and-Extend Heuristic -- 2.8 Fitting Substitution and Gap Parameters to Sequence Data -- 3 Results -- 3.1 Software -- 3.2 Parameter Fitting -- 3.3 Significance Calculation and Simple Sequences -- 3.4 Comparison to Blastx -- 3.5 Discovery of Missing TE Orders in the Human Genome -- 4 Discussion -- References -- The Maximum Weight Trace Alignment Merging Problem -- 1 Introduction -- 2 Maximum Weight Trace Alignment Merging -- 3 Graph Clustering Merger (GCM) -- 4 Experimental Study -- 5 Results -- 6 Conclusions -- References -- Author Index. |
Record Nr. | UNINA-9910484962603321 |
Cham, Switzerland : , : Springer, , [2021] | ||
Materiale a stampa | ||
Lo trovi qui: Univ. Federico II | ||
|
Issues in mathematical linguistics [[electronic resource] ] : Workshop on Mathematical Linguistics, State College, Pa., April 1998 / / edited by Carlos Martín-Vide |
Pubbl/distr/stampa | Amsterdam ; ; Philadelphia, : John Benjamins Pub. Co., c1999 |
Descrizione fisica | 1 online resource (226 p.) |
Disciplina | 410/.1/51 |
Altri autori (Persone) | Martín VideCarlos |
Collana | Studies in functional and structural linguistics |
Soggetto topico | Mathematical linguistics |
Soggetto genere / forma | Electronic books. |
ISBN |
1-283-12176-X
9786613121769 90-272-8472-5 |
Formato | Materiale a stampa |
Livello bibliografico | Monografia |
Lingua di pubblicazione | eng |
Nota di contenuto |
ISSUES IN MATHEMATICAL LINGUISTICS; Editorial page; Title page; Copyright page; Foreword; Table of contents; List of Contributors; Commands as Binary Relations; Generalized Minimalist Grammars; An Infinite Hierarchy of Mildly Context-Sensitive Families of Languages; Some Uses and Abuses of Mathematics in Linguistics; Logical Splicing in Natural Languages; X-Families: An Approach to the Study of Families of Syntactically Similar Languages; Overparsing; Computational Complexity in Language Models; Grammar Efficiency and the Historical Development of Word Order in French; Author Index
Subject Index |
Record Nr. | UNINA-9910459560703321 |
Amsterdam ; ; Philadelphia, : John Benjamins Pub. Co., c1999 | ||
Materiale a stampa | ||
Lo trovi qui: Univ. Federico II | ||
|
Issues in mathematical linguistics [[electronic resource] ] : Workshop on Mathematical Linguistics, State College, Pa., April 1998 / / edited by Carlos Martín-Vide |
Pubbl/distr/stampa | Amsterdam ; ; Philadelphia, : John Benjamins Pub. Co., c1999 |
Descrizione fisica | 1 online resource (226 p.) |
Disciplina | 410/.1/51 |
Altri autori (Persone) | Martín VideCarlos |
Collana | Studies in functional and structural linguistics |
Soggetto topico | Mathematical linguistics |
ISBN |
1-283-12176-X
9786613121769 90-272-8472-5 |
Formato | Materiale a stampa |
Livello bibliografico | Monografia |
Lingua di pubblicazione | eng |
Nota di contenuto |
ISSUES IN MATHEMATICAL LINGUISTICS; Editorial page; Title page; Copyright page; Foreword; Table of contents; List of Contributors; Commands as Binary Relations; Generalized Minimalist Grammars; An Infinite Hierarchy of Mildly Context-Sensitive Families of Languages; Some Uses and Abuses of Mathematics in Linguistics; Logical Splicing in Natural Languages; X-Families: An Approach to the Study of Families of Syntactically Similar Languages; Overparsing; Computational Complexity in Language Models; Grammar Efficiency and the Historical Development of Word Order in French; Author Index
Subject Index |
Record Nr. | UNINA-9910790059703321 |
Amsterdam ; ; Philadelphia, : John Benjamins Pub. Co., c1999 | ||
Materiale a stampa | ||
Lo trovi qui: Univ. Federico II | ||
|
Issues in mathematical linguistics : Workshop on Mathematical Linguistics, State College, Pa., April 1998 / / edited by Carlos Martín-Vide |
Edizione | [1st ed.] |
Pubbl/distr/stampa | Amsterdam ; ; Philadelphia, : John Benjamins Pub. Co., c1999 |
Descrizione fisica | 1 online resource (226 p.) |
Disciplina | 410/.1/51 |
Altri autori (Persone) | Martín VideCarlos |
Collana | Studies in functional and structural linguistics |
Soggetto topico | Mathematical linguistics |
ISBN |
1-283-12176-X
9786613121769 90-272-8472-5 |
Formato | Materiale a stampa |
Livello bibliografico | Monografia |
Lingua di pubblicazione | eng |
Nota di contenuto |
ISSUES IN MATHEMATICAL LINGUISTICS; Editorial page; Title page; Copyright page; Foreword; Table of contents; List of Contributors; Commands as Binary Relations; Generalized Minimalist Grammars; An Infinite Hierarchy of Mildly Context-Sensitive Families of Languages; Some Uses and Abuses of Mathematics in Linguistics; Logical Splicing in Natural Languages; X-Families: An Approach to the Study of Families of Syntactically Similar Languages; Overparsing; Computational Complexity in Language Models; Grammar Efficiency and the Historical Development of Word Order in French; Author Index
Subject Index |
Record Nr. | UNINA-9910811583003321 |
Amsterdam ; ; Philadelphia, : John Benjamins Pub. Co., c1999 | ||
Materiale a stampa | ||
Lo trovi qui: Univ. Federico II | ||
|
Mathematical and computational analysis of natural language [[electronic resource] ] : selected papers from the 2nd International Conference on Mathematical Linguistics, Tarragona, 2-4 May 1996 / / edited by Carlos Martín-Vide |
Pubbl/distr/stampa | Amsterdam ; ; Philadelphia, : John Benjamins, 1998 |
Descrizione fisica | 1 online resource (409 p.) |
Disciplina | 410/.1/51 |
Altri autori (Persone) | Martín VideCarlos |
Collana | Studies in functional and structural linguistics |
Soggetto topico | Mathematical linguistics |
Soggetto genere / forma | Electronic books. |
ISBN |
9786613234155
90-272-8227-7 1-283-23415-7 |
Formato | Materiale a stampa |
Livello bibliografico | Monografia |
Lingua di pubblicazione | eng |
Nota di contenuto | pt. 1. Syntax -- pt. 2. Semantics -- pt. 3. Natural language processing -- pt. 4. Varia. |
Record Nr. | UNINA-9910456724703321 |
Amsterdam ; ; Philadelphia, : John Benjamins, 1998 | ||
Materiale a stampa | ||
Lo trovi qui: Univ. Federico II | ||
|
Mathematical and computational analysis of natural language [[electronic resource] ] : selected papers from the 2nd International Conference on Mathematical Linguistics, Tarragona, 2-4 May 1996 / / edited by Carlos Martín-Vide |
Pubbl/distr/stampa | Amsterdam ; ; Philadelphia, : John Benjamins, 1998 |
Descrizione fisica | 1 online resource (409 p.) |
Disciplina | 410/.1/51 |
Altri autori (Persone) | Martín VideCarlos |
Collana | Studies in functional and structural linguistics |
Soggetto topico | Mathematical linguistics |
ISBN |
9786613234155
90-272-8227-7 1-283-23415-7 |
Formato | Materiale a stampa |
Livello bibliografico | Monografia |
Lingua di pubblicazione | eng |
Nota di contenuto | pt. 1. Syntax -- pt. 2. Semantics -- pt. 3. Natural language processing -- pt. 4. Varia. |
Record Nr. | UNINA-9910781787203321 |
Amsterdam ; ; Philadelphia, : John Benjamins, 1998 | ||
Materiale a stampa | ||
Lo trovi qui: Univ. Federico II | ||
|
Mathematical and computational analysis of natural language : selected papers from the 2nd International Conference on Mathematical Linguistics, Tarragona, 2-4 May 1996 / / edited by Carlos Martín-Vide |
Edizione | [1st ed.] |
Pubbl/distr/stampa | Amsterdam ; ; Philadelphia, : John Benjamins, 1998 |
Descrizione fisica | 1 online resource (409 p.) |
Disciplina | 410/.1/51 |
Altri autori (Persone) | Martín VideCarlos |
Collana | Studies in functional and structural linguistics |
Soggetto topico | Mathematical linguistics |
ISBN |
9786613234155
90-272-8227-7 1-283-23415-7 |
Formato | Materiale a stampa |
Livello bibliografico | Monografia |
Lingua di pubblicazione | eng |
Nota di contenuto | pt. 1. Syntax -- pt. 2. Semantics -- pt. 3. Natural language processing -- pt. 4. Varia. |
Record Nr. | UNINA-9910815023803321 |
Amsterdam ; ; Philadelphia, : John Benjamins, 1998 | ||
Materiale a stampa | ||
Lo trovi qui: Univ. Federico II | ||
|
Scientific applications of language methods [[electronic resource] /] / edited by Carlos Martín-Vide |
Pubbl/distr/stampa | London, : Imperial College Press, 2011 |
Descrizione fisica | 1 online resource (750 p.) |
Disciplina | 006.3 |
Altri autori (Persone) | Martín VideCarlos |
Collana | Mathematics, computing, language, and life. Frontiers in mathematical linguistics and language theory |
Soggetto topico |
Formal languages
Natural language processing (Computer science) |
Soggetto genere / forma | Electronic books. |
ISBN |
1-283-14339-9
9786613143396 1-84816-545-5 |
Formato | Materiale a stampa |
Livello bibliografico | Monografia |
Lingua di pubblicazione | eng |
Nota di contenuto |
Preface; Contents; Chapter 1 Descriptional Complexity - An Introductory Survey; 1.1 Introduction; 1.2 Descriptional Systems and Complexity Measures; 1.3 Measuring Sizes; 1.3.1 Descriptional Systems for Regular Languages; 1.3.1.1 Finite Automata; 1.3.1.2 Regular Expressions; 1.3.2 Pushdown Automata and Context-Free Grammars; 1.3.2.1 Pushdown Automata; 1.3.2.2 Context-Free Grammars; 1.4 Measuring Resources; 1.5 Non-Recursive Trade-Offs; 1.5.1 Proving Non-Recursive Trade-Offs; 1.5.2 A Compilation of Non-Recursive Trade-Offs; References
3.2.1 Classical Notions3.2.2 Extended Glushkov Construction; 3.2.3 Normal Forms and Casting Operation; 3.2.4 Characterization of Glushkov Automata in the Boolean Case; 3.2.5 The Problem of Reduction Rules; 3.3 Acyclic Glushkov WFA Properties; 3.3.1 K-rules; 3.3.2 Confluence for K-rules; 3.3.3 K-reducibility; 3.3.4 Several Examples of Use for K-rules; 3.4 Glushkov K-graph with Orbits; 3.5 Algorithm for Orbit Reduction; 3.6 Conclusion; References; Chapter 4 Natural Language Dictionaries Implemented as Finite Automata; 4.1 Dictionaries as Finite Automata 4.1.1 Simple and Complex, Static and Dynamic4.1.1.1 Implementing a Dictionary; 4.1.2 Variants of Finite-State Machines Relevant to Dictionary Data Structure Implementation; 4.1.2.1 Deterministic Finite-State Automaton; 4.1.2.2 Trie; 4.1.2.3 Minimal Deterministic Finite Automaton; 4.1.2.4 Recursive Automaton; 4.1.2.5 Nondeterministic FA and ε - NDFA; 4.1.2.6 Transducer; 4.1.2.7 Implementing Dictionaries with FSMs; 4.2 Automata as Mappings; 4.2.1 Perfect Hashing; 4.2.2 Morphological Analysis and Synthesis; 4.2.3 Spelling Correction and Restoration of Diacritics 4.2.4 Gazetteers and Information Extraction4.2.4.1 Pure DFA Approach; 4.2.4.2 Indexing Automaton Approach; 4.3 Construction Methods; 4.3.1 Construction from Strings; 4.3.2 Construction from Strings with Some Cyclic Structures; 4.3.3 Construction from Smaller Automata; 4.3.4 Construction from Other Sources; 4.4 Internal Structure and Compression; 4.4.1 Representation of Automata; 4.4.1.1 Transition Matrix; 4.4.1.2 Transition Lists; 4.4.1.3 Compressed Transition Matrix; 4.4.1.4 Comparison; 4.4.2 Compression Techniques; 4.4.2.1 A Space Optimized Representation of RA 4.4.2.2 Dictionary Compression |
Record Nr. | UNINA-9910461625203321 |
London, : Imperial College Press, 2011 | ||
Materiale a stampa | ||
Lo trovi qui: Univ. Federico II | ||
|
Scientific applications of language methods [[electronic resource] /] / edited by Carlos Martín-Vide |
Pubbl/distr/stampa | London, : Imperial College Press, 2011 |
Descrizione fisica | 1 online resource (750 p.) |
Disciplina | 006.3 |
Altri autori (Persone) | Martín VideCarlos |
Collana | Mathematics, computing, language, and life. Frontiers in mathematical linguistics and language theory |
Soggetto topico |
Formal languages
Natural language processing (Computer science) |
ISBN |
1-283-14339-9
9786613143396 1-84816-545-5 |
Formato | Materiale a stampa |
Livello bibliografico | Monografia |
Lingua di pubblicazione | eng |
Nota di contenuto |
Preface; Contents; Chapter 1 Descriptional Complexity - An Introductory Survey; 1.1 Introduction; 1.2 Descriptional Systems and Complexity Measures; 1.3 Measuring Sizes; 1.3.1 Descriptional Systems for Regular Languages; 1.3.1.1 Finite Automata; 1.3.1.2 Regular Expressions; 1.3.2 Pushdown Automata and Context-Free Grammars; 1.3.2.1 Pushdown Automata; 1.3.2.2 Context-Free Grammars; 1.4 Measuring Resources; 1.5 Non-Recursive Trade-Offs; 1.5.1 Proving Non-Recursive Trade-Offs; 1.5.2 A Compilation of Non-Recursive Trade-Offs; References
3.2.1 Classical Notions3.2.2 Extended Glushkov Construction; 3.2.3 Normal Forms and Casting Operation; 3.2.4 Characterization of Glushkov Automata in the Boolean Case; 3.2.5 The Problem of Reduction Rules; 3.3 Acyclic Glushkov WFA Properties; 3.3.1 K-rules; 3.3.2 Confluence for K-rules; 3.3.3 K-reducibility; 3.3.4 Several Examples of Use for K-rules; 3.4 Glushkov K-graph with Orbits; 3.5 Algorithm for Orbit Reduction; 3.6 Conclusion; References; Chapter 4 Natural Language Dictionaries Implemented as Finite Automata; 4.1 Dictionaries as Finite Automata 4.1.1 Simple and Complex, Static and Dynamic4.1.1.1 Implementing a Dictionary; 4.1.2 Variants of Finite-State Machines Relevant to Dictionary Data Structure Implementation; 4.1.2.1 Deterministic Finite-State Automaton; 4.1.2.2 Trie; 4.1.2.3 Minimal Deterministic Finite Automaton; 4.1.2.4 Recursive Automaton; 4.1.2.5 Nondeterministic FA and ε - NDFA; 4.1.2.6 Transducer; 4.1.2.7 Implementing Dictionaries with FSMs; 4.2 Automata as Mappings; 4.2.1 Perfect Hashing; 4.2.2 Morphological Analysis and Synthesis; 4.2.3 Spelling Correction and Restoration of Diacritics 4.2.4 Gazetteers and Information Extraction4.2.4.1 Pure DFA Approach; 4.2.4.2 Indexing Automaton Approach; 4.3 Construction Methods; 4.3.1 Construction from Strings; 4.3.2 Construction from Strings with Some Cyclic Structures; 4.3.3 Construction from Smaller Automata; 4.3.4 Construction from Other Sources; 4.4 Internal Structure and Compression; 4.4.1 Representation of Automata; 4.4.1.1 Transition Matrix; 4.4.1.2 Transition Lists; 4.4.1.3 Compressed Transition Matrix; 4.4.1.4 Comparison; 4.4.2 Compression Techniques; 4.4.2.1 A Space Optimized Representation of RA 4.4.2.2 Dictionary Compression |
Record Nr. | UNINA-9910789404903321 |
London, : Imperial College Press, 2011 | ||
Materiale a stampa | ||
Lo trovi qui: Univ. Federico II | ||
|