IMPROVED LIMITEDNESS THEOREMS ON FINITE AUTOMATA WITH DISTANCE FUNCTIONS

被引：38

作者：

HASHIGUCHI, K ^{[1
]}

机构：

[1] LAB INFORMAT THEOR & PROGRAMMAT, PARIS, FRANCE

来源：

THEORETICAL COMPUTER SCIENCE | 1990年 / 72卷 / 01期

关键词：

D O I：

10.1016/0304-3975(90)90044-I

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Let A be a finite automaton with a distance function, and ID(A) be the set of distances associated with words accepted by A. This paper presents an improved upper bound of ID(A) when the upper limit of ID(A) is finite. It also presents one necessary and sufficient condition concerning (word,+)-expressions for the upper limit of ID(A) to be infinite. © 1990.

引用

页码：27 / 38

页数：12

共 8 条

[1] CHOFFRUT C, 1979, LITP796 RAPP
[2] LIMITEDNESS THEOREM ON FINITE AUTOMATA WITH DISTANCE FUNCTIONS
HASHIGUCHI, K
[J]. JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1982, 24 (02) : 233 - 244
[3] REGULAR LANGUAGES OF STAR HEIGHT ONE
HASHIGUCHI, K
[J]. INFORMATION AND CONTROL, 1982, 53 (03): : 199 - 210
[4] REPRESENTATION THEOREMS ON REGULAR LANGUAGES
HASHIGUCHI, K
[J]. JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1983, 27 (01) : 101 - 115
[5] Hashiguchi K., 1979, Theoretical Computer Science, V8, P69, DOI 10.1016/0304-3975(79)90057-4
[6] LINNA M, 1973, AUTOMATA LANGUAGES P, P87
[7] MASCLE JP, 1986, 13TH P INT COLL AUT
[8] Simon I., 1978, 19th Annual Symposium on Foundations of Computer Science, P143, DOI 10.1109/SFCS.1978.21

← 1 →