Multi-Valued MSO Logics Over Words and Trees

Droste, M.; Kuich, W.; Rahonis, G.

Artykuł - szczegóły

Tytuł artykułu

Multi-Valued MSO Logics Over Words and Trees

Autorzy

Droste M. , Kuich W. , Rahonis G.

Wybrane pełne teksty z tego czasopisma

https://fi.episciences.org/

Identyfikatory

Warianty tytułu

Języki publikacji

Abstrakty

We introduce multi-valued Büchi and Muller automata over distributive lattices and a multi-valued MSO logic for infinite words. For this logic, we prove the expressive equivalence of w-recognizable and MSO-definable infinitary formal power series over distributive lattices with negation function. Then we consider multi-valued Muller tree automata and a multi-valued MSO logic for trees over distributive lattices. For this logic, we establish a version of Rabin's theorem for infinitary tree series.

Słowa kluczowe

distributive lattice multi-valued automata over infinite over infinite words and trees infinitary formal power series multi-valued MSO logic

Wydawca

IOS Press

Czasopismo

Fundamenta Informaticae

Rocznik

2008

Tom

Vol. 84, nr 3-4

Strony

305--327

Opis fizyczny

bibliogr. 54 poz.

Twórcy

autor

Droste M.

autor

Kuich W.

autor

Rahonis G.

Department of Mathematics, Aristotle University of Thessaloniki, 54124 Thessaloniki, Greece, grahonis@math.auth.gr

Bibliografia

