Limitedness theorem on finite automata with distance functions: An algebraic proof
type: Item
instance of: scholarly article
title: Limitedness theorem on finite automata with distance functions: An algebraic proof
zbMATH Open document ID: 0729.68049
DOI: 10.1016/0304-3975(91)90321-R
published in: Theoretical Computer Science
publication date: 1991-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68Q70
zbMATH DE Number: 4206004
zbMATH Keywords: automata
zbMATH Keywords: distance function
author: Hing-Man Leung
reviewed by: Christophe Reutenauer
MaRDI profile type: Publication
cites work: On the computational power of pushdown automata
cites work: Q3859267
cites work: Multitape one-way nonwriting automata
cites work: On the decidability of some problems about rational subsets of free partially commutative monoids
cites work: On measuring nondeterminism in regular languages
cites work: Limitedness theorem on finite automata with distance functions
cites work: Representation theorems on regular languages
cites work: Regular languages of star height one
cites work: Improved limitedness theorems on finite automata with distance functions
cites work: On the topological structure of a finitely generated semigroup of matrices
description: scientific article; zbMATH DE number 4206004