IRIS Institutional Research Information System - AIR Archivio Istituzionale della Ricerca

IRIS è il sistema di gestione integrata dei dati della ricerca (persone, progetti, pubblicazioni, attività) adottato dall'Università degli Studi di Milano.

AIR nasce in UNIMI nel 2006 con lo scopo di raccogliere, documentare e conservare le informazioni sulla produzione scientifica dell'Università degli Studi di Milano e costituisce di fatto l'Anagrafe della ricerca dell'Ateneo.

We study the relationship between the sizes of two-way finite automata accepting a language and its complement. In the deterministic case, by adapting Sipser's method, for a given automaton (2dfa) with n states we build an automaton accepting the complement with at most 4n states, independently of the size of the input alphabet. Actually, we show a stronger result, by presenting an equivalent 4n-state 2dfa that always halts. For the nondeterministic case, using a variant of inductive counting, we show that the complement of a unary language, accepted by an n-state two-way automaton (2nfa), can be accepted by an O(n8)-state 2nfa. Here we also make the 2nfa halting. This allows the simulation of unary 2nfa's by probabilistic Las Vegas two-way automata with O(n8) states.

Complementing two-way finite automata / V. Geffert, C. Mereghetti, G. Pighizzini - In: Developments in language theory / [a cura di] C. De Felice, A. Restivo. - Berlin : Springer, 2005. - ISBN 9783540265467. - pp. 260-271 (( Intervento presentato al 9. convegno International Conference Developments in Language Theory tenutosi a Palermo nel 2005.

Powered by IRIS-about IRIS-Utilizzo dei cookie

 Copyright © 2021