Minimal representative set for a system of frequency classes of underdetermined words

L. A. Sholomov

Prikladnaya Diskretnaya Matematika. Supplement, no. 12 (2019), pp. 41-44.

Résumé

Let a finite set $M$ and a system $\mathcal{T}$ of some non-empty subsets $T\subseteq M$ be given. Associated with the sets $M$ and $\mathcal{T}$ are the alphabets $A_0=\{a_i,\,i\in M\}$ of basic symbols and $A=\{a_T,\; T\in\mathcal{T}\}$ of underdetermined symbols. The set of all words of length $l$ in the alphabet $A$, in which each symbol $a_T$ is present $r_T$ times, $\sum\limits_{T\in\mathcal{T}} r_T=l$, is called frequency class and denoted by $\mathcal{K}_l(\mathbf{r})$ where $\mathbf{r}=(r_T,\,T\in\mathcal{T})$. The specification of the word $v$ in the alphabet $A$ is any word obtained from $v$ by replacing each symbol $a_T$ with some $a_i$, $i\in T$. The specification of the set $V$ of words in the alphabet $A$ is any set of words in the alphabet $A_0$, containing for each word $v\in V$ some specification of it. The class $\mathcal{K}_{l_1}(\mathbf{r}_1)$ is considered to be more representative than the class $\mathcal{K}_{l_2}(\mathbf{r}_2)$, if $l_1\ge l_2$ and, whatever the specification of the class $\mathcal{ K}_{l_1}(\mathbf{r}_1)$, the set of beginnings of the length $l_2$ of all words from the specification forms some specification for the class $\mathcal{K}_{l_2}(\mathbf{r}_2)$. Let $\mathfrak K$ be some system of frequency classes. A subsystem of $\mathfrak K$ is called a representative set of the system $\mathfrak K$ if, for any $\mathcal{K}_l(\mathbf{r})\in\mathfrak K$, the subsystem contains a class that is more representative than $\mathcal{K}_l (\mathbf{r})$. The paper presents a method for finding the smallest representative set for an arbitrary system of frequency classes. This setting arises in the problems of underdetermined data compression and of underdetermined functions implementation.

Détail

Keywords: underdetermined data, specification, frequency class, representative set.

Bibliographie

[1] Sholomov L. A., “Elementy teorii nedoopredelennoi informatsii”, Prikladnaya diskretnaya matematika. Prilozhenie, 2009, no. 2, 18–42

[2] Sholomov L. A., “O funktsionalakh, kharakterizuyuschikh slozhnost sistem nedoopredelennykh bulevykh funktsii”, Problemy kibernetiki, 19, Fizmatlit, M., 1967, 123–139

[3] Nechiporuk E. I., “O slozhnosti ventilnykh skhem, realizuyuschikh bulevskie matritsy s neopredelennymi elementami”, DAN SSSR, 163:1 (1965), 40–42 | Zbl

[4] Adelson-Velskii G. M., Dinits E. A., Karzanov A. V., Potokovye algoritmy, Nauka, M., 1975 | MR