Decision Problems for Probabilistic Finite Automata on Bounded Languages

• Autorzy: Bell P. C. , Halava V. , Hirvensalo M.
• Języki publikacji: EN

Abstrakty

EN

We show that several problems concerning probabilistic finite automata of a fixed dimension and a fixed number of letters for bounded cut-point and strict cut-point languages are algorithmically undecidable by a reduction of Hilbert’s tenth problem. We then consider the set of so called “F-Problems” (emptiness, infiniteness, containment, disjointness, universe and equivalence) and show that they are also undecidable for bounded (non-)strict cut-point languages on probabilistic finite automata. For a finite set of matrices { M₁ , M₂ , . . . , M_k }⊆ Q ^txt , we then consider the decidability of computing the maximal spectral radius of any matrix in the set X = { M^j1₁ M^j2₂··· M^jk_k|j₁, j₂, . . . , j_k≥0 } , which we call a bounded matrix language. Using an encoding of a probabilistic finite automaton shown in the paper, we prove the surprising result that determining if the maximal spectral radius of a bounded matrix language is less than or equal to one is undecidable, but determining whether it is strictly less than one is in fact decidable (which is similar to a result recently shown for quantum automata).

Słowa kluczowe

EN

probabilistic finite automata; bounded languages; formal power series; undecidability; Hilbert's tenth problem

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2013
• Tom: Vol. 123, nr 1
• Strony: 1--14
• Opis fizyczny: Bibliogr. 28 poz.

Twórcy

autor

Bell P. C.

• Department of Computer Science, Loughborough University Loughborough, LE11 3TU, UK

autor

Halava V.

• TUCS-Turku Centre for Computer Science Department of Mathematics, University of Turku FIN-20014, Turku, Finland

autor

Hirvensalo M.

• TUCS-Turku Centre for Computer Science Department of Mathematics, University of Turku FIN-20014, Turku, Finland

Bibliografia

• [1] Bar-Hillel, Y., Perlis, M., Shamir, E.: On formal properties of simple phrase structure grammars, Zeitschrift f¨ür Phonetik, Sprachwissenschaft und Kommunikationsforschung, 14, 1961, 143–172.
• [2] Bell, P. C., Halava, V., Harju, T., Karhum¨aki, J., Potapov, I.: Matrix equations and Hilbert’s tenth problem, International Journal of Algebra and Computation, 18, 2008, 1231–1241.
• [3] Bell, P. C., Halava, V., Hirvensalo, M.: On the Joint Spectral Radium for Bounded Matrix Languages, 4th Workshop on Reachability Problems, 6227, Springer-Verlag, 2010.
• [4] Berstel, J., Reutenauer, C.: Rational Series and their Languages, Springer-Verlag, 1988.
• [5] Blondel, V., Canterini, V.: Undecidable problems for probabilistic automata of fixed dimension, Theory of Computing Systems, 36, 2003, 231–245.
• [6] Blondel, V., Jeandel, E., Koiran, P., Portier, N.: Decidable and undecidable problems about quantum au¬tomata, SIAM Journal on Computing, 34:6, 2005, 1464–1473.
• [7] Blondel, V., Tsitsiklis, J.: The Lyapunov exponent and joint spectral radius of pairs of matrices are hard - when not impossible – to compute and to approximate, Mathematics of Control, Signals and Systems, Springer, 10, 1997, 31–40.
• [8] Blondel, V., Tsitsiklis, J.: The boundedness of all products of a pair of matrices is undecidable, Systems and Control Letters, Elsevier, 41:2, 2000, 135–140.
• [9] Dang, Z., Ibarra, O., Sun, Z.-W.: On two-way nondeterministic finite automata with one reversal-bounded counter, Theoretical Computer Science, 330(1), 2005, 59–79.
• [10] Daubechies, I., Lagarias, J. C.: Sets of matrices all infinite products of which converge, Linear Algebra and its Applications, 161, 1992, 227–263.
• [11] Davis, M.: Computability and Unsolvability, McGraw-Hill, New York, 1958.
• [12] Egerstedt, M., Blondel, V.: How hard is it to control switched systems?, Proceedings of the American Control Conference, Anchorage, 2002.
• [13] Halava, V., Kari, J., Matiyasevich, Y.: On Post correspondence problem for letter monotonic languages, Theoretical Computer Science, 410(30-32), August 2009, 2957–2960.
• [14] Hirvensalo, M.: Improved undecidability results on the emptiness problem of probabilistic and quantum cut-point languages, SOFSEM 2007: Theory and Practice of Computer Science, Lecture Notes in Computer Science, Springer, 4362, 2007, 309–319.
• [15] Hopcroft, J., Ullman, J.: Formal Languages and their Relation to Automata, Addison-Wesley, Boston, Mass., 1969.
• [16] Horn, R., Johnson, C.: Matrix Analysis, Cambridge University Press, 1990.
• [17] Ibarra, O.: Reversal-bounded multicounter machines and their decision problems, Journal of the ACM, 25:1, 1978, 116–133.
• [18] Ibarra, O., Su, J., Dang, Z., Bultan, T., Kemmerer, R.: Counter machines: decidable properties and applications to verification problems, Lecture Notes in Computer Science, 1893, 2000, 426–435.
• [19] Jones, J. P.: Universal Diophantine equation, The Journal of Symbolic Logic, 47:3, 1982, 549–571.
• [20] Jungers, R.: The Joint Spectral Radius: Theory and Applications, Lecture Notes in Control and Information Sciences, Springer-Verlag, 2009.
• [21] Matiyasevich, Y.: Hilbert’s Tenth Problem, MIT Press, 1993.
• [22] Paz, A.: Introduction to Probabilistic Automata, Academic Press, 1971.
• [23] Rabin, M. O.: Probabilistic automata, Information and Control, 6, 1963, 230–245.
• [24] Renegar, J.: On the computational complexity and geometry of the first-order theory of the reals, parts I, II and III, Journal of Symbolic Computation, 13:3, 1992, 255–352.
• [25] Salomaa, A., Soittola, M.: Automata-Theoretic Aspects of Formal Power Series, Springer-Verlag, 1978.
• [26] Schützenberger, M. P.: On the definition of a family of automata, Information and Control, 4, 1961,245–270.
• [27] Schützenberger, M. P.: On a theorem of R. Jungen, Proceedings of the American Mathematical Society, 13, 1962, 885–890.
• [28] Turakainen, P.: Generalized automata and stochastic languages, Proceedings of the American Mathematical Society21, 1969, 303–309.