Minimal cover-automata for finite languages

被引：48

作者：

Câmpeanu, C ^{[1
]}

Sântean, N ^{[1
]}

Yu, S ^{[1
]}

机构：

[1] Univ Western Ontario, Middlesex Coll, Dept Comp Sci, London, ON N6A 5B7, Canada

来源：

THEORETICAL COMPUTER SCIENCE | 2001年 / 267卷 / 1-2期

基金：

加拿大自然科学与工程研究理事会;

关键词：

finite languages; deterministic finite automata; cover language; deterministic cover automata;

D O I：

10.1016/S0304-3975(00)00292-9

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

A cover-automaton A of a finite language L subset of or equal to Sigma* 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. (C) 2001 Elsevier Science B.V. All rights reserved.

引用

页码：3 / 16

页数：14

共 12 条

[1] UNIFORM CHARACTERIZATIONS OF NONUNIFORM COMPLEXITY-MEASURES
BALCAZAR, JL
DIAZ, J
GABARRO, J
[J]. INFORMATION AND CONTROL, 1985, 67 (1-3): : 53 - 69
[2] CAMPEANU C, 1986, REV ROUM LINGUIST, V23, P7
[3] A TIME-COMPLEXITY GAP FOR 2-WAY PROBABILISTIC FINITE-STATE AUTOMATA
DWORK, C
STOCKMEYER, L
[J]. SIAM JOURNAL ON COMPUTING, 1990, 19 (06) : 1011 - 1023
[4] Hopcroft J. E., 2007, Introduction to Automata Theory, Languages and Computation
[5] KANEPS J, 1991, LECT NOTES COMPUT SC, V510, P174
[6] KANEPS J, 1990, LECT NOTES COMPUT SC, V452, P355
[7] PAREDAENS J, 1977, ACTA INFORM, V9, P73, DOI 10.1007/BF00263766
[8] Salomaa A., 1969, THEORY AUTOMATA
[9] SALOMAA K, 1994, THEORET COMPUT SCI, V125, P315
[10] Automaticity .1. Properties of a measure of descriptional complexity
Shallit, J
Breitbart, Y
[J]. JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1996, 53 (01) : 10 - 25

← 1 2 →