- Oggetto:
Complexity of the Mints hierarchy in first-order intuitionistic logic
- Oggetto:
Complexity of the Mints hierarchy in first-order intuitionistic logic
- Oggetto:
Academic year 2013/2014
- Course ID
- SEM-CMHFOIL
- Teaching period
- Seminario
- Type
- Seminario
- Course disciplinary sector (SSD)
- INF/01 - informatica
- Delivery
- Tradizionale
- Language
- Inglese
- Attendance
- Facoltativa
- Type of examination
- Non prevista
- Oggetto:
Sommario del corso
- Oggetto:
Program
In classical logic, every first-order formula is equivalent to one
in prenex normal form. Intuitionistic logic does not have this property
but it can be stratified on the basis of the quantifier prefix
a formula _would have_ if classically normalized. In the minimal
(universally-implicational) fragment, this corresponds to alternation
of positive and negative occurrences of the universal quantifier. This
idea is implicit in a 1968 paper of G. Mints.
We investigate the decidability and complexity of the decision problems
for classes of this hierarchy. The talk will be based on joint work
with A. Schubert, D. Walukiewicz-Chrzaszcz, and K. Zdanowski.Suggested readings and bibliography
- Oggetto:
Class schedule
Days Time Classroom Venerdì 10:00 - 12:00 Sala Seminari Dipartimento di Informatica Lessons: dal 22/11/2013 to 22/11/2013
- Oggetto:
Note
The seminar will be held by Prof. Pawel Urzyczyn, Varsavia University.
- Oggetto: