On partitions separating words. (English) Zbl 1239.68039

Holub, Štěpán; Kortelainen, Juha

Int. J. Algebra Comput. 21, No. 8, 1305-1316 (2011).

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.

Reviewer: Adrian Atanasiu (Bucharest)

MSC:

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

Keywords:

formal languages; finite automata; separation by closed sets; Parikh vector

Citations:

Zbl 1247.68129

References:

[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