Self-verifying automata are a special variant of finite automata with a symmetric kind of nondeterminism. In this paper, we study the transformation of self-verifying automata into deterministic automata from a descriptional complexity point of view. The main result is the exact cost, in terms of the number of states, of such a simulation.
Converting self-verifying automata into deterministic automata / G. Jiraskova, G. Pighizzini - In: Language and automata theory and applications : third International conference, LATA 2009, Tarragona, Spain, April 2-8, 2009 : proceedings / [a cura di] A. H. Dediu, A. M. Ionescu, C. Martin-Vide. - Berlin : Springer, 2009. - ISBN 9783642009815. - pp. 458-468 (( Intervento presentato al 3. convegno International conference on Language and automata theory and applications (LATA) tenutosi a Tarragona (Spain) nel 2009.
Converting self-verifying automata into deterministic automata
G. PighizziniUltimo
2009
Abstract
Self-verifying automata are a special variant of finite automata with a symmetric kind of nondeterminism. In this paper, we study the transformation of self-verifying automata into deterministic automata from a descriptional complexity point of view. The main result is the exact cost, in terms of the number of states, of such a simulation.
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
