Bad Pictures: Some Structural Properties Related to Overlaps
| Autor: | Marcella Anselmo, Dora Giammarresi, Maria Madonia, Carla Selmi |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
Overlap
Existential quantification Binary number 0102 computer and information sciences 02 engineering and technology 01 natural sciences Index Combinatorics Transformation (function) 010201 computation theory & mathematics 0202 electrical engineering electronic engineering information engineering Bad pictures 020201 artificial intelligence & image processing Mathematics |
| Zdroj: | Descriptional Complexity of Formal Systems ISBN: 9783030625351 DCFS |
| DOI: | 10.1007/978-3-030-62536-8_2 |
| Popis: | Given two pictures p and f, p is f-free if f is not a sub-picture of p. A binary picture f is good if for any pair of f-free pictures p and q there exists a bit-to-bit transformation from p to q such that any picture in the intermediate steps is f-free. Such transformation is called f-free transformation. A binary picture is bad if it is not good. These notions generalize to pictures the corresponding ones for strings. We study some properties of bad binary pictures in terms of overlaps and give some examples. Furthermore, we discuss the properties of an index of a bad picture f, that is a minimal picture size (h, k) for which two pictures of such size do not admit a f-free transformation. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|