We study the worst case complexity of regular operations on cofinite languages (i.e., languages whose complement is finite) and provide algorithms to compute efficiently the resulting minimal automata.

Bassino, F., Giambruno, L., Nicaud, C. (2010). Complexity of operations on cofinite languages. In Lecture Notes in Computer Science (pp.222-233) [10.1007/978-3-642-12200-2_21].

Complexity of operations on cofinite languages

GIAMBRUNO, Laura;
2010-01-01

Abstract

We study the worst case complexity of regular operations on cofinite languages (i.e., languages whose complement is finite) and provide algorithms to compute efficiently the resulting minimal automata.
Settore INF/01 - Informatica
2010
9th Latin American Theoretical Informatics Symposium (LATIN'10)
Oaxaca, Mexico
12
Bassino, F., Giambruno, L., Nicaud, C. (2010). Complexity of operations on cofinite languages. In Lecture Notes in Computer Science (pp.222-233) [10.1007/978-3-642-12200-2_21].
Proceedings (atti dei congressi)
Bassino, F; Giambruno, L; Nicaud, C
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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10447/55822
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 4
  • ???jsp.display-item.citation.isi??? 3
social impact