The Supports of Weighted Unranked Tree Automata

• Autorzy: Droste M. , Heusel D.

Identyfikatory

DOI

10.3233/FI-2015-1143

• Języki publikacji: EN

Abstrakty

EN

We investigate the supports of weighted unranked tree automata. Our main result states that the support of a weighted unranked tree automaton over a zero-sum free, commutative strong bimonoid is recognizable. For this, we use methods of Kirsten (DLT 2009), in particular, his construction of finite automata recognizing the supports of weighted automata on strings over zero-sum free, commutative semirings. We also get an effective construction of a finite tree automaton recognizing the support of a given weighted unranked tree automaton for zero-sum free, commutative strong bimonoids where Kirsten’s zero generation problem is decidable. In addition, we give a translation of nested weighted automata into weighted unranked tree automata for arbitrary commutative strong bimonoids. As a consequence,we derive analogous results for the supports of nested weighted automata. Finally, we give similar results for the supports of weighted pushdown automata.

Słowa kluczowe

EN

machine theory; robots; mathematical models; recursive functions; artificial intelligence

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2015
• Tom: Vol. 136, nr 1/2
• Strony: 37--58
• Opis fizyczny: Bibliogr. 34 poz.

Twórcy

autor

Droste M.

• Institut für Informatik, Universität Leipzig D-04109 Leipzig, Germany

autor

Heusel D.

• Institut für Informatik, Universität Leipzig D-04109 Leipzig, Germany

Bibliografia

