Algebra i logika
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive
Impact factor

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Algebra Logika:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Algebra i logika, 2016, Volume 55, Number 4, Pages 419–431
DOI: https://doi.org/10.17377/alglog.2016.55.402
(Mi al749)
 

This article is cited in 1 scientific paper (total in 1 paper)

Undecidable iterative propositional calculus

G. V. Bokov

Faculty of Mechanics and Mathematics, Moscow State University, Leninskie Gory, Moscow, 119992 Russia
Full-text PDF (149 kB) Citations (1)
References:
Abstract: We consider iterative propositional calculi that are finite sets of propositional formulas together with modus ponens and an operation of superposition defined by a set of Mal'tsev operations. For such formulas, the question is studied whether the derivability problem for formulas is decidable. In the paper, we construct an undecidable iterative propositional calculus whose axioms depend on three variables. A derivation of formulas in the given calculus models the solution process for Post's correspondence problem. In particular, we prove that the general problem of expressibility for iterative propositional calculi is algorithmically undecidable.
Keywords: iterative propositional calculus, derivability problem, expressibility problem, Post’s correspondence problem.
Received: 24.09.2015
English version:
Algebra and Logic, 2016, Volume 55, Issue 4, Pages 274–282
DOI: https://doi.org/10.1007/s10469-016-9396-3
Bibliographic databases:
Document Type: Article
UDC: 510.64
Language: Russian
Citation: G. V. Bokov, “Undecidable iterative propositional calculus”, Algebra Logika, 55:4 (2016), 419–431; Algebra and Logic, 55:4 (2016), 274–282
Citation in format AMSBIB
\Bibitem{Bok16}
\by G.~V.~Bokov
\paper Undecidable iterative propositional calculus
\jour Algebra Logika
\yr 2016
\vol 55
\issue 4
\pages 419--431
\mathnet{http://mi.mathnet.ru/al749}
\crossref{https://doi.org/10.17377/alglog.2016.55.402}
\transl
\jour Algebra and Logic
\yr 2016
\vol 55
\issue 4
\pages 274--282
\crossref{https://doi.org/10.1007/s10469-016-9396-3}
\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000388103400002}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84994744785}
Linking options:
  • https://www.mathnet.ru/eng/al749
  • https://www.mathnet.ru/eng/al/v55/i4/p419
  • This publication is cited in the following 1 articles:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Алгебра и логика Algebra and Logic
    Statistics & downloads:
    Abstract page:182
    Full-text PDF :46
    References:43
    First page:12
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024