{"entities":{"Q1826435":{"pageid":1837177,"ns":120,"title":"Item:Q1826435","lastrevid":57582495,"modified":"2026-03-31T11:59:54Z","type":"item","id":"Q1826435","labels":{"en":{"language":"en","value":"Decidability of quantified propositional intuitionistic logic and S4 on trees of height and arity \\(\\leq \\omega\\)"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 2081493"}},"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":"Q1826435$E97E992F-4C9B-4A80-B963-79F1F2189466","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"2edd3a08bb0c7ed0c2731229a3146090fcdc60cc","datavalue":{"value":{"text":"Decidability of quantified propositional intuitionistic logic and S4 on trees of height and arity \\(\\leq \\omega\\)","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1826435$A2845C0A-69CC-472C-A34E-D54D4B676CD8","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"8217ada62d30537aa6058f698fd65d4b38ac26cc","datavalue":{"value":"1054.03011","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1826435$F9FAC03B-A6EB-4F98-811C-F4A379B76838","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"37b019e89cb08882c4fda7783a360d1728596378","datavalue":{"value":{"entity-type":"item","numeric-id":288246,"id":"Q288246"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1826435$2826E172-A5F3-4A79-B329-64D54A9D0B39","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"e692f569038e7bcb7d3e72ba14d8d8e224046270","datavalue":{"value":{"entity-type":"item","numeric-id":169434,"id":"Q169434"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1826435$7B6FC169-2DAA-40D1-9BE1-B9D412DFAA2A","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"fdf3003d3f6dc4bd36d0ddd91ae69d1d9d4864ff","datavalue":{"value":{"time":"+2004-08-06T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1826435$1C457BC5-8F27-4429-8987-4EDBD8D1E43A","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"3aedbb349d804343ecf232aaab168726e0d12689","datavalue":{"value":"https://arxiv.org/abs/math/0203113","type":"string"},"datatype":"url"},"type":"statement","id":"Q1826435$C081C844-3ADF-411D-A853-CA06C071854D","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"afc758d8f1eae031a8e2400969c8345b1c28f1ed","datavalue":{"value":"The long title describes the contents of this article, but not the context. In J. Symb. Log. 62, 529--544 (1997; Zbl 0887.03002), \\textit{P. Kremer} showed that the set of quantified propositional formulas, valid with respect to all the Kripke structures (i.e., quasi-order with the minimal element), is highly undecidable; indeed, it is recursively isomorphic to the valid second-order formulas. He left open the problem: what happens if structures are confined to tree orders. The author answers this by showing the decidability in this setting. Actually, he considers three classes of structures: all the trees as described in the title, the exactly \\(n\\)-branching full tree, and the finite trees. In each of these classes, the set of valid formulas is decidable. He reduces the problem to the 1969 vintage result of \\textit{M. O. Rabin} on the decidability of the second-order tree language [Trans. Am. Math. Soc. 141, 1--35 (1969; Zbl 0221.02031)] by giving a translation of intuitionism formulas to tree formulas. Modal system S4 is similarly shown to be decidable. The author also considers the case when the structures are linear orders of various kinds [G\u00f6del-Dummet logics], and cites a number of open problems.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1826435$2BA26E27-8880-42D8-967F-19D10E3B610F","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"407654cf92f0702e03297e7fe541e25fa3f13c2d","datavalue":{"value":"03B25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1826435$83C53A3B-CF2D-4A09-9EE4-A5D340F25B5A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2337f934f367559a8ee0c48540aa4d52d0fa385a","datavalue":{"value":"03B20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1826435$5ACD5CC8-8028-4760-A0D4-BADA55260886","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"74a6cec96241e450625296e63e8dd539239d7104","datavalue":{"value":"03B45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1826435$C5ED4BE2-8CCA-4AF5-BD6E-83FBB7CF3AB7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e671cb9a7cd5542f21890d12b2e8ee004a8c8889","datavalue":{"value":"03C99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1826435$DD8E9A4B-7AFC-4E2F-8263-3A890995C7A6","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"00b21f23f0d0759a9e0463bf20a42936d7e2dba0","datavalue":{"value":"2081493","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1826435$866FCD3F-A8A3-499C-A153-4E8B4217815A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"48fe5da30f2000a910dd1a06f280ea2b3174328d","datavalue":{"value":"decidability","type":"string"},"datatype":"string"},"type":"statement","id":"Q1826435$BD55D2CA-D26E-4647-83AD-F72A712E6AE2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"945aa0ce91fe6de5a7754ae896576ceb141efb13","datavalue":{"value":"tree structure","type":"string"},"datatype":"string"},"type":"statement","id":"Q1826435$E87ED4B4-B5B8-4B65-9328-4D3E80F2EC78","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3875c79fa835ac45a1818de05c1bd8b1020c938e","datavalue":{"value":"Kripke model","type":"string"},"datatype":"string"},"type":"statement","id":"Q1826435$78D25365-0129-4503-AC8B-8D6BFD5C9AEC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9a28728b94e34f8cf3493870916b3fdca5e4d02e","datavalue":{"value":"quantified propositional formulas","type":"string"},"datatype":"string"},"type":"statement","id":"Q1826435$214EED35-33D6-450B-84A8-D5EDBACFA571","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d450f4b3083fe34d24db452ee74b92106c27a96e","datavalue":{"value":"intuitionistic logic","type":"string"},"datatype":"string"},"type":"statement","id":"Q1826435$09C5709E-D227-410B-B8FD-B3817CD5542E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f1dda010537b7b36bd45151721146f720815706e","datavalue":{"value":"modal logic","type":"string"},"datatype":"string"},"type":"statement","id":"Q1826435$C391D2CD-04E4-4EA4-A103-02373AC2AE43","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":"Q1826435$A503A76D-2F7F-4078-A3F2-779BF1778487","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"ac6e1bbaecaaf9743ea28b35cd4f55f3f8e066fd","datavalue":{"value":{"entity-type":"item","numeric-id":2767023,"id":"Q2767023"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1826435$101E1D60-70CE-4256-A6DC-A06AECC7EA20","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e52f372fafe719de5108c59e0672833ae8788a32","datavalue":{"value":{"entity-type":"item","numeric-id":4055622,"id":"Q4055622"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1826435$B23C3BCF-29CE-444D-B56F-B83E8459D2B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a5dfbc538077da75d332fb528c12551a8b230f68","datavalue":{"value":{"entity-type":"item","numeric-id":1148885,"id":"Q1148885"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1826435$264EDC8F-04C7-40FE-A420-5D32A572AC8C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"121c2b77a2e6f0b6bdb52f35e082e117e95f7c7d","datavalue":{"value":{"entity-type":"item","numeric-id":5287696,"id":"Q5287696"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1826435$D9FC0A2D-8E79-4F81-857E-CF0D13084F9F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6adcd56a0617efad5383d484676cc25701bc6e22","datavalue":{"value":{"entity-type":"item","numeric-id":4358053,"id":"Q4358053"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1826435$09F513DB-79CB-4D51-B95D-45486957D2DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4fc0fbba62806d6611fde9901ad3ff3bed111c8f","datavalue":{"value":{"entity-type":"item","numeric-id":5509675,"id":"Q5509675"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1826435$B1E6162B-64C1-4E6C-83CE-3D0A41B6747B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6c3a48dc71ab7bc77b1ce9ffe6a02b960104792e","datavalue":{"value":{"entity-type":"item","numeric-id":5796041,"id":"Q5796041"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1826435$FC2E4C95-66F8-41B8-A8FC-5A24D627D2E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b476279f9ef74fddb27272ad70ec34f0a4ec2a74","datavalue":{"value":{"entity-type":"item","numeric-id":5625141,"id":"Q5625141"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1826435$C8155C95-308E-4009-897D-46E3E8A0239C","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"ba86d8b36296ee58f547f7e61d082944b8ba6326","datavalue":{"value":"10.1023/B:LOGI.0000021744.10237.D0","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1826435$CDF90C6A-416F-4818-8BEA-71F6F397049D","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"29228986dbcf8ed2c578ae6f1d8029c211166fe3","datavalue":{"value":{"entity-type":"item","numeric-id":4358053,"id":"Q4358053"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a2dfb2fbb862a573ea780abe75e98699ad97bea3","datavalue":{"value":{"amount":"+0.7776448130607605","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":"Q1826435$58E467C7-0AF0-4E8C-B5FC-1D86CE3F23B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bfcf9bee88c51f2cfa1fd094339fd35821bdd450","datavalue":{"value":{"entity-type":"item","numeric-id":5292653,"id":"Q5292653"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a2dfb2fbb862a573ea780abe75e98699ad97bea3","datavalue":{"value":{"amount":"+0.7776448130607605","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":"Q1826435$37E1C66C-A40C-4CDB-B37B-D13EA0D0D470","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0e32b818e429ad0b6b270769587e5a50c6a38bbd","datavalue":{"value":{"entity-type":"item","numeric-id":1079558,"id":"Q1079558"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5403797a9032acd4835d2fa82815625c782e1225","datavalue":{"value":{"amount":"+0.7760193943977356","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":"Q1826435$C42CE627-69E2-4CCF-93F1-D5610F1EAACB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6d08cb31bd72d771492e81fdc29718f0c2266517","datavalue":{"value":{"entity-type":"item","numeric-id":3726100,"id":"Q3726100"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9b8e0451e079060b422cce75bce0b992553483e8","datavalue":{"value":{"amount":"+0.7570724487304688","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":"Q1826435$CF253C82-4B86-4596-8171-B7085735697F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1baf0e8b09720f765e34340f8ed24c658f1f3acf","datavalue":{"value":{"entity-type":"item","numeric-id":3370616,"id":"Q3370616"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0da282ef60d6f888f2a002651db852b4f9efa17a","datavalue":{"value":{"amount":"+0.7442737221717834","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":"Q1826435$72748DF9-31DF-49A6-BD95-9CC3649B1364","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1826435","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1826435"}}}}}