State Complexity of Suffix Distance
| Autor: | Kai Salomaa, Timothy Ng, David Rappaport |
|---|---|
| Přispěvatelé: | Queen's University [Kingston, Canada], Giovanni Pighizzini, Cezar Câmpeanu, TC 1, WG 1.2 |
| Rok vydání: | 2019 |
| Předmět: |
Compressed suffix array
Discrete mathematics Generalized suffix tree Computer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing) 0102 computer and information sciences 02 engineering and technology 01 natural sciences Longest common substring problem Combinatorics Deterministic finite automaton Regular language 010201 computation theory & mathematics 0202 electrical engineering electronic engineering information engineering Computer Science (miscellaneous) Edit distance [INFO]Computer Science [cs] 020201 artificial intelligence & image processing Suffix FM-index Computer Science::Formal Languages and Automata Theory Mathematics |
| Zdroj: | Lecture Notes in Computer Science 19th International Conference on Descriptional Complexity of Formal Systems (DCFS) 19th International Conference on Descriptional Complexity of Formal Systems (DCFS), Jul 2017, Milano, Italy. pp.287-298, ⟨10.1007/978-3-319-60252-3_23⟩ Descriptional Complexity of Formal Systems ISBN: 9783319602516 DCFS |
| ISSN: | 1793-6373 0129-0541 |
| DOI: | 10.1142/s0129054119400355 |
| Popis: | The neighbourhood of a regular language with respect to the prefix, suffix and subword distance is always regular and a tight bound for the state complexity of prefix distance neighbourhoods is known. We give upper bounds for the state complexity of the neighbourhood of radius [Formula: see text] of an [Formula: see text]-state deterministic finite automaton language with respect to the suffix distance and the subword distance, respectively. For restricted values of [Formula: see text] and [Formula: see text] we give a matching lower bound for the state complexity of suffix distance neighbourhoods. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|