No label defined (Q3705345)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 3930882
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 3930882 |
Statements
1984
0 references
equation in words
0 references
constraint in words
0 references
bounded decoding delay
0 references
antiprefix property
0 references
optimal generalized prefix coding of local models of languages
0 references
probabilistic model of a diagram-bounded language
0 references
0.7715631723403931
0 references
0.7701787948608398
0 references
If R is a binary relation on a set of words, and \(\alpha\) and \(\beta\) are words in the alphabet \(B=<b_ 1,...,b_ m>\) of unknowns, then the condition \(\alpha\) \(R\beta\) is called an equation in words, while \(\alpha\) \(\bar R\beta\) is called a constraint in words of type R with respect to the q-ary alphabet A of solutions. The solutions are given by the sets \(V=<v_ 1,...,v_ m>\) of words in A (which are also called q- ary codes) which yield true statements when substituted in the left and right sides of the condition. Let A be the alphabet of a communication channel, \({\mathcal L}\subseteq B^*\) the message language, and \(f=f_ V: b_ i\to v_ i\), \(i=1,2,...,m\), an alphabetic coding scheme. For f to be one-to-one on \({\mathcal L}\) it is necessary and sufficient that the code V be a solution of the system \[ \Sigma ({\mathcal L}):\quad \{\alpha \neq \beta:\quad \alpha,\beta \in {\mathcal L},\quad \alpha \not\equiv \beta \} \] of constraints in words. Constructive sufficient conditions for one-to- oneness of f that can be checked on word samples that are bounded independently of the language are of special interest. Here we solve the coding problem for a local model of \({\mathcal L}\) of bounded depth, including the coding problem with bounded decoding delay. The property of boundedness of the decoding delay is a generalization of the prefix property: successive localization of the elementary codes is carried out (except for a finite number of cases) on the basis of the antiprefix property of the words. In this note we give algorithmic results relating to optimal generalized prefix coding of local models of languages. An example is given of coding of probabilistic model of a diagram-bounded language with zero redundancy according to a local model of depth 2 which is an essential refinement of a local model of depth 1.
0 references