Artykuł w czasopiśmie
Brak miniatury
Licencja
ClosedAccessDostęp zamknięty
 

On the Mints Hierarchy in First-Order Intuitionistic Logic

Uproszczony widok
dc.abstract.enWe stratify intuitionistic first-order logic over (∀,→) into fragments determined by the alternation of positive and negative occurrences of quantifiers (Mints hierarchy). We study the decidability and complexity of these fragments. We prove that even the Δ2 level is undecidable and that Σ1 is Expspace-complete. We also prove that the arity-bounded fragment of Σ1 is complete for co-Nexptime.
dc.affiliationUniwersytet Warszawski
dc.contributor.authorSchubert, Aleksy
dc.contributor.authorUrzyczyn, Paweł
dc.contributor.authorZdanowski, Konrad
dc.date.accessioned2024-01-25T15:46:33Z
dc.date.available2024-01-25T15:46:33Z
dc.date.issued2017
dc.description.financeNie dotyczy
dc.description.number4
dc.description.volume12
dc.identifier.doi10.2168/LMCS-12(4:11)2016
dc.identifier.issn1860-5974
dc.identifier.urihttps://repozytorium.uw.edu.pl//handle/item/114830
dc.identifier.weblinkhttps://lmcs.episciences.org/2623
dc.languageeng
dc.pbn.affiliationcomputer and information sciences
dc.relation.ispartofLogical Methods in Computer Science
dc.relation.pages1-25
dc.rightsClosedAccess
dc.sciencecloudnosend
dc.subject.enComputer Science - Logic in Computer Science
dc.titleOn the Mints Hierarchy in First-Order Intuitionistic Logic
dc.typeJournalArticle
dspace.entity.typePublication