Kybernetika 43 no. 3, 265-278, 2007

Automata with two-sided pushdowns defined over free groups generated by reduced alphabets

Petr Blatný, Radek Bidlo and Alexander Meduna

Abstract:

This paper introduces and discusses a modification of pushdown automata. This modification is based on two-sided pushdowns into which symbols are pushed from both ends. These pushdowns are defined over free groups, not free monoids, and they can be shortened only by the standard group reduction. We demonstrate that these automata characterize the family of recursively enumerable languages even if the free groups are generated by no more than four symbols.