Improved limitedness theorems on finite automata with distance functions (Q908702)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Improved limitedness theorems on finite automata with distance functions
scientific article

    Statements

    Improved limitedness theorems on finite automata with distance functions (English)
    0 references
    1990
    0 references
    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.
    0 references
    0 references
    finite automaton
    0 references
    distance function
    0 references
    upper bound
    0 references
    0 references