No label defined (Q3343463)

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 3878385
Language Label Description Also known as
default for all languages
No label defined
    English
    No label defined
    scientific article; zbMATH DE number 3878385

      Statements

      0 references
      1984
      0 references
      free monoid
      0 references
      three-element codes
      0 references
      [For the entire collection see Zbl 0533.00025.] Let A be a finite set of words over a finite alphabet \(\Sigma\). We define \(Amb(A)=\{x\in \Sigma^*\cup \Sigma^{\omega}| x=\alpha u<\beta v\) for some \(\alpha\),\(\beta\in A\), \(\alpha\) \(\neq \beta\), and \(u,v\in A^*\cup A^{\omega}\},\) where \(\Sigma^{\omega}\) denotes the set of all infinite words from left to right and the relation \(<\) stands for ''is a prefix of''. It is well-known that for any two-element code (base of a free monoid) A there exists a finite word w such that \(Amb(A)=pref(w)\) \((=the\) set of all prefixes of w). We show that the similar result holds for three-element codes, too. Now, however, w need not be finite, i.e., \(Amb(A)=pref(xy^{\omega}),\) for some finite words x and y. For four- element codes the structure of Amb(A) is much more complicated. Later on the author has deduced from the main result of this paper that each three-element code has a bounded delay in at least one direction [Theor. Comput. Sci. (to appear)].
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references