Descriptional Complexity of the Languages KaL: Automata, Monoids and Varieties

Ondřej Klíma
(Department of Mathematics and Statistics, Masaryk University Brno, Czech Republic)
Libor Polák
(Department of Mathematics and Statistics, Masaryk University Brno, Czech Republic)

The first step when forming the polynomial hierarchies of languages is to consider languages of the form KaL where K and L are over a finite alphabet A and from a given variety V of languages, a being a letter from A. All such KaL's generate the variety of languages BPol1(V).

We estimate the numerical parameters of the language KaL in terms of their values for K and L. These parameters include the state complexity of the minimal complete DFA and the size of the syntactic monoids. We also estimate the cardinality of the image of A* in the Schuetzenberger product of the syntactic monoids of K and L. In these three cases we obtain the optimal bounds.

Finally, we also consider estimates for the cardinalities of free monoids in the variety of monoids corresponding to BPol1(V) in terms of sizes of the free monoids in the variety of monoids corresponding to V.

In Ian McQuillan and Giovanni Pighizzini: Proceedings Twelfth Annual Workshop on Descriptional Complexity of Formal Systems (DCFS 2010), Saskatoon, Canada, 8-10th August 2010, Electronic Proceedings in Theoretical Computer Science 31, pp. 130–138.
Published: 7th August 2010.

ArXived at: http://dx.doi.org/10.4204/EPTCS.31.15 bibtex PDF

Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org