Parsing with a finite dictionary
| Autor: | Jean-Pierre Duval, Giuseppina Rindone, Julien Clément, Giovanna Guaiana, Dominique Perrin |
|---|---|
| Rok vydání: | 2005 |
| Předmět: |
Finite-state machine
Parsing General Computer Science General problem String searching algorithm computer.software_genre Theoretical Computer Science Combinatorics String matching Decomposition method (constraint satisfaction) Suffix Finite automata computer Word length Computer Science(all) Mathematics |
| Zdroj: | Theoretical Computer Science. 340:432-442 |
| ISSN: | 0304-3975 |
| DOI: | 10.1016/j.tcs.2005.03.030 |
| Popis: | We address the following issue: given a word w ∈ A* and a set of n nonempty words X, how does one determine efficiently whether w ∈ X* or not? We discuss several methods including an O(r × |w| + |X|) algorithm for this problem where r ≤ n is the length of a longest suffix chain of X and |X| is the sum of the lengths of words in X. We also consider the more general problem of providing all the decompositions of w in words of X. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect