Relative Nondeterministic Information Logic is EXPTIME-complete

• Autorzy: Demri S. , Orłowska E.
• Języki publikacji: EN

Abstrakty

EN

We define a relative version of the logic NIL introduced by Or owska, Pawlak and Vakarelov and we show that its satisfiability is not only decidable but also EXPTIME-complete. Such a logic combines two ingredients that are seldom present simultaneously in information logics: frame conditions involving more than one information relation and relative frames. The EXPTIMEupper bound is obtained by designing a well-suited decision procedure based on the nonemptiness problem of Büchi automata on infinite trees. The paper provides evidence that Büchi automata on infinite trees are crucial language acceptors even for relative information logics with multiple types of relations.

Słowa kluczowe

EN

information logic; relative frame; computational complexity; Büchi tree automaton

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2007
• Tom: Vol. 75, nr 1-4
• Strony: 163--178
• Opis fizyczny: bibliogr. 33 poz.

Twórcy

autor

Demri S.

autor

Orłowska E.

• Lab.Spécification et Vérification, CNRS & INRIA Futurs & ENS de Cachan 61, Av.Pdt. Wilson, 94235 Cachan Cedex, France,

Bibliografia

• [1] Balbiani, P.: Modal logics with relative accessibility relations, Conference on Formal and Applied Practical Reasoning (D. Gabbay, H. Ohlbach, Eds.), Lecture Notes in Computer Science, vol. 1085 of Lecture Notes in Computer Science, Springer, 1996, 29-41.
• [2] Balbiani, P., Orłowska, E.: A hierarchy of modal logics with relative accessibility relations, Journal of Applied Non-Classsical Logics, 9(2-3), 1999, 303-328, Special issue in the memory of George Gargov.
• [3] Chen, C., Lin, I.: The complexity of propositional modal theories and the complexity of consistency of propositional modal theories, LFCS-3, St. Petersburg (A. Nerode, Y. Matiyasevich, Eds.), Lecture Notes in Computer Science, vol. 813 of Lecture Notes in Computer Science, Springer, 1994, 69-80.
• [4] Demri, S.: The Nondeterministic Information Logic NIL is PSPACE-complete, Fundamenta Informaticae, 42(3-4), 2000, 211-234.
• [5] Demri, S., Gabbay, D.: On modal logics characterized by models with relative accessibility relations: Part I, Studia Logica, 65(3), 2000, 323-353.
• [6] Demri, S., Konikowska, E.: Relative similarity logics are decidable: reduction to FO2 with equality, JELIA'98, Lecture Notes in Artificial Intelligence, vol. 1489 of Lecture Notes in Artificial Intelligence, Springer, 1998, 279-293.
• [7] Demri, S., Orlowska, E.: Incomplete Information: Structure, Inference, Complexity, EATCS Monographs, Springer, Berlin, 2002.
• [8] Demri, S., Sattler, U.: Automata-theoretic decision procedures for information logics, Fundamenta Informaticae, 53(1), 2002, 1-22.
• [9] Emerson, A., Jutla, C.: The complexity of Tree Automata and logics of programs, 29th Annual Symposium on Foundations of Computer Science, IEEE Computer Society Press, 1988, 328-337.
• [10] Fischer,M., Ladner, R.: Propositional Dynamic Logic of Regular Programs, Journal of Computer and System Sciences, 18, 1979, 194-211.
• [11] Hemaspaandra, E.: The price of Universality, Notre Dame Journal of Formal Logic, 37(2), 1996, 173-203.
• [12] Konikowska, B.: A logic for reasoning about relative similarity, Studia Logica, 58(1), 1997, 185-226.
• [13] Konikowska, B.: A logic for reasoning about similarity, [23], 1998, 462-491.
• [14] Ladner, R.: The computational complexity of provability in systems of modal propositional logic, SIAM Journal of Computing, 6(3), 1977, 467-480.
• [15] Lutz, C., Sattler, U.: The complexity of reasoning with Boolean Modal Logics, Advances in Modal Logics 2000, Volume 3, World Scientific, 2002, 329-348.
• [16] Marek, W., Pawlak, Z.: Mathematical foundations of information storage and retrieval, Part I: CC PAS Reports 135, Part II: CC PAS Reports 136, Part III: CC PAS Reports 137, 1973.
• [17] Marek, W., Pawlak, Z.: Information storage and retrieval system - mathematical foundation, Technical Report 149, CC PAS, Warsaw, 1974.
• [18] Marek, W., Pawlak, Z.: Information storage and retrieval system - mathematical foundations, Theoretical Computer Science, 1, 1976, 331-354.
• [19] Orłowska, E.: Logic approach to information systems, Technical Report 437, Institute of Computer Science, Polish Academy of Sciences, Warsaw, 1981.
• [20] Orłowska, E.: Semantics of vague concepts, Technical Report 469, Institute of Computer Science, Polish Academy of Sciences, Warsaw, 1982.
• [21] Orłowska, E.: Semantics of vague concepts, Foundations of Logic and Linguistics. Problems and Solutions. Selected contributions to the 7th International Congress of Logic, Methodology, and Philosophy of Science, Salzburg, Austria (G. Dorn, P. Weingartner, Eds.), Plenum, London, New York, 1983, 465-482.
• [22] Orłowska, E.: Logic of indiscernibility relations, 5th Symposium on Computation Theory, Zaborów, Poland (A. Skowron, Ed.), Lecture Notes in Computer Science, vol. 208 of Lecture Notes in Computer Science, Springer, 1984, 177-186.
• [23] Orłowska, E., Ed.: Incomplete Information: Rough Set Analysis, Studies in Fuzziness and Soft Computing, Physica, Heidelberg, 1998.
• [24] Orłowska, E., Pawlak, Z.: Representation of nondeterministic information, Theoretical Computer Science, 29, 1984, 27-39.
• [25] Pawlak, Z.: Information systems, Technical Report 338, Institute of Computer Science, Polish Academy of Sciences, Warsaw, 1978.
• [26] Pawlak, Z.: Information systems theoretical foundations, Information Systems, 6(3), 1981, 205-218.
• [27] Rabin, M.: Weakly definable relations and special automata, Symposium on Mathematical Logic and Foundations of Set Theory (Y. Bar-Hillel, Ed.), North-Holland, 1970, 1-23.
• [28] Spaan, E.: Complexity of Modal Logics, Ph.D. Thesis, ILLC, Amsterdam University, 1993.
• [29] Stepaniuk, J.: Rough Relations and Logics, in L. Polkowski, A. Skowron (Eds.), Rough Sets in Knowledge Discovery 1. Methodology and Applications, Physica-Verlag, Heidelberg 1998, 248-260.
• [30] Vakarelov, D.: Abstract characterization of some knowledge representation systems and the logic NIL of nondeterministic information, Artificial Intelligence: Methodology, Systems, Applications (P. Jorrand, V. Sgurev, Eds.), North-Holland, 1987, 255-260.
• [31] Vakarelov, D.: Modal logics for knowledge representation systems, Theoretical Computer Science, 90, 1991, 433-456.
• [32] Vakarelov, D.: Information Systems, Similarity and Modal Logics, [23], 1998, 492-550.
• [33] Vardi, M., Wolper, P.: Automata-theoretic techniques for modal logics of programs, Journal of Computer and System Sciences, 32, 1986, 183-221.