{"entities":{"Q1035649":{"pageid":1037497,"ns":120,"title":"Item:Q1035649","lastrevid":50804096,"modified":"2026-01-15T05:58:17Z","type":"item","id":"Q1035649","labels":{"en":{"language":"en","value":"Logical structures and genus of proofs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5624903"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1035649$7FD06965-8B2D-4195-AA9E-FFF576605BAC","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"6857f51b460ba5c3c6250d387242f04c06aab378","datavalue":{"value":{"text":"Logical structures and genus of proofs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1035649$82979BFA-7B97-4D2C-8327-2D2E13BFC31D","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"bcc94e122c2f9044ad80902ea4c76928fa9955c7","datavalue":{"value":"1182.03105","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1035649$1B26865A-FBF4-4C5B-AEBB-0972F57ABF23","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"db2fe20e7af1bde4dc050e6d480bb6b9ca259444","datavalue":{"value":{"entity-type":"item","numeric-id":702484,"id":"Q702484"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1035649$B2DABCA9-81F0-4FCA-8215-35BBCF055889","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f91a4bcbc93435aed71775d25a4c5cd09e26f12d","datavalue":{"value":{"entity-type":"item","numeric-id":122505,"id":"Q122505"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1035649$8749FBB2-A478-42EA-8C94-B8C0A49DEB16","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"ef2b4a391107c8565fc25ba0caa09f7f59741046","datavalue":{"value":{"time":"+2009-11-04T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1035649$C5DF9FCB-96E8-47E9-9C1F-56416779D69C","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"2254681009399787ceb521349c1a0d526feaf732","datavalue":{"value":"To measure the complexity of a (formal) proof, the author introduces the notion of genus. The object of investigation of this paper is classical sentential sequent calculus. The starting point is Gentzen's threads [`Faden'], which S. Buss organized as a logical flow graph. To resolve crossing-over of edges, the author embeds a graph on the surface of a sphere with handles. The genus of a proof is, of course, the minimum number of handles necessary. She shows the existence of a cut-free proof of genus \\(n\\), for any \\(n\\geq 0\\). If the genera of proofs of two upper sequents of a cut are \\(k\\) and \\(l\\), respectively, then the genus of the proof with the cut is between \\(k+l\\) and \\(k+l+ r-1\\), where \\(r\\) is the number of atomic formulas occurring in the cut formula. Another kind of result is the realizability of any non-oriented graph as the logical flow graph of a cut-free proof. This is an unpublished result of R. Statman from the early 1970's. The author reformulates and proves it in a graph-theoretic format.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1035649$2298F63B-7372-442E-BE87-7F2F0CB51B47","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6e2ae8b1900147d15ddea62ccb5302a15ee19b5d","datavalue":{"value":"03F07","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1035649$3F78A126-1008-4531-88C4-074A0EDA83BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"ece9b879f80d96e2a1d45b28bdcc8cfa6b01861e","datavalue":{"value":"03F20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1035649$FA9AAFCB-ACA1-48CD-BC14-D5944BFE04EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"357c7c34a1a90d83243f17011b7aa90788d1792d","datavalue":{"value":"05C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1035649$DF305A2A-3A6F-4513-8B46-B33B4BB98BEC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"82e8efd6e51c28a954a2ab0c3ccebf86d2ac5eb3","datavalue":{"value":"05C62","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1035649$844B0452-FBDF-43F3-9BDC-2DFAA242C340","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"a469089718a24f20de7e2d1b8702644c8801600a","datavalue":{"value":"5624903","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1035649$19266C3E-3ED4-4275-AF9A-3468E0E2C4A8","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5e639cac55cb05a5a369dd1b27e3222011ce4841","datavalue":{"value":"genus of a proof","type":"string"},"datatype":"string"},"type":"statement","id":"Q1035649$B62A6E3D-D1CA-415B-98ED-80958A93C598","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7922c79235032f78dd6d2b449b362a905a29a30d","datavalue":{"value":"logical flow graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1035649$B2719B5F-AE38-4D45-AAC1-E3A0B1554F2B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2c7d4aa0d3cf1745112ae7d594a2a5578f4e767f","datavalue":{"value":"sequent calculus","type":"string"},"datatype":"string"},"type":"statement","id":"Q1035649$B473E401-5ACB-4656-92F1-C91298B5FCFA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9bde502d875fa8eeedd7c6109a48a0c26939dc22","datavalue":{"value":"cut-free proof","type":"string"},"datatype":"string"},"type":"statement","id":"Q1035649$D450A0E4-AC29-49BE-9CFB-B597D2C13482","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"abab6d51bc0722532b523ea42f8eaf8ed745f963","datavalue":{"value":"cut","type":"string"},"datatype":"string"},"type":"statement","id":"Q1035649$234E9E14-0B61-405E-A472-7F64A2E0247A","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1035649$CC3F8274-4688-416E-AF35-197770564CA7","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"af16d3067ba9a998dbc5d218db3c2a7948893db5","datavalue":{"value":"https://doi.org/10.1016/j.apal.2009.05.007","type":"string"},"datatype":"url"},"type":"statement","id":"Q1035649$F7EF7EB9-DB85-4F49-87AD-62657EE0AA10","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"5d168cca9b687d3cda1954c6a37de843e2065d03","datavalue":{"value":"W2037021689","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1035649$A5A0EE8D-3E2E-4B76-9066-6E68B0576F67","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"d87fac94667acc9c8d81f0966c80a0f253ba95d6","datavalue":{"value":"Q57253053","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1035649$BE4BFBD2-0EE0-4918-97B6-80218E010649","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"49508253f586991686167e53d90ae970b902e6b3","datavalue":{"value":{"entity-type":"item","numeric-id":1176199,"id":"Q1176199"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1035649$13531345-7A57-4B8F-B8A7-2DFD91DBF907","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a064c24e33fdb6013bc5a8a7ffdbe6ad695be319","datavalue":{"value":{"entity-type":"item","numeric-id":674415,"id":"Q674415"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1035649$1A62643B-F6A2-4BB3-A094-5E18C867B9C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3b438253220515ab35f613aaed4ed5f62096aa41","datavalue":{"value":{"entity-type":"item","numeric-id":1125056,"id":"Q1125056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1035649$22EAC354-7F9A-45BE-AB20-B746927516C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"70cf46fa6ed3fb126b0a12eb1810a62dfc7ef455","datavalue":{"value":{"entity-type":"item","numeric-id":1853510,"id":"Q1853510"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1035649$157F5D26-B09D-48E4-AB5C-7F7497DEEA39","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"129f67f850c86ea1d5373017cb2a7d02cf64bb14","datavalue":{"value":{"entity-type":"item","numeric-id":4496851,"id":"Q4496851"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1035649$1A4C8B18-217D-46E1-9172-DF233D98A897","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ff1c9576a9af1e44009a9ef9a0f7f22e091829d5","datavalue":{"value":{"entity-type":"item","numeric-id":5610986,"id":"Q5610986"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1035649$D901D3CA-A3BA-4F5C-8BD6-1CDC5BACCBE7","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"469e72545dfc249d4a7fcc52dcceb2832bfa16e9","datavalue":{"value":"10.1016/J.APAL.2009.05.007","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1035649$8DD2D483-D74E-4F70-860D-A8BB40D7C29B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"42a3728eb6d6cea535db12f53a28c7233f093a8f","datavalue":{"value":{"entity-type":"item","numeric-id":1263584,"id":"Q1263584"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"59e60516f25bd30a4a62a93c1d5c74041be3de5e","datavalue":{"value":{"amount":"+0.7816858887672424","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1035649$05DBE4A9-09F3-4279-9B3E-462E7FA472A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3d810f021175925e6dc2d89e37a847f4ea5c360f","datavalue":{"value":{"entity-type":"item","numeric-id":4532599,"id":"Q4532599"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dfa247160a637c4e9fddebfc4b5ce3d286889ee6","datavalue":{"value":{"amount":"+0.7722084522247314","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1035649$AFC16048-9C72-47B9-AA36-8FA40C6EB168","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"53bca1d06dbb6380267a6ecb6c728afd5be6f617","datavalue":{"value":{"entity-type":"item","numeric-id":1125056,"id":"Q1125056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d38c7e79ebbe49058012736651baf6f1bb8893e7","datavalue":{"value":{"amount":"+0.7474713921546936","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1035649$293269C7-6459-4316-9D79-7360E4491B8A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"21d04cca6a3ab2228460822bf8e82bf740d4618e","datavalue":{"value":{"entity-type":"item","numeric-id":674415,"id":"Q674415"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d38c7e79ebbe49058012736651baf6f1bb8893e7","datavalue":{"value":{"amount":"+0.7474713921546936","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1035649$2A847776-AF67-41A9-9CBE-693A9ABB461A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"54caad1467dbad2df2ae164a0c93ccd6a638f159","datavalue":{"value":{"entity-type":"item","numeric-id":4337947,"id":"Q4337947"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"78b7f61a7e160bcefa47054fd28b7ebf45967b8c","datavalue":{"value":{"amount":"+0.7370624542236328","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1035649$161E0727-EE96-43F8-872B-D78980332079","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1035649","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1035649"}}}}}