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
1984
0 references
free monoid
0 references
three-element codes
0 references
0 references
0.9086455
0 references
0 references
0 references
0 references
0 references
0.87433267
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