Schedule
First International Workshop on Foundations of Computer Science as
LogicRelated.
August 30, 2008, Istanbul, Turkey.
Sabanci University Campus Colocated with ICTAC 2008 5th International Colloquium on Theoretical
Aspects of Computing.
For transportation between downtown Istanbul to the Sabanci University Campus (departing from Taksim Square) please check:
http://www.sabanciuniv.edu/eng/?kampus/hizmetolanak/ulasim/servis/servis.php
Workshop Schedule
==================================================
First Session  Moderator Walter Carnielli
==================================================
14:00  14:40
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
Foundational Ontology DOLCE" (Joint work with Oliver Kutz and Till
Mossakowski)
14:40 15:20
Juan C. Agudelo
IFCH and CLE, State University of CampinasUNICAMP, Brazil.
"Circuitsatisfiability 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)
==================================================
16:00 16:20
Coffee Break
==================================================
Second Session Moderator Çigdem Gencer
==================================================
16:20 17:00
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 CostaLeite
Swiss National Science Foundation
"Reducing knowledge to belief"
==================================================
19:00
Informal gathering (dinner)  University Cafeteria ==================================================
Overview
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 wellknow 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 socalled) nonclassical 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 nonclassical logic
theories may lead to new theories of computation which approach
quantum computing and other nonconventional ways to computation.
This workshop aims to discuss the lines of attack that logic can
offer to computation theory, emphasizing nonclassical logics and
combinations of logics as related to foundations of computer
science.
Topics of interest include (but are by no means limited to)
* Theoretical (conventional and nonconventional) models of computation
* Quantum computation and quantum logic(s)
* Paraconsistency, paraconsistentism and their relationship to
computational models
* IndependenceFriendly 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: postconference 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
firstorder 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 socalled
architectural specification) of the firstorder 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 ChurchTuring 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 nonstandard logics, showing how
computational complexity could be regarded as a nonabsolute, logicdependent
notion.
================================================
"Circuitsatisfiability 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 S5circuits by considering a previous generalization
of classical (boolean) circuits to nonstandard logic circuits. In S5
circuits, logic gates accomplish operations in accordance with an adequate
semantic for the wellknown modal logic S5. We show that there exists a
polynomialsize S5circuit solving the problem of circuitsatisfiability (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 nonunifiability
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 CostaLeite
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 truthcondition, 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"
