Decidability, undecidability, and PSPACE-completeness of the twins property in the tropical semiring. (English) Zbl 1282.68123
Summary: We solve a problem already investigated by Mohri in 1997: we show that the twins property for weighted finite automata over the tropical semiring is decidable and PSPACE-complete. We also point out that it is undecidable whether two given states are twins.
MSC:
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
| 68Q45 | Formal languages and automata |
References:
| [1] | Allauzen, C.; Mohri, M., Efficient algorithms for testing the twins property, Journal of Automata, Languages and Combinatorics, 8, 117-144 (2003) · Zbl 1089.68049 |
| [2] | Béal, M. P.; Carton, O.; Prieur, C.; Sakarovitch, J., Squaring transducers. An efficient procedure for deciding functionality and sequentiality, Theoretical Computer Science, 292, 45-63 (2003) · Zbl 1064.68050 |
| [3] | Berstel, J.; Reutenauer, C., (Rational Series and their Languages. Rational Series and their Languages, EATCS Monographs on Theoretical Computer Science, vol. 12 (1984), Springer-Verlag: Springer-Verlag Berlin, Heidelberg, New York) · Zbl 0573.68037 |
| [4] | Berstel, J.; Reutenauer, C., (Noncommutative Rational Series with Applications. Noncommutative Rational Series with Applications, Encyclopedia of Mathematics and its Applications, vol. 137 (2010), Cambridge University Press) |
| [5] | Borchardt, B., A pumping-lemma and decidability problems for recognizable tree series, Acta Cybernetica, 14, 509-544 (2003) · Zbl 1094.68046 |
| [6] | Büchse, M.; May, J.; Vogler, H., Determinization of weighted tree automata using factorizations, Journal of Automata, Languages and Combinatorics, 15 (2010) · Zbl 1345.68201 |
| [7] | Choffrut, C., Une caracterisation des fonctions sequentielles et des fonctions sous-sequentielles en tant que relations rationnelles, Theoretical Computer Science, 5, 325-337 (1977) · Zbl 0376.94022 |
| [8] | (Droste, M.; Kuich, W.; Vogler, H., Handbook of Weighted Automata. Handbook of Weighted Automata, Monographs in Theoretical Computer Science. An EATCS Series (2009), Springer-Verlag) · Zbl 1200.68001 |
| [9] | Gaubert, S., On the Burnside problem for semigroups of matrices in the \((\max, +)\) algebra, Semigroup Forum, 52, 271-292 (1996) · Zbl 0858.20050 |
| [10] | Gaubert, S.; Mairesse, J., Modeling and analysis of timed Petri nets using heaps of pieces, Institute of Electrical and Electronics Engineers. Transactions on Automatic Control, 44, 683-698 (1998) · Zbl 0955.68082 |
| [11] | G. Grahne, A. Thomo, Approximate reasoning in semi-structured databases, in: M. Lenzerini, et al. (Eds.), 8th International Workshop on Knowledge Representation meets Databases, KRDB2001, vol. 45, CEUR Workshop Proceedings.; G. Grahne, A. Thomo, Approximate reasoning in semi-structured databases, in: M. Lenzerini, et al. (Eds.), 8th International Workshop on Knowledge Representation meets Databases, KRDB2001, vol. 45, CEUR Workshop Proceedings. · Zbl 1110.68033 |
| [12] | Hashiguchi, K., Algorithms for determining relative star height and star height, Information and Computation, 78, 124-169 (1988) · Zbl 0668.68081 |
| [13] | Hromkovič, J.; Karhumäki, J.; Klauck, H.; Schnitger, G.; Seibert, S., Communication complexity method for measuring nondeterminism in finite automata, Information and Computation, 172, 202-217 (2002) · Zbl 1009.68067 |
| [14] | Ibarra, O.; Ravikumar, B., On sparseness, ambiguity and other decision problems for acceptors and transducers, (Monien, B.; Vidal-Naquet, G., STACS’86 Proceedings. STACS’86 Proceedings, Lecture Notes in Computer Science, vol. 210 (1986), Springer-Verlag: Springer-Verlag Berlin), 171-179 · Zbl 0605.68080 |
| [15] | D. Kirsten, Distance desert automata and the star height problem, R.A.I.R.O. - Informatique Théorique et Applications, special issue of selected best papers from FoSSaCS 2004, vol. 39, 2005, pp. 455-509.; D. Kirsten, Distance desert automata and the star height problem, R.A.I.R.O. - Informatique Théorique et Applications, special issue of selected best papers from FoSSaCS 2004, vol. 39, 2005, pp. 455-509. · Zbl 1082.20041 |
| [16] | D. Kirsten, Distance desert automata and star height substitutions, Habilitationsschrift, Universität Leipzig, Fakultät für Mathematik und Informatik, 2006.; D. Kirsten, Distance desert automata and star height substitutions, Habilitationsschrift, Universität Leipzig, Fakultät für Mathematik und Informatik, 2006. · Zbl 1111.68057 |
| [17] | D. Kirsten, A Burnside approach to the termination of Mohri’s algorithm for polynomially ambiguous min-plus-automata, R.A.I.R.O. - Informatique Théorique et Applications, special issue on Journées Montoises d’Informatique Théorique 2006, JM’06, 42, 2008, pp. 553-581.; D. Kirsten, A Burnside approach to the termination of Mohri’s algorithm for polynomially ambiguous min-plus-automata, R.A.I.R.O. - Informatique Théorique et Applications, special issue on Journées Montoises d’Informatique Théorique 2006, JM’06, 42, 2008, pp. 553-581. · Zbl 1155.68042 |
| [18] | Kirsten, D.; Lombardy, S., Deciding unambiguity and sequentiality of polynomially ambiguous min-plus automata, (Albers, S.; Marion, J. Y., STACS’09 Proceedings (2009)), 589-600 · Zbl 1236.68172 |
| [19] | Kirsten, D.; Mäurer, I., On the determinization of weighted automata, Journal of Automata, Languages and Combinatorics, 10, 287-312 (2005) · Zbl 1161.68542 |
| [20] | Klimann, I.; Lombardy, S.; Mairesse, J.; Prieur, C., Deciding unambiguity and sequentiality from a finitely ambiguous max-plus automaton, Theoretical Computer Science, 327, 349-373 (2004) · Zbl 1071.68035 |
| [21] | Knight, K.; May, J., A better \(N\)-best list: Practical determinization of weighted finite tree automata, (NACACL-HLT Proceedings (2006), Association for Computational Linguistics), 351-358 |
| [22] | Krob, D., The equality problem for rational series with multiplicities in the tropical semiring is undecidable, International Journal of Algebra and Computation, 4, 405-425 (1994) · Zbl 0834.68058 |
| [23] | Kuich, W.; Salomaa, A., (Semirings, Automata, Languages. Semirings, Automata, Languages, Monographs in Theoretical Computer Science. An EATCS Series, vol. 5 (1986), Springer-Verlag: Springer-Verlag Berlin) · Zbl 0582.68002 |
| [24] | Métivier, Y.; Richomme, G., New results on the star problem in trace monoids, Information and Computation, 119, 240-251 (1995) · Zbl 0832.68074 |
| [25] | Mohri, M., Finite-state transducers in language and speech processing, Computational Linguistics, 23, 269-311 (1997) |
| [26] | M. Mohri, Weighted automata algorithms, Chapter 6 in [8]; M. Mohri, Weighted automata algorithms, Chapter 6 in [8] · Zbl 1484.68092 |
| [27] | Salomaa, A.; Soittola, M., (Automata-Theoretic Aspects of Formal Power Series. Automata-Theoretic Aspects of Formal Power Series, Texts and Monographs on Computer Science (1978), Springer-Verlag: Springer-Verlag Berlin, Heidelberg, New York) · Zbl 0377.68039 |
| [28] | Simon, I., Recognizable sets with multiplicities in the tropical semiring, (Chytil, M. P.; etal., MFCS’88 Proceedings. MFCS’88 Proceedings, Lecture Notes in Computer Science, vol. 324 (1988), Springer-Verlag: Springer-Verlag Berlin), 107-120 · Zbl 0656.68086 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
