Complexity of operations on cofinite languages

Laura Giambruno, Frédérique Bassino, Cyril Nicaud

Risultato della ricerca: Other

3 Citazioni (Scopus)

Abstract

We study the worst case complexity of regular operations oncofinite languages (i.e., languages whose complement is finite) and provide algorithms to compute efficiently the resulting minimal automata.
Lingua originaleEnglish
Pagine222-233
Numero di pagine12
Stato di pubblicazionePublished - 2010

Fingerprint

Automata
Complement
Language

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Cita questo

Giambruno, L., Bassino, F., & Nicaud, C. (2010). Complexity of operations on cofinite languages. 222-233.

Complexity of operations on cofinite languages. / Giambruno, Laura; Bassino, Frédérique; Nicaud, Cyril.

2010. 222-233.

Risultato della ricerca: Other

Giambruno, L, Bassino, F & Nicaud, C 2010, 'Complexity of operations on cofinite languages', pagg. 222-233.
Giambruno, Laura ; Bassino, Frédérique ; Nicaud, Cyril. / Complexity of operations on cofinite languages. 12 pag.
@conference{e951a06061414386b015dc9ae64892b4,
title = "Complexity of operations on cofinite languages",
abstract = "We study the worst case complexity of regular operations oncofinite languages (i.e., languages whose complement is finite) and provide algorithms to compute efficiently the resulting minimal automata.",
keywords = "automata, cofinite languages, regular operations, state complexity",
author = "Laura Giambruno and Fr{\'e}d{\'e}rique Bassino and Cyril Nicaud",
year = "2010",
language = "English",
pages = "222--233",

}

TY - CONF

T1 - Complexity of operations on cofinite languages

AU - Giambruno, Laura

AU - Bassino, Frédérique

AU - Nicaud, Cyril

PY - 2010

Y1 - 2010

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

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

KW - automata

KW - cofinite languages

KW - regular operations

KW - state complexity

UR - http://hdl.handle.net/10447/55822

M3 - Other

SP - 222

EP - 233

ER -