{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T04:57:54Z","timestamp":1760245074403,"version":"3.41.0"},"reference-count":11,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2006,4,1]],"date-time":"2006-04-01T00:00:00Z","timestamp":1143849600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Logic"],"published-print":{"date-parts":[[2006,4]]},"abstract":"<jats:p>\n            In the same sense as classical logic is a formal theory of truth, the recently initiated approach called\n            <jats:italic>computability logic<\/jats:italic>\n            is a formal theory of computability. It understands (interactive) computational problems as games played by a machine against the environment, their computability as existence of a machine that always wins the game, logical operators as operations on computational problems, and validity of a logical formula as being a scheme of \u201calways computabl \u201d problems. Computability logic has been introduced semantically, and now among its main technical goals is to axiomatize the set of valid formulas or various natural fragments of that set. The present contribution signifies a first step towards this goal. It gives a detailed exposition of a soundness and completeness proof for the rather new type of a deductive propositional system\n            <jats:bold>CL1<\/jats:bold>\n            , the logical vocabulary of which contains operators for the so called\n            <jats:italic>parallel<\/jats:italic>\n            and\n            <jats:italic>choice<\/jats:italic>\n            operations, and the atoms of which represent\n            <jats:italic>elementary problems<\/jats:italic>\n            , that is, predicates in the standard sense.This article is self-contained as it explains all relevant concepts. While not technically necessary, familiarity with the foundational paper \u201cIntroduction to Computability Logi \u201d [Annals of Pure and Applied Logic 123 (2003), pp.1-99] would greatly help the reader in understanding the philosophy, underlying motivations, potential and utility of computability logic---the context that determines the value of the present results.\n          <\/jats:p>","DOI":"10.1145\/1131313.1131318","type":"journal-article","created":{"date-parts":[[2006,7,25]],"date-time":"2006-07-25T14:14:26Z","timestamp":1153836866000},"page":"302-330","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":20,"title":["Propositional computability logic I"],"prefix":"10.1145","volume":"7","author":[{"given":"Giorgi","family":"Japaridze","sequence":"first","affiliation":[{"name":"Villanova University, Villanova, PA"}]}],"member":"320","published-online":{"date-parts":[[2006,4]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.2307\/2275407"},{"key":"e_1_2_1_2_1","unstructured":"van Benthem J. 2001. Logic in games. Tech. rep. University of Amsterdam. ILLC preprint.]]  van Benthem J. 2001. Logic in games. Tech. rep. University of Amsterdam. ILLC preprint.]]"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(92)90073-9"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/646203.682136"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0168-0072(97)00046-8"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0168-0072(01)00123-3"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0168-0072(03)00023-X"},{"volume-title":"Proceedings of the Symposium on Foundations of Mathematics. PWN","year":"1961","author":"Lorenzen P.","key":"e_1_2_1_9_1"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/151233.151240"},{"issue":"42","key":"e_1_2_1_11_1","first-page":"230","article-title":"On computable numbers with an application to the Entscheidungsproblem","volume":"2","author":"Turing A.","year":"1936","journal-title":"Proceedings of the London Mathematical Society"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(97)00154-0"}],"container-title":["ACM Transactions on Computational Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1131313.1131318","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1131313.1131318","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T15:06:16Z","timestamp":1750259176000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1131313.1131318"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,4]]},"references-count":11,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2006,4]]}},"alternative-id":["10.1145\/1131313.1131318"],"URL":"https:\/\/doi.org\/10.1145\/1131313.1131318","relation":{},"ISSN":["1529-3785","1557-945X"],"issn-type":[{"type":"print","value":"1529-3785"},{"type":"electronic","value":"1557-945X"}],"subject":[],"published":{"date-parts":[[2006,4]]},"assertion":[{"value":"2006-04-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}