6533b856fe1ef96bd12b1c99

RESEARCH PRODUCT

Complexity of operations on cofinite languages

Frédérique BassinoCyril NicaudLaura Giambruno

subject

Nested wordTheoretical computer scienceSettore INF/01 - Informaticaautomata[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS]regular operationReDoSComputer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing)[INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS]0102 computer and information sciences02 engineering and technologyDescriptive complexity theorystate complexity01 natural sciencesComplement (complexity)Deterministic finite automaton010201 computation theory & mathematicsTheory of computation0202 electrical engineering electronic engineering information engineeringComputer Science::Programming LanguagesQuantum finite automata020201 artificial intelligence & image processingNondeterministic finite automatoncofinite languageMathematics

description

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

yearjournalcountryeditionlanguage
2010-04-19
10.1007/978-3-642-12200-2_21http://hdl.handle.net/10447/55822