Reconstructing Words from Right-Bounded-Block Words
| Autor: | Pamela Fleischmann, Michel Rigo, Florin Manea, Dirk Nowotka, Marie Lejeune |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2020 |
| Předmět: |
FOS: Computer and information sciences
Discrete Mathematics (cs.DM) Formal Languages and Automata Theory (cs.FL) Computer Science::Information Retrieval 010102 general mathematics Astrophysics::Instrumentation and Methods for Astrophysics Computer Science - Formal Languages and Automata Theory Computer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing) 0102 computer and information sciences 01 natural sciences Article Combinatorics Combinatorics on words Reconstruction problem 010201 computation theory & mathematics Block (telecommunications) Bounded function Computer Science (miscellaneous) FOS: Mathematics Mathematics - Combinatorics Computer Science::General Literature Combinatorics (math.CO) 0101 mathematics Computer Science - Discrete Mathematics Mathematics |
| Zdroj: | Developments in Language Theory |
| Popis: | A reconstruction problem of words from scattered factors asks for the minimal information, like multisets of scattered factors of a given length or the number of occurrences of scattered factors from a given set, necessary to uniquely determine a word. We show that a word \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$w\in \{\mathtt {a},\mathtt {b}\}^*$$\end{document} can be reconstructed from the number of occurrences of at most \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\min (|w|_\mathtt {a},|w|_\mathtt {b})+1$$\end{document} scattered factors of the form \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathtt {a}^i \mathtt {b}$$\end{document}, where \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$|w|_{\mathtt {a}}$$\end{document} is the number of occurrences of the letter \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathtt {a}$$\end{document} in w. Moreover, we generalize the result to alphabets of the form \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\{1, \ldots , q\}$$\end{document} by showing that at most \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\sum _{i=1}^{q-1} |w|_i \, (q-i+1)$$\end{document} scattered factors suffices to reconstruct w. Both results improve on the upper bounds known so far. Complexity time bounds on reconstruction algorithms are also considered here. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|