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

      0 references
      0 references
      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
      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

      Identifiers

      0 references
      0 references
      0 references
      0 references