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.
EnglishWe 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.
| Titolo: | Complementing two-way finite automata |
| Autori: | MEREGHETTI, CARLO (Secondo) PIGHIZZINI, GIOVANNI (Ultimo) |
| Parole Chiave: | Automata and formal languages; Descriptional complexity |
| Settore Scientifico Disciplinare: | Settore INF/01 - Informatica |
| Data di pubblicazione: | 2005 |
| Enti collegati al convegno: | European Association for Theoretical Computer Science |
| Digital Object Identifier (DOI): | http://dx.doi.org/10.1007/11505877_23 |
| Tipologia: | Book Part (author) |
| Appare nelle tipologie: | 03 - Contributo in volume |
File in questo prodotto:
| File | Descrizione | Tipologia | Licenza | |
|---|---|---|---|---|
| pubblicato.pdf | Publisher's version/PDF | Administrator Richiedi una copia |
http://hdl.handle.net/2434/9762
Copyright © 2020