On Del-Robust Primitive Partial Words with One Hole
| Autor: | Amit Kumar Srivastava, Ananda Chandra Nayak |
|---|---|
| Rok vydání: | 2016 |
| Předmět: |
String (computer science)
Context-free language Computer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing) 0102 computer and information sciences 02 engineering and technology Special class 01 natural sciences Combinatorics General Relativity and Quantum Cosmology Combinatorics on words 010201 computation theory & mathematics Symbol (programming) Single hole 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Partial word Computer Science::Formal Languages and Automata Theory Word (group theory) Mathematics |
| Zdroj: | Language and Automata Theory and Applications ISBN: 9783319299990 LATA |
| DOI: | 10.1007/978-3-319-30000-9_18 |
| Popis: | A partial word is a string over a finite alphabet with some undefined places which are known as holes or “do not know” symbols. A partial word w is said to be primitive if there does not exist any word v such that w is contained in \(v^n\) with \(n \ge 2\). We investigate the effect of a point mutation on primitive partial words with a single hole. We characterize a special class of such words, del-robust primitive partial words with one hole, that remains primitive on deletion of any symbol or the hole. We identify some important properties of such words and prove that the language of non-del-robust primitive partial words with one hole is not context-free. Finally we approximate the counting of del-robust primitive partial words with one hole for a fixed length. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|