On the Existence of Universal Finite or Pushdown Automata

Manfred Kudlek
(Universität Hamburg)

We investigate the (non)-existence of universal automata for some classes of automata, such as finite automata and pushdown automata, and in particular the influence of the representation and encoding function. An alternative approach, using transition systems, is presented too.

In Elham Kashefi, Jean Krivine and Femke van Raamsdonk: Proceedings 7th International Workshop on Developments of Computational Methods (DCM 2011), Zurich, Switzerland, 3rd July 2011, Electronic Proceedings in Theoretical Computer Science 88, pp. 79–86.
Sadly, Manfred Kudlek passed away June 18, 2012, before publication of this paper.
Published: 30th July 2012.

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

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