Limitedness theorem on finite automata with distance functions: An algebraic proof. (English) Zbl 0729.68049

A distance function on a finite automaton is a function assigning to each transition a nonnegative integer. To a sequence of transitions is then assigned the sum of the corresponding integers, and to a word w accepted by the automaton is assigned the number d(w) which is the minimum of all these integers corresponding to accepting paths for w. The problem of deciding whether d(w), w accepted, is bounded was solved by Hashiguchi. The author gives an algebraic proof of this result, by considering some exotic semiring introduced by Simon. Complexity results are also deduced: the author’s algorithm is in \(2^{0(n^ 2)}\), with \(n=number\) of states, for the time, and PSPACE-hard.


68Q70 Algebraic theory of languages and automata
Full Text: DOI


[1] Aho, A.V.; Hopcroft, J.E.; Ullman, J.D., The design and analysis of computer algorithms, (1974), Addison-Wesley Reading, MA · Zbl 0207.01701
[2] Berstel, J., Transductions and context-free languages, (1979), Teubner Stuttgart · Zbl 0424.68040
[3] Fischer, P.C.; Rosenberg, A.L., Multitape one-way nonwriting automata, J. comput. system sci., 2, 88-101, (1968) · Zbl 0159.01504
[4] Gibbons, A.; Rytter, W., On the decidability of some problems about rational subsets of free partially commutative monoids, Theoret. comput. sci., 48, 329-337, (1986) · Zbl 0638.68084
[5] J. Goldstine, C.M.R. Kintala and D. Wotschke, On measuring nondeterminism in regular languages, Inform. and Comput., to appear. · Zbl 0698.68068
[6] Hashiguchi, K., Limitedness theorem on finite automata with distance functions, J. comput. system sci., 24, 233-244, (1982) · Zbl 0513.68051
[7] Hashiguchi, K., Representation theorems on regular languages, J. comput. system sci., 27, 101-115, (1983) · Zbl 0516.68063
[8] Hashiguchi, K., Regular languages of star height one, Inform. and control, 53, 199-210, (1982) · Zbl 0547.68072
[9] Hashiguchi, K., Improved limitedness theorem on finite automata with distance functions, Theoret. comput. sci., 72, 27-38, (1990) · Zbl 0693.68031
[10] Leung, H., On the topological structure of a finitely generated semigroup of matrices, Semigroup forum, 37, 273-287, (1988) · Zbl 0646.20056
[11] Simon, I., Limited subsets of a free monoid, Proc. nineteenth ann. IEEE symp. on 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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.