Structures with Multirelations, their Discrete Dualities and Applications

• Autorzy: Düntsch I. , Orłowska E. , Rewitzky I.
• Języki publikacji: EN

Abstrakty

EN

In this paper we show that the problem of discrete duality can be extended beyond the clasical setting of duality between a class of algebras and a class of relational structures. Namely, for some classes of algebras, the relevant dual structures are the structures with multirelations. Several applications of multirelations will be described.

Słowa kluczowe

EN

apartness space; dependency; discrete duality; game of choice; multirelation; nearness space; neighbourhood system; point-set relation; skill relation

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2010
• Tom: Vol. 100, nr 1/4
• Strony: 77--98
• Opis fizyczny: . Bibliogr. 59 poz.

Twórcy

autor

Düntsch I.

autor

Orłowska E.

autor

Rewitzky I.

• National Institute of Telecommunications, Szachowa St.1, 04-894 Warsaw, Poland,

Bibliografia

• [1] M. Aiello and J. van Benthem. Logical patterns in space. In D. I. Beaver, J. van Benthem, and D. Barker-Plummer, editors, Words, Proofs and Diagrams, pages 5-25. CSLI Stanford, 2002.
• [2] R.J.R. Back and J. von Wright. Games and winning strategies. Information Processing Letters, 53(3):165-172, 1995.
• [3] R.J.R. Back and J. vonWright. Refinement Calclulus: A Systematic Introduction.Graduate Texts in ComputerScience. Springer-Verlag, 1998.
• [4] E. Bishop. Foundations of Constructive Mathematics. McGraw-Hill, New York, 1967.
• [5] D. Bridges and L. Vıta. A constructive theory of point-set nearness. CDMTCS 159, Department of Mathematics and Statistics, University of Canterbury, 2001.
• [6] D. Bridges and L. Vıta. Apartness spaces as a framework for constructive topology. Annals of Pure and Applied Logic, 119:61-83, 2003.
• [7] C. Brink. Second-order Boolean algebras. Quaestiones Mathematicae, 7:93-100, 1984.
• [8] C. Brink. Power structures. Algebra Universalis, 30:177-216, 1993.
• [9] C. Brink and I. Rewitzky. A Paradigm for Program Semantics: Power Structures and Duality. CSLI, 2001.
• [10] B. Chellas. Modal Logic. An Introduction. Cambridge University Press, 1980.
• [11] R. Cignoli, S. Laflace, and A. Petrovich. Remarks on Priestley duality for distributive lattices. Order, 8:299-315, 1991.
• [12] J.P. Doignon. Knowledge spaces and skill assignments. In G. Fischer and D. Laming, editors, Contributions to Mathematical Psychology, Psychometrics, and Methodology. Springer, Berlin, 1994.
• [13] J.P. Doignon and J.C. Falmagne. Spaces for the assessment of knowledge. International Journal of Man-Machine Studies, 23:175-196, 1985.
• [14] K. Došen. Duality between modal algebras and neighbourhood frames. Studia Logica, 48(2):219-234, 1989.
• [15] I. Düntsch and G. Gediga. Skills and knowledge structures. British Journal of Mathematical and Statistical Psychology, 48:9-27, 1995.
• [16] I. Düntsch and E. Orłowska. Beyond modalities: sufficiency and mixed algebras. In E. Orłowska and A. Szalas, editors, Relational Methods for Computer Science Applications, pages 263-285. Physica, Heidelberg, 2001.
• [17] I. Düntsch and E. Orłowska. A discrete duality between the apartness algebras and apartness frames. Journal of Applied Non-classical Logics, 18(2-3):209-223, 2008.
• [18] I. Düntsch, E. Orłowska, and A. Radzikowska. Lattice-based relation algebras II. Lecture Notes in Artificial Intelligence, 4342:267-289, 2006.
• [19] I. Düntsch, E. Orłowska, A. Radzikowska, and D. Vakarelov. Relational representation theorems for some lattice-based structures. Journal of Relational Methods in Computer Science, 1:132-160, 2005.
• [20] W. Dzik, E. Orłowska, and C. van Alten. Relational representation theorems for general lattices with negations. Lecture Notes in Computer Science, 4136:162-176, 2006.
• [21] J. Flum. Games, kernels and antitone operations. Order, 17:61-73, 2000.
• [22] S. Passy, G. Gargov, and T. Tinchev. Modal environment for boolean speculations. In D. Skordev, editor, Mathematical Logic and Applications. Proceedings of the Gödel Conference, Druzhba, Bulgaria, pages 253-263. Plenum Press, New York, 2001.
• [23] B. Ganter and R. Wille. Formal Concept Analysis: Mathematical Foundations. Springer, Heidelberg, 1999.
• [24] G. Gediga and I. Düntsch. Skill set analysis in knowledge structures. British Journal of Mathematical and Statistical Psychology, 55:361-384, 2002.
• [25] M. Gerson. The inadequacy of the neighborhood semantics for modal logic. Journal of Symbolic Logic, 40(2):141-148, 1975.
• [26] R. Goldblatt. Varieties of complex algebras. Annals of Pure and Applied Logic, 44:173-242, 1989.
• [27] R. Goldblatt. Logics of time and computation. CSLI Lecture Notes, 7, 1992.
• [28] W. H. Hesselink. Nondeterminism and recursion via stacks and games. Theoretical Computer Science, 124:273-295, 1994.
• [29] I. Humberstone. Inaccessible worlds. Notre Dame Journal of Formal Logic, 24(3):346-352, 1983.
• [30] J. J¨arvinen and E. Orłowska. Relational correspondences for lattices with operators. Lecture Notes in Computer Science, 3929:134-146, 2006.
• [31] B. Jónsson and A. Tarski. Boolean algebras with operators I. American Journal of Mathematics, 73:891-939, 1951.
• [32] T.Y. Lin. Neighbourhood systems and approximation in relational databases and knowledge bases. In 4th International Symposium on Methodologies of Intelligent Systems, pages 75-86, 1989.
• [33] L.L. Maksimova. Pretabular superintuitionistic logics. Algebra and Logic, 11(5):558-570, 1972.
• [34] L.L. Maksimova. Pretabular extensions of the Lewis' logic s4. Algebra and Logic, 14(1):28-55, 1975.
• [35] C. Martin, S. Curtis, and I. Rewitzky. Modelling angelic and demonic nondeterminism with multirelations. Science of Computer Programming, 65(2):140-158, 2007.
• [36] R. Montague. Pragmatics. In R. Klibansky, editor, Contemporary Philosophy: a Survey, pages 102-122. La Nuova Italia Editrice, Firenze, 1968.
• [37] R. Montague. Universal grammar. Theoria, 36:373-398, 1970.
• [38] S. A. Naimpally and B. D. Warrack. Proximity Spaces. Cambridge University Press, Cambridge, 1970.
• [39] E. Orłowska and A. Radzikowska. Relational representability for algebras of substructural logics. Lecture Notes in Computer Science, 3929:212-224, 2006.
• [40] E. Orłowska and A. Radzikowska. Representation theorems for some fuzzy logics based on residuated nondistributive lattices. Fuzzy Sets and Systems, 159:1247-1259, 2008.
• [41] E. Orłowska and I. Rewitzky. Duality via truth: Semantic frameworks for lattice-based logics. Journal of the IGPL, 13:467-490, 2005.
• [42] E. Orłowska and I. Rewitzky. Discrete duality and its application to reasoning with incomplete information. Lecture Notes in Artificial Intelligence, 4585:51-56, 2007.
• [43] E. Orłowska and I. Rewitzky. Context algebras, context frames and their discrete duality. Transactions on Rough Sets IX, Lecture Notes in Artificial Intelligence, 5390:212-229, 2008.
• [44] E. Orłowska and I. Rewitzky. Algebras for Galois-style connections and their discrete duality. Fuzzy Sets and Systems, 161:1325-1342, 2010.
• [45] E. Orłowska, I. Rewitzky, and I. Düntsch. Relational semantics through duality. InW. MacCaull, M. Winter, and I. Düntsch, editors, Proceedings of the 8th International Conference on RelationalMethods in Computer Science and the 3rd International Workshop on Applications of Kleene Algebra and Workshop of COST Action 274, volume 3929 of Lecture Notes in Computer Science, pages 17-32, Heidelberg, 2005. Springer-Verlag.
• [46] E. Orłowska and D. Vakarelov. Lattice-based modal algebras and modal logics. In P. Hajek, L. M. Valdes-Villanueva, and D. Westerstahl, editors, Logic, Methodology and Philosophy of Science. Proceedings of the 12th International Congress, pages 147-170. Kings College London, 2005.
• [47] M. Pauly. A modal logic for coalition power in games. Journal of Logic and Computation, 12(1):149-166, 2002.
• [48] D. Peleg. Concurrent dynamic logic. Journal of the ACM, 34:450-479, 1987.
• [49] H. A. Priestley. Representation of distributive lattices by means of ordered Stone spaces. Bulletin of the London Mathematical Society, 2:186-190, 1970.
• [50] H. A. Priestley. Ordered topological spaces and the representation of distributive lattices. Proceedings of the London Mathematical Society, 24:507-530, 1972.
• [51] J. C. Raven. Guide to using the coloured progressive matrices sets A, Ab, B (Revised version). Gieve, London, 1965.
• [52] J. C. Raven. The Raven's Progressive Matrices: Change and stability over culture and time. Cognitive Psychology, 41:1-48, 2000.
• [53] I. Rewitzky. Binary multirelations. In H. de Swart, E. Orłowska, G. Schmidt, and M. Roubens, editors, Theory and Application of Relational Structures as Knowledge Instruments, volume 2929, pages 259-274. Spinger-Verlag, 2003.
• [54] D. Scott. Advice on modal logic. In K. Lambert, editor, Philosophical Problems in Logic: Some Recent Developments, pages 143-173. Reidel, Dordrecht, 1970.
• [55] W. Sierpinski and C. Krieger. General Topology. University of Toronto, 1956.
• [56] M. H. Stone. The theory of representations for Boolean algebras. Trans. Amer. Math. Soc., 40:37-111, 1936.
• [57] R. Wille. Restructuring lattice theory: An approach based on hierarchies of concepts. In I. Rival, editor, Ordered sets, volume 83 of NATO Advanced Studies Institute, pages 445-470. Reidel, Dordrecht, 1982.
• [58] R. Wille. Boolean concept logic. In G.W. Ganter, B. and Mineau, editors, Conceptual Structures: Logical, Linguistic and Computational Issues, Lecture Notes in Artificial Intelligence 1867, pages 317-331. Springer-Verlag, 2000.
• [59] Y. Y. Yao. Granular computing using neighbourhood systems. In P.K. Chawdhry, R. Roy, T. Furuhashi, editors, Advances in Soft Computing - Engineering Design and Manufacturing, pages 539-553. Springer-Verlag, London, 1999.