Ricerc@Sapienza

We investigate the language classes recognized by group automata over matrix groups. We present a summary of the results obtained so far together with a number of new results. We look at the computational power of time-bounded group automata where the group under consideration has polynomial growth.

The problem of the commutative equivalence of context-free and regular languages is studied. In particular conditions ensuring that a context-free language of exponential growth is commutatively equivalent with a regular language are investigated.