On partitions separating words. (English) Zbl 1239.68039

The paper continues and improves a result from [J. Brzozowski, E. Grant and J. Shallit, “Closures in formal languages and Kuratowski’s theorem”, Lect. Notes Comput. Sci. 5583, 125–144 (2009; Zbl 1247.68129)] (this being the only recent reference; all the others are before 1998), namely, it proves the following theorem for a finite alphabet \(A\): Let \(m\) be a positive integer and let \(u_1,u_2,\dots,u_m\in A^{+}\). There exists a closed partition of \(A^{+}\) separating these words if and only if for all distinct \(i,j\in\{1,\dots,m\}\), the words \(u_i\) and \(u_j\) do not commute.
Although the proof addresses only the binary case \(A=\{0,1\}\), the result is very interesting. Moreover, the authors show that the languages \(L_1,\dots,L_m\) defined here as the partition of \(A^+\) (with \(u_i\in L_i\)) are regular while the languages from the original theorem [loc. cit., Theorem 14] are context-sensitive. I appreciate the construction of finite automata which recognize these languages as a remarkable result.
Using the notion of a Parikh vector in order to treat these problems from a geometrical point of view, the paper proposes an interesting conjecture: Let \(m\in\mathbb{N}_+\) and \(u_1,\dots,u_m\in A^+\) be words such that the Parikh vectors of any two distinct words are linearly independent. Then there exists a closed partition of \(A^+\) into \(m\) commutative context-free languages separating \(u_1,\dots,u_m\).
This assertion is proved only for the case \(m=2\).
The paper is well constructed, with a surprising interference between formal languages theory and number theory. Although some assertions create problems for the reader (for example, on page 1309, a sequence \(z=123\) can be interpreted and evaluated in four different modes: \(b((1)(2)(3))=11,\; b((1)(23))=25,\; b((12)(3))=27,\; b((123))=123\)), in general, all information is described in detail, and adequate examples are provided to clarify various situations. I recommend this paper in particular because of the possibility of interesting implications for future research.


68Q45 Formal languages and automata
68R15 Combinatorics on words
52C35 Arrangements of points, flats, hyperplanes (aspects of discrete geometry)


Zbl 1247.68129
Full Text: DOI


[1] DOI: 10.1016/0022-0000(87)90018-3 · Zbl 0627.68063
[2] Brzozowski J., LNCS 5583 pp 125–
[3] Boudet A., LNCS 1059 pp 30–
[4] Ginsburg S., The Mathematical Theory of Context Free Languages (1966) · Zbl 0184.28401
[5] Hammer P. C., Nieuw Archief v. Wiskunde 7 pp 74–
[6] DOI: 10.1006/jcss.1997.1553 · Zbl 0914.68119
[7] Kuratowski C., Fund. Math. 3 pp 182–
[8] Lothaire M., Combinatorics on Words (1983) · Zbl 0514.20045
[9] DOI: 10.1016/0012-365X(84)90055-4 · Zbl 0542.54001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.