This paper investigates acceptance conditions for finite automata recognizing omega-regular languages. Their expressive power and their position w.r.t. the Borel hierarchy is also studied. The full characterization for the conditions (nin f, (sic)), (nin f, subset of) and (nin f, =) is given. The final section provides a partial characterization of (f in, =)
Dennunzio, A., Formenti, E., Provillard, J. (2012). Acceptance Conditions for ω-Languages. In Developments in Language Theory (pp.320-331) [10.1007/978-3-642-31653-1_29].
Acceptance Conditions for ω-Languages
DENNUNZIO, ALBERTO;
2012
Abstract
This paper investigates acceptance conditions for finite automata recognizing omega-regular languages. Their expressive power and their position w.r.t. the Borel hierarchy is also studied. The full characterization for the conditions (nin f, (sic)), (nin f, subset of) and (nin f, =) is given. The final section provides a partial characterization of (f in, =)
File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
