Automates de coût borné sur un alphabet à une lettre. (French) Zbl 0578.68044

Summary: Let A be an automaton with n states on a single letter alphabet and having a cost function (called ”distance function” by K. Hashiguchi). If its cost c(A) is bounded, then \(c(A)<n^ 2\). Moreover, this bound is asymptotically optimal in the sense that there exists a family \(\{A_ n\}\) of automata, where \(A_ n\) has n states and such that \(\lim_{n\to +\infty}c(A_ n)/n^ 2=1\).


68Q45 Formal languages and automata
Full Text: EuDML


[1] 1. S. EILENBERG, Automata, Languages and Machines, Academic Press, Vol. A, 1974. Zbl0317.94045 · Zbl 0317.94045
[2] 2. K. HASHIGUCHI, Limitedness Theorem on Finite Automata with Distance Functions, J. Comp. Syst Sc., Vol. 24, 1982, p. 233-244. Zbl0513.68051 MR661652 · Zbl 0513.68051
[3] 3. G. MARKOWSKY, Bounds on the Index and Period of a Binary Relation on a finite Set, Semigroup Forum, Vol. 13, 1977, p. 253-259. Zbl0353.20055 MR446762 · Zbl 0353.20055
[4] 4. E. SELMER, On the Linear Diophantine Problem of Frobenius, J. reine angew. Math., Vol. 293/294, 1977, p. 1-17. Zbl0349.10009 MR441855 · Zbl 0349.10009
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.