Effective optimization with weighted automata on decomposable trees

References

• Blum L, Shub M, Smale S. On a theory of computation and complexity over the real numbers. Bull. Am. Math. Soc. 1989;21:1–46.
   Web of Science ®Google Scholar
• Meer K, Weber G-W. Some aspects of studying an optimization or decision problem in different computational models. Eur. J. Oper. Res. 2002;143:406–418.
   Web of Science ®Google Scholar
• Fabre E, Jezequel L. Distributed optimal planning: an approach by weighted automata calculus. In: Proceedings of the 48th IEEE Conference on Decision and Control, held jointly with the 28th Chinese Control Conference. Shanghai (China): CDC/CCC 2009; 2009. p. 211–216.
   Google Scholar
• Büchi JR. Weak second-order arithmetic and finite automata. Z. Math. Logik Grundlagen Math. 1960;6:66–92.
   Google Scholar
• Elgot CC. Decision problems of finite automata design and related arithmetics. Trans. Amer. Math. Soc. 1961;98:21–52.
   Google Scholar
• Droste M, Gastin P. Weighted automata and weighted logics. Research Report LSV-05-13, Labiratoire Spécification et Vérification, Ecole Normal Supérieure Cachan 61, avenue du Président Wilson 94235 Cachan Cedex France; 2005.
   Google Scholar
• Fülöp Z, Maletti A, Vogler H. A Kleene theorem for weighted tree automata over distributive multioperator monoids; Theor. Comput. Sys. 2009;44:455–499.
   Google Scholar
• Kleene SC. Representation of events in nerve nets and finite automata. In: Shannon CE, McCarthy J, editors. Automata studies. Princeton: Princeton University Press; 1956. p. 3–42.
   Google Scholar
• Droste M, Vogler H. Weighted logics for unranked tree automata. Theor. Comput. Sys. 2009;48:23–47.
   Web of Science ®Google Scholar
• Mandrali E, Rahonis G. Recognizable tree series with discounting. Acta Cybernet. 2009;19:411–439.
   Google Scholar
• Droste M, Meinecke I. Describing average- and longtime-behavior by weighted mso logics. Hlinĕnź P, Kučera A, editors. MFCS 2010, LNCS 6281. Berlin Heidelberg: Springer-Verlag; 2010. p. 537–548.
   Google Scholar
• Droste M, Götze D, Märcker S, Meinecke I. Weighted tree automata over valuation monoids and their characterization by weighted logics. In: Kuich W, Rahonis G, editors. Bozapalidis festschrift, LNCS 7020. Berlin Heidelberg: Springer-Verlag; 2011. p. 30–55.
   Google Scholar
• Droste M, Meinecke I, Šešelja B, Tepavević A. A cascade decomposition of weighted finite transition systems. In: Mauri G, Leporati A, editors. DLT 2011, LNCS 6795. Berlin Heidelberg: Springer-Verlag; 2011. p. 472–473.
   Google Scholar
• Makowsky JA, Ravve EV. Incremental model checking for decomposable structures. Mathematical foundations of computer science (MFCS’95). Vol. 969. Lecturer notes in computer science. Berlin Heidelberg: Springer Verlag; 1995. p. 540–551
   Google Scholar
• Makowsky JA. Compactness, embeddings and definability. Barwise J, Feferman S, editors. Model-theoretic logics, perspectives in mathematical logic, chapter 18. New York (NY): Springer Verlag; 1985.
   Google Scholar
• Feferman S, Vaught R. The first order properties of products of algebraic systems. Fundam. Math. 1959;47:57–103.
   Google Scholar
• Shelah S. The monadic theory of order. Ann. Math. 1975;102:379–419.
   Web of Science ®Google Scholar
• Gurevich Y. Modest theory of short chains. I. J. Symbolic Logic. 1979;44:481–490.
   Web of Science ®Google Scholar
• Shelah S. On the very weak 0–1 law for random graphs with orders. J. Logic Comput. 1996;6:137–159.
   Web of Science ®Google Scholar
• Makowsky JA. Algorithmic uses of the Feferman--Vaught theorem. Ann. Pure Appl. Logic. 2004;126:159–213.
   Web of Science ®Google Scholar
