pipette
ENEnglish

From k+1 to k heads the descriptive trade-off is non-recursive

Christos Kapoutsis

Preprint

En palabras de los autores

We prove that no recursive function can upper bound the increase in the size of description when a two-way deterministic finite automaton with k+1 heads is replaced by an equivalent two-way deterministic finite automaton with k heads. This is true for all k, and remains true if the automata are unary and/or nondeterministic.

Resultado principalEl resumen no menciona limitaciones.

Apareció: viernes, 9 de octubre. arXiv. Preprint, todavía sin revisión por pares.

Comentario de los autores: Proceedings of DCFS 2004, pp. 213-224. Number of pages: 13. Number of figures: 0