Self-verifying automata are a special variant of finite automata with a symmetric kind of nondeterminism. We study the conversion of self-verifying automata to 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.
Optimal simulation of self-verifying automata by deterministic automata / G. Jiraskova, G. Pighizzini. - In: INFORMATION AND COMPUTATION. - ISSN 0890-5401. - 209:3(2011 Mar), pp. 528-535. [10.1016/j.ic.2010.11.017]
Optimal simulation of self-verifying automata by deterministic automata
G. PighizziniUltimo
2011
Abstract
Self-verifying automata are a special variant of finite automata with a symmetric kind of nondeterminism. We study the conversion of self-verifying automata to 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.
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
