{"entities":{"Q923068":{"pageid":924916,"ns":120,"title":"Item:Q923068","lastrevid":65376984,"modified":"2026-04-12T02:10:43Z","type":"item","id":"Q923068","labels":{"en":{"language":"en","value":"Simple interpretations among complicated theories"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4170864"}},"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":"Q923068$43A9AD47-5ECB-4B23-B217-139EE3924792","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"24a412d1930974902b3b8d97410780e3d39bb0cc","datavalue":{"value":{"text":"Simple interpretations among complicated theories","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q923068$788BC746-F075-4A05-9C5C-07AD1A1FA8BA","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"0480523154688c1ffb5f55747a8b063a98f440cd","datavalue":{"value":"0712.03006","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q923068$03F7F484-A78A-4F2C-AEA7-BEF96DB5C523","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"2fe236f5ebe47bb9791211ceddf4fa6bf8e999b4","datavalue":{"value":"10.1016/0020-0190(90)90051-X","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q923068$C8CD924D-BB3F-4D12-8F0D-3059B300D164","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"d92e5b50a477cfe238ac688c9a8eb0ddc7ad041e","datavalue":{"value":{"entity-type":"item","numeric-id":204638,"id":"Q204638"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q923068$164EA66C-55C5-40E0-90DD-B2E38C5906CC","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"52fa7d44b58d0511cb8993765bd916aef86052d8","datavalue":{"value":{"entity-type":"item","numeric-id":63092,"id":"Q63092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q923068$5D9B2B12-721E-4854-98B9-F7B03350BE03","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"70d2fbf8bcd48a5ca1ac752985098b379d0dbb65","datavalue":{"value":{"time":"+1990-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q923068$B3585A40-A0CC-42BD-8E25-EC04C5335AC4","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"6e3684bb01c16a04ef69732a4cf37c3540f2eedd","datavalue":{"value":"Let QPTL denote the quantified propositional temporal logic with temporal operators ``nexttime'' and ``from now on forever'' and with the time structure of the type of natural numbers. Interpretations of some formal theories in QPTL are described which do not increase the number of quantifier alternations. By use of results of Sistla, Vardi and Wolper on complexity of quantifier bounded fragments of QPTL it gives (k-1)-fold exponential upper bounds of space complexity for the formulae of these theories with at most k quantifier alternations. The theories considered are 1): extensions of Presburger arithmetic by the predicate \\(x/_ my\\) which expresses that x is a power of m which divides y (for fixed m), 2) first order theories of m-ary trees with m successors, the prefix relation and the equal length relation, 3) the existential monadic second order theory of finite linear orders.","type":"string"},"datatype":"string"},"type":"statement","id":"Q923068$4C332253-F249-4CBA-993E-4134E89C0345","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"407654cf92f0702e03297e7fe541e25fa3f13c2d","datavalue":{"value":"03B25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q923068$215063A2-8E9B-4EDE-839C-684C78532A33","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"74a6cec96241e450625296e63e8dd539239d7104","datavalue":{"value":"03B45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q923068$1F3B28D9-307E-4A3B-89F4-1CC7E4E0A942","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q923068$9D79AADF-F0F7-4D51-8423-4C82D0693291","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q923068$5AB50570-1B59-45FD-8D74-951DC20826B2","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"884cebd0c0ad464fdf039a42e905659a1d42ce4e","datavalue":{"value":"4170864","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q923068$E740EE3E-4C6B-4926-B205-963C84082F89","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8e1e9381a3b8c3280e1ca77cfe130163c41d1349","datavalue":{"value":"decision complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q923068$EC914787-E5B1-4297-8BC9-5C0403B262BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a2449aa51f2a6c08b731b808b894ebe1e67b7f5f","datavalue":{"value":"quantified propositional temporal logic","type":"string"},"datatype":"string"},"type":"statement","id":"Q923068$D093D160-D2A2-4362-9BE9-CD7A6EEAD501","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bc414f681425b8ca834fa8ee0244adca0266d7f2","datavalue":{"value":"formal theories","type":"string"},"datatype":"string"},"type":"statement","id":"Q923068$80BB68DF-292D-4E05-883C-9C944167F519","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"62aad4e23b2f7dd73fff7fdf2b98241526182721","datavalue":{"value":"number of quantifier alternations","type":"string"},"datatype":"string"},"type":"statement","id":"Q923068$AF081CAE-DAA0-42F9-B623-A3D009BC7114","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6359dec5562d00aa1cb910e716d5f688a838da1b","datavalue":{"value":"complexity of quantifier bounded fragments","type":"string"},"datatype":"string"},"type":"statement","id":"Q923068$EC294312-2191-45AC-A1AB-800707D756A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bec8e70a962ab030bcaf2596abe48cfd6776ce29","datavalue":{"value":"exponential upper bounds of space complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q923068$2AF0C225-CD63-4037-A4F8-559E43CED558","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a42ba80a808f4b85d743f4df7d267089c8177eca","datavalue":{"value":"extensions of Presburger arithmetic","type":"string"},"datatype":"string"},"type":"statement","id":"Q923068$6E68AE1B-E4C7-4884-B6E7-22FF18E440D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b9af64c907529aa7598ebdbd38e0455cb7265496","datavalue":{"value":"first order theories of m-ary trees with m successors","type":"string"},"datatype":"string"},"type":"statement","id":"Q923068$50D87DC7-A966-4429-BF80-736663666671","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"95f8cdba91242f80f3ba34a1f56774c810dc764f","datavalue":{"value":"existential monadic second order theory of finite linear orders","type":"string"},"datatype":"string"},"type":"statement","id":"Q923068$44D241DD-26B1-48F9-A525-A292502DCE19","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":"Q923068$E2B09A6A-71D8-4260-ADEA-E7FD42C7D116","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"a419dd7ff0f3d465e478a0d405d767ee1f50956e","datavalue":{"value":{"entity-type":"item","numeric-id":917543,"id":"Q917543"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q923068$C03CF6D4-AF15-42F4-936B-D76251F54AE7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9f9514a16855598dd4702afb3968f95cf10303f8","datavalue":{"value":{"entity-type":"item","numeric-id":4134970,"id":"Q4134970"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q923068$391FFC28-E34D-4288-9053-2D9F1808B695","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1d6ee8482439db0c1b60415d5abcf524a3b838fa","datavalue":{"value":{"entity-type":"item","numeric-id":3769957,"id":"Q3769957"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q923068$119BB7C3-4951-49D7-848E-17CCF5D0DAC1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8d079b47cf1ba2d598f964b28ddec583cafa7821","datavalue":{"value":{"entity-type":"item","numeric-id":1088653,"id":"Q1088653"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q923068$351BD65B-D4E0-421C-A1A5-59C8922DF8E2","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e080210901be2a3cd23d58d8de35aa960da018fa","datavalue":{"value":{"entity-type":"item","numeric-id":4381382,"id":"Q4381382"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5a23cf83a444eccdb48d6f70aaffbe4c93a76724","datavalue":{"value":{"amount":"+0.7878921627998352","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":"Q923068$3F141356-45D4-4F45-80F2-DF7184226A7C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"808970fdcdd100f78bc7a745530c1d015ec895af","datavalue":{"value":{"entity-type":"item","numeric-id":3769957,"id":"Q3769957"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7163df792b2d450db98b293d708e818660cb6745","datavalue":{"value":{"amount":"+0.7876418232917786","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":"Q923068$746479D1-4F4F-4EE6-BD0F-0F545445A21F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f1990d77e9c082ed3b93eb00c37d8f154a5bc967","datavalue":{"value":{"entity-type":"item","numeric-id":1401306,"id":"Q1401306"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f5efeb56e229e58e8022355c28b04dea01284a45","datavalue":{"value":{"amount":"+0.7864557504653931","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":"Q923068$AF7C5A5B-BECD-4B18-A82D-A3E79A41A175","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"65103e820561a9321c0c366efd2359a0c13391cd","datavalue":{"value":{"entity-type":"item","numeric-id":4475142,"id":"Q4475142"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9f45a385dddffa69064ff3acfde280f68fe608d2","datavalue":{"value":{"amount":"+0.7777363061904907","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":"Q923068$66C0610C-90AA-4C99-90F6-EE892E274BB4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"20502be7dae51c272f2616fd28866b335793fb95","datavalue":{"value":{"entity-type":"item","numeric-id":418122,"id":"Q418122"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a34de72508bad0ba277e32de614b8ac22fbfcdbb","datavalue":{"value":{"amount":"+0.7773259282112122","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":"Q923068$223CE98E-C5D6-4408-98F8-F01D08350D68","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Simple interpretations among complicated theories","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Simple_interpretations_among_complicated_theories"}}}}}