[1] Arnold A.: Finite Transition Systems, International Series in Computer Science, Prentice Hall, 1994.
[2] Berstel J., Reutenauer C: Rational Series and Their Languages, EATCS Monographs in Theoretical Computer Science, vol. 12, Springer-Verlag, 1988.
[3] Berstel J., Reutenauer C: Recognizable formal power series on trees, Theoretical Computer Science, 18(2), 1982,115-148.
[4] Birkhoff G.: Lattice Theory, Revised ed. American Mathematical Society Colloquium Publications, Vol. XXV, American Mathematical Society, Providence, R.I. 1961.
[5] Bollig B., Meinecke I.: Weighted distributed systems and their logics, in: Proceedings ofLFCS 2007, LNCS, 4514, 2007 54-68.
[6] Borchardt B.: The Theory of Recognizable Tree Series, PhD Thesis, Dresden University of Technology, 2004.
[7] Bozapalidis S.: Effective construction of the syntactic algebra of a recognizable series on trees, Acta Informat-ica, 28, 1991,351-363.
[8] Bozapalidis S.: Equational elements in additive algebras, Theory of Computing Systems, 32, 1999, 1-33.
[9] Bozapalidis S., Rahonis G.: On the closure of recognizable tree series under tree homomorphisms. Special issue on "Weighted automata" (M. Droste, H. Vogler, eds.) Journal of Automata Languages and Combinatorics, 10(2/3), 2005,185-202.
[10] Bruns G., Godefroid P.: Model-checking with multi-valued logics, in: Proceedings oflCALP 2004, LNCS, 3142,2004,281-293.
[11] Biichi J.R.: Weak second-order arithmetic and finite automata, Z Math. Logik Grundlagen Math., 6, 1960, 66-92.
[12] Biichi J.R.: On a decision method in restricted second order arithmetic, in: Proc. 1960 Int. Congr. for Logic, Methodology and Philosophy of Science, 1962, 1-11.
[13] Chechik M., Devereux B., Gurfinkel A.: Model-checking infinite state-space systems with fine-grained abstractions using SPIN, Proceedings of SPIN 2001, LNCS, 2057, 2001 16-36.
[14] Davey B.A., Priestley H.A.: Introduction to Lattices and Order, 2nd ed. Cambridge University Press, 2002.
[15] Doner J.: Tree acceptors and some of their applications, Journal of Computer and Systems Sciences, 4, 1970, 406-451.
[16] Droste M., Gastin P.: Weighted automata and weighted logics, Theoretical Computer Science 380, 2007, 69-86; extended abstract in: 32ndICALP, LNCS, 3580, 2005, 513-525.
[17] Droste M., Kuich W., Vogler H. (eds): Handbook of Weighted Automata, EATCS Monographs in Theoretical Computer Science, Springer-Verlag, in preparation.
[18] Droste M., Pech C, Vogler H.: A Kleene theorem for weighted tree automata, Theory of Computing Systems, 38, 2005, 1-38.
[19] Droste M., Rahonis G.: Weighted automata and weighted logics on infinite words. Special issue on Workshop on words and automata, WOWA 2006 (M. Volkov, ed.) Russian Mathematics (Iz. VUZ), to appear; extended abstract in: Proceedings of DLT'06, LNCS, 4036, 2006, 49-58.
[20] Droste M., Rahonis G.: Weighted automata and weighted logics with discounting, in: Proceedings of CIAA 2007, LNCS, 4783, 2007, 73-84.
[21] Droste M., Vogler H.: Weighted tree automata and weighted logics, Theoretical Computer Science, 366, 2006, 228-247.
[22] Droste M., Vogler H.: Weighted logics for XML. Preprint.
[23] Eilenberg S.: Automata, Languages and Machines, vol. A, Academic Press, 1974.
[24] Elgot C: Decision problems of finite automata design and related arithmetics, Transactions of the American Mathematical Society, 98, 1961, 21-52.
[25] Esik Z., Kuich W: Formal tree series, Journal of Automata, Languages and Combinatorics, 8(2), 2003, 219-285.
[26] Esik Z., Kuich W: A semiring-semimodule generalization of o;-regular languages I. Special issue on "Weighted automata" (M. Droste, H. Vogler, eds.) Journal of Automata Languages and Combinatorics, 10, 2005, 203-242.
[27] Esik Z., Kuich W.: A semiring-semimodule generalization of o>-regular languages II. Special issue on "Weighted automata" (M. Droste, H. Vogler, eds.) Journal of Automata Languages and Combinatorics, 10, 2005, 243-264.
[28] Esik Z., Kuich W: Modern Automata Theory, http://www.dmg.tuwien.ac.at/kuich/matl5.ps
[29] Fainekos G.: An Introduction to Multi-Valued Model Checking, http://www.seas.upenn.edu/~faikekos/pub/fainekos_wpell.pdf.
[30] Fichtner I. (nee Maurer): Characterizations of Recognizable Picture Series, PhD Thesis, Leipzig University, 2006.
[31] Golan S.: Semirings and their Applications, Kluwer Academic Publishers, 1999.
[32] Gurfinkel A., Chechik M.: Multi-valued model checking via classical model checking, in: Proceedings of CONCUR 2003, LNCS , 2761, 2003, 266-280.
[33] Kuich W.: Semirings and formal power series: Their relevance to formal languages and automata theory, in: Handbook of Formal Languages (G. Rozenberg, A. Salomaa, eds.), vol. 1, Springer, 1997, 609-677.
[34] Kuich W: Formal power series on trees, in: Proceedings of DLT'97, (S. Bozapalidis, ed.), Aristotle University of Thessaloniki, Thessaloniki 1997,61-101.
[35] Kuich W, Rahonis G.: Fuzzy regular languages over finite and infinite words, Fuzzy Sets and Systems, 157, 2006,1532-1549.
[36] Kuich W., Salomaa A.: Semirings, Automata, Languages, EATCS Monographs in Theoretical Computer Science, vol. 5, Springer-Verlag, 1986.
[37] Kupferman O., Lustig Y.: Lattice automata, in: Proceedings ofVMCAI2007, LNCS, 4349, 2007, 199-213.
[38] Kurshan R.P.: Computer-Aided Verification of Coordinating Processes, Princeton Series in Computer Science, Princeton University Press, 1994.
[39] Mathissen C: Definable transductions and weighted logics for texts, in: Proceedings of DLT 2007, LNCS, 4588, 2007, 324-336.
[40] Maurer I.: Weighted picture automata and weighted logics, in: Proceedings of STACS 2006, LNCS, 3884, 2006,313-324.
[41] McMillan K.: Symbolic Model Checking, Kluwer Academic Publishers, 1993.
[42] Meinecke I.: Weighted logics for traces, in: Proceedings of CSR 2006, LNCS 3967, 2006, 235-246.
[43] Mordeson J., Malik D.: Fuzzy Automata and Languages: Theory and Applications, Chapman & Hall, CRC Boca Raton, London, New York, Washington, DC, 2002.
[44] Pech C: Kleene-Type Results for Weighted Tree Automata, PhD Thesis, Dresden University of Technology, 2003.
[45] Perrin D., Pin J.E.: Infinite Words, Elsevier 2004.
[46] Rabin M.O.: Decidability of second-order theories and automata on infinite trees, Transactions of the American Mathematical Society, 141, 1969,1-35.
[47] Rahonis G.: Infinite fuzzy computations, Fuzzy Sets and Systems, 153, 2005, 275-288.
[48] Rahonis G.: Weighted Muller tree automata and weighted logics. Special issue on "Weighted automata" (M. Droste, H. Vogler, eds.) Journal of Automata Languages and Combinatorics, in press.
[49] Salomaa A., Soittola M.: Automata-Theoretic Aspects of Formal Power Series, Texts and Monographs in Computer Science, Springer-Verlag, 1978.
[50] Schiitzenberger M.: On the definition of a family of automata, Information and Control, 4, 1961, 245-270.
[51] Seidl H.: Finite tree automata with cost functions, Theoretical Computer Science, 126(1), 1994, 113-142.
[52] Thatcher J.W., Wright J.B.: Generalized finite automata theory with application to a decision problem of second-order logic, Mathematical Systems Theory, 2(1), 1968, 57-81.
[53] Thomas W: Automata on infinite objects, in: Handbook of Theoretical Computer Science, vol. B (J. v. Leeuwen, ed.), Elsevier Science Publishers, Amsterdam 1990, 135-191.
[54] Thomas W.: Languages, automata and logic, in: Handbook of Formal Languages (G. Rozenberg, A. Salomaa, eds.), vol. 3, Springer, 1997, 389-485.

Typ dokumentu

Bibliografia

Identyfikator YADDA

bwmeta1.element.baztech-article-BUS5-0015-0076