Electronic Resource
Springer
Theory of computing systems
26 (1993), S. 169-185
ISSN:
1433-0490
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
Notes:
Abstract A distance automaton is a (nondeterministic finite) automaton which is equipped with a nonnegative cost function on its transitions. The distance of a word recognized by such a machine quantifies the expenses associated with the recognition of this word. The distance of a distance automaton is the maximal distance of a word recognized by this machine or is infinite, depending on whether or not a maximum exists. We present distance automata havingn states and distance 2 n − 2. As a by-product we obtain regular languages having exponential finite order. Given a finitely ambiguous distance automaton withn states, we show that either its distance is at most 3 n − 1, or the growth of the distance in this machine is linear in the input length. The infinite distance problem for these distance automata is NP-hard and solvable in polynomial space. The infinite-order problem for regular languages is PSPACE-complete.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01202281
| Library |
Location |
Call Number |
Volume/Issue/Year |
Availability |
