Combinatorics on words and Formal Language Theory

(in chronological order)

• ## 1. On a problem about contextual languages, Bulletin mathematique de la Societe des Sciences Mathematiques de Roumanie, 33 (81), 1989.

My first attempt at scientific research, I was still not even an undergraduate student at the moment of submitting it. It deals with the problem of showing that every regular language is inner contextual (an open problem at the time).

• ## 2. Self-reading sequences, Discrete Applied Mathematics Volume 50, Issue 2  (1994), Pages 201-203.

OK, this is a short one, but I was an undergraduate student at the time :). Basically, I was  traveling between Galati and Bucharest, Romania (a four hour train trip), the only thing to read was an issue of the Bulletin of the EATCS, that contained an article due  to A. Salomaa and G. Paun with several open problems. By the time the train reached Bucharest (despite not having any pen and paper) I had solved one of the open problems in their article :).  Namely, so-called self-reading sequences are not ultimately periodic. Despite its length/somewhat frivolous history, the paper turns out to be useful, especially in gauging the complexity of kneading sequences in Applied Symbolic Dynamics.

• ## 3. Some combinatorial properties of self-reading sequences (together with Gheorghe Paun),Discrete Applied Mathematics, Volume 55, Issue 1 , 28 October 1994, Pages 83-86.

This is also a rather short paper, completed while I was still an undergraduate student :). Like the previous paper in this area, this one has applications to  applied symbolic dynamics, namely in studying the disjunctiveness of kneading sequences. See this article for an overview of disjunctiveness in Theoretical Computer Science, and this for the (symbolic dynamics related) good stuff :).

## 5.The Strong Equivalence of ET0L Grammars, Information Processing Letters, vol. 62(1997), 171--177.

This is  a paper essentially completed during my undergraduate years, in fact its conference version has appeared in the Proceedings of the First Developments in Language Theory conference (1993). In essence I prove a result about "strong" notion of equivalence applied to Lindenmayer systems. For such systems, usual language equivalence is undecidable. To obtain a decidable property one has to provide some information about the structure of parse trees of the unknown grammar. I give one notion of equivalence that is decidable. Strangely enough, I found an application of the ideas in this paper more than ten years after the paper was completed :) ...