Improved limitedness theorems on finite automata with distance functions. (English) Zbl 0693.68031

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


68Q45 Formal languages and automata
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI


[1] Choffrut, Ch., Series rationelles d’image finie, Rapport LITP 79-6 (1979)
[2] Hashiguchi, K., A decision procedure for the order of regular events, Theoret. Comput. Sci., 8, 69-72 (1979) · Zbl 0419.68088
[3] Hashiguchi, K., Limitedness theorem on finite automata with distance functions, J. Comput. System Sci., 24, 233-244 (1982) · Zbl 0513.68051
[4] Hashiguchi, K., Representation theorems on regular languages, J. Comput. System Sci., 27, 101-115 (1983) · Zbl 0516.68063
[5] Hashiguchi, K., Regular languages of star height one, Inform. and Control, 53, 109-210 (1982) · Zbl 0547.68072
[6] Linna, M., Finite power property of regular languages, (Nivat, M., Automata, Languages and Programming (1973), North-Holland: North-Holland Amsterdam), 87-98 · Zbl 0276.02020
[7] Mascle, J. P., Torsion, matrix semigroups and recognizable transductions, Proc. 13th Internat. Coll. on Automata, Languages, and Programming (1986) · Zbl 0624.68066
[8] Simon, I., Limitedness subsets of a free monoid, Proc. 19th Ann. Symp. Foundations of Computer Science, 143-150 (1978)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.