• [1] Berstel, J., Reutenauer, C.: Rational Series and Their Languages, vol. 12 of EATCS Monographs on Theoretical Computer Science, Springer, 1988.
• [2] Bollig, B., Gastin, P., Monmege, B., Zeitoun, M.: Pebble weighted automata and transitive closure logics, in: International Colloquium on Automata, Languages, and Programming (S. Abramsky, C. Gavoille, C. Kirchner, F. Meyer auf der Heide, P. Spirakis, Eds.), vol. 6199 of LNCS, Springer, 2010, 587–598.
• [3] Brüggemann-Klein, A., Murata, M., Wood, D.: Regular tree and regular hedge languages over unranked alphabets: version 1, Technical Report HKUST-TCSC-2001-0, The Hongkong University of Science and Technology, 2001.
• [4] Brüggemann-Klein, A., Wood, D.: Regular tree languages over non-ranked alphabets, Available at http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.50.5397, 1998.
• [5] Büchi, J. R.: Weak second-order arithmetic and finite automata, Zeitschrift für mathematische Logik und Grundlagen der Mathematik, 6, 1960, 66–92.
• [6] Bukharaev, R. G.: Theorie der stochastischen Automaten, Leitfäden der Informatik, Teubner, 1995.
• [7] Comon, H., Dauchet, M., Gilleron, R., Löding, C., Jacquemard, F., Lugiez, D., Tison, S., Tommasi,M.: Tree automata techniques and applications, Available at http://www.grappa.univ-lille3.fr/tata, 2007.
• [8] Droste,M., Götze, D.: The support of nested weighted automata, in: Non-Classical Models of Automata and Applications (S. Bensch, F. Drewes, R. Freund, F. Otto, Eds.), Österreichische Computer Gesellschaft, 2013, 101–116.
• [9] Droste, M., Götze, D., Märcker, S., Meinecke, I.: Weighted tree automata over valuation monoids and their characterization by weighted logics, in: Algebraic Foundations in Computer Science (W. Kuich, G. Rahonis, Eds.), vol. 7020 of LNCS, Springer, 2011, 30–55.
• [10] Droste, M., Kuich,W., Vogler, H., Eds.: Handbook of Weighted Automata, EATCS Monographs on Theoretical Computer Science, Springer, 2009.
• [11] Droste, M., Stüber, T., Vogler, H.: Weighted finite automata over strong bimonoids, Information Sciences, 180, 2010, 156–166.
• [12] Droste, M., Vogler, H.: Weighted logics for XML, 2008, Manuscript.
• [13] Droste, M., Vogler, H.: Weighted logics for unranked tree automata, Theory of Computing Systems, 48(1), 2011, 23–47.
• [14] Droste, M., Vogler, H.: Weighted automata and multi-valued logics over arbitrary bounded lattices, Theoretical Computer Science, 418, 2012, 14–36.
• [15] Droste, M., Vogler, H.: The Chomsky-Schützenberger theorem for quantitative context-free languages, in: Developments in Language Theory (M.-P. Béal, O. Carton, Eds.), vol. 7907 of LNCS, Springer, 2013, 203–214.
• [16] Eilenberg, S.: Automata, Languages, and Machines - Volume A, vol. 59 of Pure and Applied Mathematics, Academic Press, 1974.
• [17] Elgot, C. C.: Decision problems of finite automata design and related arithmetics, Transactions of the American Mathematical Society, 98, 1961, 21–52.
• [18] Golan, J. S.: Semirings and Their Applications, Springer, 1999.
• [19] Gottwald, S.: A Treatise on Many-Valued Logics, Studies in Logic and Computation, Research Studies Press, 2001.
• [20] Grätzer, G.: General Lattice Theory, Second edition, Birkhäuser Verlag, 2003.
• [21] Högberg, J., Maletti, A., Vogler, H.: Bisimulation minimisation of weighted automata on unranked trees, Fundamenta Informaticae, 92, 2009, 103–130.
• [22] Kirsten, D.: An algebraic characterization of semirings for which the support of every recognizable series is recognizable, in: Mathematical Foundations of Computer Science (R. Královic, D. Niwinski, Eds.), vol. 5734 of LNCS, Springer, 2009, 489–500.
• [23] Kirsten, D.: The support of a recognizable series over a zero-sumfree, commutative semiring is recognizable, Acta Cybernetica, 20, 2011, 211–221. Extended abstract in DLT 2009.
• [24] Kreuzer, M., Robbiano, L.: Computational Commutative Algebra 1, Springer, 2008.
• [25] Kuich, W., Salomaa, A.: Semirings, Automata, Languages, vol. 5 of EATCS Monographs on Theoretical Computer Science, Springer, 1986.
• [26] Libkin, L.: Logics for unranked trees: an overview, in: Automata, Languages and Programming (L. Caires, G. F. Italiano, L. Monteiro, C. Palamidessi, M. Yung, Eds.), vol. 3580 of LNCS, Springer, 2005, 35–50.
• [27] Murata, M.: Forest-regular languages and tree-regular languages, 1995, Unpublished manuscript.
• [28] Neven, F.: Automata, logic, and XML, in: Computer Science Logic (J. C. Bradfield, Ed.), vol. 2471 of LNCS, Springer, 2002, 2–26.
• [29] Paz, A.: Introduction to Probabilistic Automata, Computer science and applied mathematics, Academic Press, 1971.
• [30] Radovanovic, D.: Weighted tree automata over strong bimonoids, Novi Sad Journal of Mathematics, 40, 2010, 89–108.
• [31] Salomaa, A., Soittola, M.: Automata-Theoretic Aspects of Formal Power Series, Texts and Monographs in Computer Science, Springer, 1978.
• [32] Tan, T.: Extending two-variable logic on data trees with order on data values and its automata, ACM Transactions on Computational Logic, 15, 2014, 8:1–8:39.
• [33] Thatcher, J. W.: Characterizing derivation trees of context-free grammars through a generalization of finite automata theory, Journal of Computer and System Sciences, 1, 1967, 317–322.
• [34] Veanes, M., Bjørner, N.: Symbolic Tree Transducers, in: Ershov Memorial Conference (E. M. Clarke, I. Virbitskaite, A. Voronkov, Eds.), vol. 7162 of LNCS, Springer, 2011, 377–393.