ISSN:
1432-0525
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
Notes:
Summary This paper investigates some problems which change their status from being unsolvable to solvable when varying the values of parameters. Let EMPTY(n, k) be the problem to decide for all rational probabilistic acceptors B with at most n states and k input symbols and for all rational numbers λ, whether the accepted language L(B,λ) is empty. It turns out that EMPTY(2, k) is solvable for all k, while EMPTY (9,9) and EMPTY (65,2) are not. Some problems of the theory of ℤ-rational power series are shown to be unsolvable, too, even for small values of the problemparameters.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF00261257
Permalink