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

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

2010-08-10

arxiv.org/abs/1008.1655v1

EPTCS 31, 2010, pp. 130-138

Computer Science

Formal Languages and Automata Theory

In Proceedings DCFS 2010, arXiv:1008.1270

Scientific paper

10.4204/EPTCS.31.15

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.

Affiliated with

Also associated with

No associations

Rating

Descriptional Complexity of the Languages KaL: Automata, Monoids and Varieties does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Descriptional Complexity of the Languages KaL: Automata, Monoids and Varieties, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Descriptional Complexity of the Languages KaL: Automata, Monoids and Varieties will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-583276