×

zbMATH — the first resource for mathematics

Finite-valued distance automata. (English) Zbl 0938.68709

MSC:
68Q45 Formal languages and automata
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Aho, A.; Hopcroft, J.; Ullman, J.: The design and analysis of computer algorithms. (1974) · Zbl 0326.68005
[2] Balcázar, J.; Díaz, J.; Gabarró, J.: Structural complexity. (1988) · Zbl 0638.68040
[3] Garey, M.; Johnson, D.: Computers and intractability. (1979) · Zbl 0411.68039
[4] Gohon, P.: Automates de coût borné sur un alphabet à une lettre. RAIRO inform. Théor. 19, 351-357 (1985) · Zbl 0578.68044
[5] Goldstine, J.; Leung, H.; Wotschke, D.: On the relation between ambiguity and nondeterminism in finite automata. Inform. and comput. 100, 261-270 (1992) · Zbl 0752.68056
[6] Gurari, E.; Ibarra, O.: The complexity of decision problems for finite-turn multicounter machines. J. comput. System sci. 22, 220-229 (1981) · Zbl 0458.68011
[7] Gurari, E.; Ibarra, O.: A note on finite-valued and finitely ambiguous transducers. Math. systems theory 16, 61-66 (1983) · Zbl 0502.68022
[8] Hashiguchi, K.: Limitedness theorem on finite automata with distance functions. J. comput. System sci. 24, 233-244 (1982) · Zbl 0513.68051
[9] Hashiguchi, K.: Improved limitedness theorems on finite automata with distance functions. Theoret. comput. Sci. 72, 27-38 (1990) · Zbl 0693.68031
[10] Hopcroft, J.; Ullman, J.: Introduction to automata theory, languages, and computation. (1979) · Zbl 0426.68001
[11] Ibaraki, T.: Finite automata having cost functions: nondeterministic models. Inform. and control 37, 40-69 (1978) · Zbl 0382.68053
[12] D. Krob, The equality problem for rational series with multiplicities in the tropical semiring is undecidable, Internat. J. Alg. and Comput., to appear. · Zbl 0834.68058
[13] Krob, D.: Some consequences of a Fatou property of the tropical semiring. J. pure appl. Algebra 93, 231-249 (1994) · Zbl 0806.68083
[14] Leung, H.: An algebraic method for solving decision problems in finite automata theory. Ph.d. thesis (1987)
[15] Leung, H.: Limitedness theorem on finite automata with distance functions: an algebraic proof. Theoret. comput. Sci. 81, 137-145 (1991) · Zbl 0729.68049
[16] Leung, H.: On some decision problems in finite automata. Monoids and semigroups with applications, 509-526 (1991) · Zbl 0796.20062
[17] Leung, H.: A note on finitely ambiguous distance automata. Inform. process. Lett. 44, 329-331 (1992) · Zbl 0796.68150
[18] Leung, H.: On finite automata with limited nondeterminism. Lecture notes in computer science 629, 355-363 (1992)
[19] Simon, I.: Limited subsets of a free monoid. Proc. 19th IEEE FOCS, 143-150 (1978)
[20] Simon, I.: Recognizable sets with multiplicities in the tropical semiring. Lecture notes in computer science 324, 107-120 (1988)
[21] Simon, I.: On semigroups of matrices over the tropical semiring. Tech. report RT-MAC-8907 (1989)
[22] Simon, I.: The nondeterministic complexity of a finite automaton. Mots, 384-400 (1990)
[23] Weber, A.: On the valuedness of finite transducers. Acta inform. 27, 749-780 (1990) · Zbl 0672.68027
[24] Weber, A.: Distance automata having large finite distance or finite ambiguity. Math. systems theory 26, 169-185 (1993) · Zbl 0771.68088
[25] Weber, A.: Decomposing a k-valued transducer into k unambiguous ones. Lecture notes in computer science 583, 503-515 (1992)
[26] Weber, A.: Exponential upper and lower bounds for the order of a regular language. Theoret. comput. Sci. 134, 253-262 (1994) · Zbl 0823.68049
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.