• Bollig B, Gastin P. Weighted versus probabilistic logics. In: Diekert V, Nowotka D, editors. DLT 2009, LNCS R5583. Berlin Heidelberg: Springer-Verlag; 2009. p. 18–38.
   Google Scholar
• Droste M, Gastin P. Weighted automata and weighted logics. Theor. Comput. Sci. 2007;380:69–86.
   Web of Science ®Google Scholar
• Meinecke I. Weighted logics for traces. In: Proceedings of the first international computer science conference on theory and applications, CSR’06. Berlin, Heidelberg: Springer-Verlag; 2006. p. 235–246.
   Google Scholar
• Fichtner I. Weighted picture automata and weighted logics. In: STACS 2006. Marseille (France): Springer; 2006. p. 313–324.
   Google Scholar
• Mathissen C. Definable transductions and weighted logics for texts. In: Proceedings of the 11th International Conference on Developments in Language Theory, DLT’07. Berlin, Heidelberg: Springer-Verlag; 2007. p. 324–336.
   Google Scholar
• Mathissen C. Weighted logics for nested words and algebraic formal power series. In: Proceedings of the 35th International Colloquium on Automata, Languages and Programming, Part II, ICALP ’08. Berlin, Heidelberg: Springer-Verlag; 2008. p. 221–232.
   Google Scholar
• Valiant LG. A bridging model for parallel computation. Commun. ACM. 1990;33:103–111.
   Web of Science ®Google Scholar
• Culler D, Karp R, Patterson D, Sahay A, Schauser KE, Santos E, Subramonian R, Von Eicken T. LogP: towards a realistic model of parallel computation. Vol. 28. In: PPOPP ’93 Proceedings of the fourth ACM SIGPLAN Symposium on Principles and practice of parallel programming. Shenzhen (China); 1993. p. 1–12.
   Google Scholar
• Biggs NL, Damerell RM, Sands DA. Recursive families of graphs. J. Comb. Theory. 1972;12:123–131.
   Google Scholar
• Courcelle B, Makowsky JA. Fusion in relational structures and the verification of monadic second-order properties. Math. Struc. Comp. Sci. April 2002;12:203–235.
   Google Scholar
• Fischer E, Makowsky JA. Linear recurrence relations for graph polynomials. Avron A, Dershowitz N, Rabinovich A, editors. Pillars of computer science. Berlin, Heidelberg: Springer-Verlag; 2008. p. 266–279.
   Google Scholar
• Hickmott S, Rintanen J, Thiébaux S, White L. Planning via Petri net unfolding: Generalization and improvements. In: Proceedings of the 20th International Joint Conference on Artificial Intelligence, IJCAI’07. San Francisco, CA, USA: Morgan Kaufmann Publishers Inc.; 2007. p. 1904–1911.
   Google Scholar
• Bonet B, Haslum P, Hickmott S, Thiébaux S. Transactions on petri nets and other models of concurrency I. chapter directed unfolding of Petri nets. Berlin, Heidelberg: Springer-Verlag; 2008. p. 172–198.
   Google Scholar
• Weber G-W, Uğur Ö, Taylan P, Tezel A. On optimization, dynamics and uncertainty: a tutorial for gene-environment networks. Discrete Appl. Math. 2009;157:2494–2513.
   Web of Science ®Google Scholar
• Weber G-W, Kropat E, Akteke-Öztürk B, Görgülü Z-K. A survey on or and mathematical methods applied on gene-environment networks. Cent. Eur. J. Oper. Res. 2009;17:315–341.
   Web of Science ®Google Scholar
• Weber G-W, Taylan P, Akteke-Öztürk B, Uğur Ö. Mathematical and data mining contributions to dynamics and optimization of gene-environment networks. Electron. J. Theor. Phys. 2007;4:115–146.
   Google Scholar
• Weber G-W, Tezel A, Taylan P, Soyler A, C̣etin M. Mathematical contributions to dynamics and optimization of gene-environment networks. Vol. 57. In: Special Issue. Celebration of Prof. Dr. Hubertus Th. Jongen’s 60th Birthday, of Optimization; 2008. p. 353–377.
   Google Scholar