About prefix sets of words (Q1122006): Difference between revisions
From MaRDI portal
Removed claim: reviewed by (P1447): Item:Q216237 |
ReferenceBot (talk | contribs) Changed an Item |
||
(3 intermediate revisions by 3 users not shown) | |||
Property / reviewed by | |||
Property / reviewed by: Daniel Krob / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/0097-3165(89)90048-4 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W195352547 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4430300 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: An answer to a question about finite maximal prefix sets of words / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Sur certains sous-monoïdes libres / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On a question concerning certain free submonoids / rank | |||
Normal rank |
Latest revision as of 15:44, 19 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | About prefix sets of words |
scientific article |
Statements
About prefix sets of words (English)
0 references
1989
0 references
A subset X of the free monoid \(A^*\) over the alphabet A is called prefix iff it satisfies the property: uv\(\in X\) and \(u\in X\) \(\Rightarrow\) \(v=1\). A set \(X\subset A^*\) is then called maximal prefix if it is prefix and not strictly contained in an other prefix subset of \(A^*\). It is easy to see that the concatenation product of two maximal prefix sets is also maximal prefix. A converse of this result was proved by \textit{M. P. Schützenberger} [Bull. Soc. Math. Fr. 93, 209-223 (1965; Zbl 0149.026)] under the hypotheses that X, Y are finite and that the product XY is unambiguous (for more details concerning this theorem or prefix sets, see \textit{J. Berstel} and \textit{D. Perrin} [Theory of Codes (1985; Zbl 0587.68066)]). Here, the author generalizes Schützenberger's result to the non finite case. It is proved that for every sets \(X,Y\subset A^*\) such that: i) \(\exists x_ 0\in X\), \(x_ 0A^+\cap X=\emptyset\), ii) \(\forall x\in X\), \(\exists n\in {\mathbb{N}}\), \(Y\cap R^ n_ xA^*=\emptyset\) where \(R_ x=\{w\in A^+\), \(x\in A^*w\}\) then, if the product XY is unambiguous and maximal prefix, X and Y are also maximal prefix. The two previous conditions are shown to be necessary.
0 references
ambiguity
0 references
free monoid
0 references
alphabet
0 references
concatenation product
0 references
maximal prefix sets
0 references