First International Workshop on Foundations August 30, 2008, Istanbul, Turkey Co-located with ICTAC 2008 |
 A View of Constantinople Across the Bosphorus with the Hagia Sophia in the Distance by Antoine-Ignace Melling (1763-1831) |
|
Schedule First International Workshop on Foundations of Computer Science as Workshop Schedule ================================================== Dominik Lücke SFB/TR 8 Spatial Cognition, Bremen, Germany and DFKI Lab Bremen, Germany. "Modular Construction of Models: Towards a Consistency Proof for the 14:40- 15:20 Juan C. Agudelo IFCH and CLE, State University of CampinasUNICAMP, Brazil. "Circuit-satisfiability can be polynomial: a logic shift" 15:20- 16:00 Çigdem Gencer Department of Mathematics and Computer Science, Istanbul Kultur University, Istanbul, Turkey. "Unifiability in Extensions of K4.3" (Joint work with Dick de Jongh) ================================================== Coffee Break
================================================== Walter Carnielli IFCH and CLE, State University of Campinas - UNICAMP, Brazil and Dept. of Computer Science and Communications, University of Luxembourg, Luxembourg "Computability: Logic versus Physics" 17:00- 17:40 Alexandre Costa-Leite Swiss National Science Foundation "Reducing knowledge to belief"
Informal gathering (dinner) - University Cafeteria ==================================================
The workshop intends to discuss the philosophical, mathematical and technical aspects about the relevance of logic in the foundations of Computer Science, specially concerning new paradigms of computation. It is well-know how and how much the foundations of computer science depends on logic. Not only programming languages entirely depend on logic issues, but also expressing essential features of computers as e.g. formalizing relevant theories for computer science involves tackling questions such as decidability and consistency of logical theories. Classical and (the so-called) non-classical logics play an essential role therein. On the one hand, topics such as the existence of unprovable sentences in such theories will touch foundational issues as Godel's Incompleteness Theorem and related matters, while on the other hand non-classical logic theories may lead to new theories of computation which approach quantum computing and other non-conventional ways to computation. This workshop aims to discuss the lines of attack that logic can offer to computation theory, emphasizing non-classical logics and combinations of logics as related to foundations of computer science.
Topics of interest include * Theoretical (conventional and non-conventional) models of computation * Quantum computation and quantum logic(s) * Paraconsistency, paraconsistentism and their relationship to computational models * Independence-Friendly logic and its implications to computation * Logical aspects of knowledge representation * Information and computation * Philosophical aspects on computing * Challenging issues on the history of computing * Computable model theory * Category theory and models of computation * Computational algebra (algorithms and foundations)
Organization The workshop is being organized by the Brazilian Logic Society and sponsored by the FAPESP ConsRel Project "Logical Consequence and Combinations of Logics" (Universities of Campinas and Sao Paulo, Brazil)
Program committee Varol Akman (Bilkent University at Ankara, Turkey) Walter Carnielli (UNICAMP at Campinas, Brazil) Newton da Costa (UFSC at Florianóplis, Brazil) Giorgi Japaridze (Villanova University at Villanova, Pennsylvania, USA) Martin Davis (Professor Emeritus, New York University, NY, USA) Wilfrid Hodges (Queen Mary College, University of London) Amilcar Sernadas (IST at Lisbon, Portugal) Aldo Ursini (University of Siena at Siena, Italy)
Important dates * Workshop: August 30, 2008. * Abstract submission deadline: June 30, 2008. * Paper submission deadline: post-conference publication (to be announced) * Acceptance notification: July 30, 2008 ============================ Extended deadlines Abstract submissions: : July 18, 2008 Acceptance notification: August 5t 2008 ============================
Proceedings We plan to publish a selection of the presented papers in a special volume of an international journal in the area (details to be announced)
Accepted papers "Modular Construction of Models: Towards a Consistency Proof for the Foundational Ontology DOLCE" Oliver Kutz, Dominik Lücke and Till Mossakowski SFB/TR 8 Spatial Cognition, Bremen, Germany and DFKI Lab Bremen, Germany We discuss the problem of consistency proofs for large and complex first-order theories originating from the realm of ontologies. In particular, we argue that 'standard' automated reasoning methods are often insufficient for proving such consistency results. We advocate an approach where a global model of a theory is built from smaller models together with amalgamability properties between such models. To illustrate the feasibility of this technique, we have constructed a modular version (a so-called architectural specification) of the first-order version of the foundational ontology DOLCE. ================================================ "Computability: Logic versus Physics" Walter Carnielli IFCH and CLE, State University of Campinas - UNICAMP, Brazil Dept. of Computer Science and Communications, University of Luxembourg, Luxembourg We describe two physical versions (respectively proposed by Robin Gandy and David Deutsch) of the Church-Turing thesis. The proposal by Deutsch to consider computability as a branch of physics is criticized, and we argue in favor of logical theories of computation. Finally, we describe two ways in which classical models of computation can be generalized through non-standard logics, showing how computational complexity could be regarded as a non-absolute, logic-dependent notion. ================================================ "Circuit-satisfiability can be polynomial: a logic shift" Juan C. Agudelo Ph.D. Program in Philosophy, area of Logic, IFCH and Group for Applied and Theoretical Logic- CLE, State University of Campinas - UNICAMP, Brazil . Logic and Computation Research Group, Eafit University, Colombia We define the model of S5-circuits by considering a previous generalization of classical (boolean) circuits to non-standard logic circuits. In S5- circuits, logic gates accomplish operations in accordance with an adequate semantic for the well-known modal logic S5. We show that there exists a polynomial-size S5-circuit solving the problem of circuit-satisfiability (for classical circuits). As a consequence, if P and NP do not coincide, as it is widely believed, the notion of computational complexity can be relativized by means of logic. ================================================ "Unifiability in Extensions of K4.3" Cigdem Gencer and Dick de Jongh Department of Mathematics and Computer Science, Istanbul Kultur University, Istanbul, Turkey and Institute for Logic, Language and Computation, Universiteit van Amsterdam We give a semantic characterization for unifiability and non-unifiability in the extensions of K4.3. We apply this result to obtain a syntactic characterization and give a concrete decision procedure for unifiability in those logics. For that purpose we use universal models. ================================================ "Reducing knowledge to belief" Alexandre Costa-Leite Swiss National Science Foundation Knowledge is usually viewed as a stronger notion than belief. One of the basic differences between both concepts is that knowledge implies truth while belief does not. Both concepts have the same truth-condition, but their difference is the fact that models for the basic logic of knowledge have as plausibility relation an equivalence relation, while models for belief are euclidian. However, a problem of collapsing knowledge and belief attracted the attention of a few researchers. The purpose of this talk is to explain some approaches to this problem as well to propose a new solution to it based on techniques of combining logics and paraconsistent logics.
Call for papers Contributions are invited on all topics of the workshop. Please submit an extended abstract in PDF format (from two to a maximum of ten pages) including a short abstract (maximum 20 lines) and references. The submission contents must be unpublished and not submitted for publication in any journals or other scientific meetings. It is expected that accepted papers will be presented at the workshop by one of its authors.
Contact For additional information about submissions, please contact the Program Chair: Walter Carnielli
Sponsors Brazilian Logic Society and FAPESP ConsRel Project "Logical Consequence and Combinations of Logics"
|