1. Two decision problems in Contact Logics
- Author
-
Cigdem Gencer, Zafer Özdemir, Philippe Balbiani, Logique, Interaction, Langue et Calcul (IRIT-LILaC), Institut de recherche en informatique de Toulouse (IRIT), Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées, Centre National de la Recherche Scientifique (CNRS), Istanbul Aydin University, Istanbul University, İstanbul Kültür Üniversitesi, Centre National de la Recherche Scientifique - CNRS (FRANCE), İstanbul Aydin Üniversitesi - IAU (TURKEY), Institut National Polytechnique de Toulouse - Toulouse INP (FRANCE), Université Toulouse III - Paul Sabatier - UT3 (FRANCE), Université Toulouse - Jean Jaurès - UT2J (FRANCE), Université Toulouse 1 Capitole - UT1 (FRANCE), İstanbul Kültür Üniversitesi - IKU (TURKEY), and Institut National Polytechnique de Toulouse - INPT (FRANCE)
- Subjects
Logique en informatique ,Unifiability problem ,Theoretical computer science ,Unification ,Logic ,Computer science ,Computability ,Contact Logics ,010102 general mathematics ,[INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO] ,02 engineering and technology ,Decision problem ,Type (model theory) ,01 natural sciences ,Focus (linguistics) ,Decidability ,TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES ,Computer Science::Logic in Computer Science ,0202 electrical engineering, electronic engineering, information engineering ,Natural (music) ,020201 artificial intelligence & image processing ,0101 mathematics ,Boolean satisfiability problem ,Satisfiability problem - Abstract
Contact Logics provide a natural framework for representing and reasoning about regions in several areas of computer science. In this paper, we focus our attention on reasoning methods for Contact Logics and address the satisfiability problem and the unifiability problem. Firstly, we give sound and complete tableaux-based decision procedures in Contact Logics and we obtain new results about the decidability/complexity of the satisfiability problem in these logics. Secondly, we address the computability of the unifiability problem in Contact Logics and we obtain new results about the unification type of the unifiability problem in these logics.
- Published
- 2019