Minimal cover-automata for finite languages



Title Minimal cover-automata for finite languages
Author(s) Cezar Campeanu, Nicolae Santean, S. Yu
Journal Theoretical Computer Science
Date 2001
Volume 267
Issue 1-2
Start page 3
End page 16
Abstract A cover-automaton A of a finite language L⊆Σ∗ is a finite deterministic automaton (DFA) that accepts all words in L and possibly other words that are longer than any word in L. A minimal deterministic finite cover automaton (DFCA) of a finite language L usually has a smaller size than a minimal DFA that accept L. Thus, cover automata can be used to reduce the size of the representations of finite languages in practice. In this paper, we describe an efficient algorithm that, for a given DFA accepting a finite language, constructs a minimal deterministic finite cover-automaton of the language. We also give algorithms for the boolean operations on deterministic cover automata, i.e., on the finite languages they represent.
DOI 10.1016/S0304-3975(00)00292-9

Using APA 6th Edition citation style.

[Page generation failure. The bibliography processor requires a browser with Javascript enabled.]

Times viewed: 492

Adding this citation to "My List" will allow you to export this citation in other styles.