{"entities":{"Q1323362":{"pageid":1334112,"ns":120,"title":"Item:Q1323362","lastrevid":68462079,"modified":"2026-04-12T23:52:17Z","type":"item","id":"Q1323362","labels":{"en":{"language":"en","value":"Logical and schematic characterization of complexity classes"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 567323"}},"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":"Q1323362$C34157F3-D6FA-4630-A0A5-D90EF47ADCAB","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"017804547ec7e362d919875fc9a963dd8d29b2c3","datavalue":{"value":{"text":"Logical and schematic characterization of complexity classes","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1323362$B10696CA-8AB1-4904-82F8-C91D6977CF20","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"f3e46b81e70835a3222c0301aa4d6ea4f3a688cc","datavalue":{"value":"0790.68045","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1323362$45FD7568-4B85-4267-A93E-DD5DA31174A1","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"66013722674d2b1b8e02ea485574aeba4e627930","datavalue":{"value":"10.1007/BF01200263","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1323362$49D63BC0-4340-4B0B-BE7B-44F9F3F08202","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"f466736e4a4b4501d0136ec6feb8a629013f44a0","datavalue":{"value":{"entity-type":"item","numeric-id":265086,"id":"Q265086"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1323362$FDA5FEF6-6E6E-49C0-859E-7C26E9A6CE24","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"7d0f02e85530cd06ceb2c58a40dc9c2e0258e194","datavalue":{"value":{"entity-type":"item","numeric-id":161641,"id":"Q161641"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1323362$DC4CEDA3-E897-419D-95E5-A47B85B7F71E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"61a335d09cf4057e5c760f9e6e170367a29098e7","datavalue":{"value":{"time":"+1994-06-02T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1323362$F8062DF3-FB4F-4B21-B943-0AF7C31F1234","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"84e62ec76fa0848efc8148b34d2d59bdf7c9910c","datavalue":{"value":"We consider classes of well-known program schemes from a complexity theoretic viewpoint. We define logics which express all those problems solvable using our program schemes and show that the class of problems so solved or expressed coincides exactly with the complexity class of PSPACE (our problems are viewed as sets of finite structures over some vocabulary and, hence, they need not be encoded for input to our program schemes). We derive normal form theorems for our logics and use these normal form theorems to show that certain problems concerning acceptance and termination of our program schemes and satisfiability of our logical formulae are PSPACE-complete. Moreover, we show that a naturally-defined game problem, seemingly disjoint from logic and program schemes, is PSPACE-complete using the results described above. We also highlight similarities between the results of this paper and the literature, so providing the reader with an introduction to this area of research.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1323362$60D0505F-4C34-41FC-BB78-E3E0FABE0325","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1323362$0E3B1003-CA4D-47CB-A773-03A247F9C197","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1323362$2E11A9FE-0DFA-43B3-8B6F-83340BFC723B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4782ec55a8b8cc3ebd55f173b4568991ce0fd6ad","datavalue":{"value":"91A99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1323362$825807F2-9860-4D41-83C8-4A2E65339E74","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"09ed39cfb5b9001b8dcdf0cd912f337319c0b0af","datavalue":{"value":"567323","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1323362$B5FA0414-0FE9-45A4-933F-E27D6882D1ED","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1408da7db4c03e08918a50622f2fb337e63ab39f","datavalue":{"value":"complexity classes","type":"string"},"datatype":"string"},"type":"statement","id":"Q1323362$AE26B5EC-64A1-4D7B-A181-1DEEEE5DC624","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d5cb5b54a3a08e256bbb0215c92de493a4b5803e","datavalue":{"value":"program schemes","type":"string"},"datatype":"string"},"type":"statement","id":"Q1323362$8644EB5B-EA09-412D-8474-E45EA09BC702","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"96c107bb63de79565718d188b33fcc483957cfdd","datavalue":{"value":"PSPACE","type":"string"},"datatype":"string"},"type":"statement","id":"Q1323362$CAD28FC7-F603-4E1A-BF76-43917B1AD2CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"96fd7be9631edb45ac33ee482d312a36831c0760","datavalue":{"value":"normal form theorems","type":"string"},"datatype":"string"},"type":"statement","id":"Q1323362$75736D2A-9A4E-4492-A2E6-79A9CC757A4C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4befa4ca20f2beabcfa09e8a92ae13c21cb4934a","datavalue":{"value":"termination","type":"string"},"datatype":"string"},"type":"statement","id":"Q1323362$8A99893C-804D-4912-9634-F25D44238839","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"252f9f9ed9fe8ca406cc19fba38a46c0414791ee","datavalue":{"value":"satisfiability","type":"string"},"datatype":"string"},"type":"statement","id":"Q1323362$F284A4EF-6235-4006-8D97-DF2E0C89439B","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":"Q1323362$35460830-9144-4E5C-A72F-14EC66B91FF9","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"d9285a61f3039e7ce640456a9ea2b4d13665dc77","datavalue":{"value":{"entity-type":"item","numeric-id":5626625,"id":"Q5626625"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1323362$0B1AE9DB-9084-4B54-B4DE-594DEB1AB815","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4a7aaf7722886d9f40935d9243b5bd9dc530813b","datavalue":{"value":{"entity-type":"item","numeric-id":5660503,"id":"Q5660503"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1323362$F4120402-C88B-42DE-938D-36FE205D04DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0c53780c6a81f22c6542147d1a5d338f1d2f921a","datavalue":{"value":{"entity-type":"item","numeric-id":4729378,"id":"Q4729378"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1323362$DE69C7AD-5EAA-403B-BDDF-815CD7D07B18","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d0839e7e46510112865b452a6ed8d8dd889a4c60","datavalue":{"value":{"entity-type":"item","numeric-id":4058132,"id":"Q4058132"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1323362$06975CFE-41AF-4A24-8718-5C0E353D7982","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1323362$3DC2D320-7FAA-458D-92A5-580BB35DC58D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5710cd0fb8b5907d40eeada6e14d4018e26669a5","datavalue":{"value":{"entity-type":"item","numeric-id":1255942,"id":"Q1255942"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1323362$0BB24CB9-E121-4B7B-991B-26DD59A03235","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d0e3a179147832b2b1c96869b8d44ccac54dac91","datavalue":{"value":{"entity-type":"item","numeric-id":4343990,"id":"Q4343990"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1323362$3BC0E5A4-1285-4350-A185-ADEB3EFBCC57","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"46522e4fba2913fbfce618ec550ae0397d19c411","datavalue":{"value":{"entity-type":"item","numeric-id":3718149,"id":"Q3718149"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1323362$E9B1609F-95B1-464C-ADF8-56EF6094EB75","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b67ee9815f7ab3c8b2b4907677d99ca915d101b0","datavalue":{"value":{"entity-type":"item","numeric-id":1164622,"id":"Q1164622"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1323362$4A4124DE-0105-4351-B088-8AA080DD062F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"18d639fb9d03ad258814bab0f3f43d6d28e28a1e","datavalue":{"value":{"entity-type":"item","numeric-id":1173404,"id":"Q1173404"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1323362$34C34B21-4FEE-4AF1-A612-97DC89D53FFA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"04ca7a1acbb96c14c8f84c4ce6e6462daf757716","datavalue":{"value":{"entity-type":"item","numeric-id":3773337,"id":"Q3773337"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1323362$6F14A03A-81F7-40FA-811E-278ACD596D6C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fca97034e9eff6920b06a8f9cb612fa5d8889f95","datavalue":{"value":{"entity-type":"item","numeric-id":3974868,"id":"Q3974868"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1323362$F5470698-7A97-4991-A0EA-D84EE4B6E570","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"80c767919e94a3332b8d198174b1921d5e4026fe","datavalue":{"value":{"entity-type":"item","numeric-id":3821586,"id":"Q3821586"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1323362$D57D3907-4856-4213-B023-E8CBDCDEF946","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c15a8baf735680842777a1bce3d3c78132d43e41","datavalue":{"value":{"entity-type":"item","numeric-id":4131614,"id":"Q4131614"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1323362$45B69D1D-E99B-4EF1-9846-F51DA66E9C45","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7091303a5936a3d2add9212809debc0350ec7c45","datavalue":{"value":{"entity-type":"item","numeric-id":4185781,"id":"Q4185781"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1323362$E3BD46BF-28FF-44EB-8C22-EA77987BA962","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9635365b0780328d7ae22bc69b462e7144999d03","datavalue":{"value":{"entity-type":"item","numeric-id":5573961,"id":"Q5573961"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1323362$29A87814-180D-48BE-8536-F142452CC847","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"736a1d463d18d2f300e2b9600c3f86eae2986ef8","datavalue":{"value":{"entity-type":"item","numeric-id":2537313,"id":"Q2537313"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1323362$55452102-7EDD-411E-B08C-7C78A0A6A759","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"539d31d4fd142d7bab7d11ac98ad97b424cadd9f","datavalue":{"value":{"entity-type":"item","numeric-id":4431234,"id":"Q4431234"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1323362$E77C8832-FD77-45E9-A50C-009C5FEFF31D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"47583cbf0cbd2a2542b73f535dd56565e702d68a","datavalue":{"value":{"entity-type":"item","numeric-id":1323362,"id":"Q1323362"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1323362$96B93040-E8D4-468C-AEEB-48F8DC38845A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e4751cb99cfb27abec44f2378f8165a3a9a6376a","datavalue":{"value":{"entity-type":"item","numeric-id":1236109,"id":"Q1236109"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1323362$8AF4B6F5-DFC6-49AA-94F0-8677999C04E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"df4477667d1e832c2b258226b966cf6180b37911","datavalue":{"value":{"entity-type":"item","numeric-id":1106839,"id":"Q1106839"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1323362$EABC2027-D880-42D5-8F6F-73AD1BD6BA69","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f8abe13e1e22c2d30de8b462293c9efd77a0bdd4","datavalue":{"value":{"entity-type":"item","numeric-id":1106839,"id":"Q1106839"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8cee313bb75610342ee8de35a903e94e1a247fee","datavalue":{"value":{"amount":"+0.8126609325408936","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":"Q1323362$A1810D9A-0958-4E35-8227-4F300A7320E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"45da740055550693832601ad8e4cb98b54a4decd","datavalue":{"value":{"entity-type":"item","numeric-id":5311269,"id":"Q5311269"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8181046bd6490de5bed2a2cd3266b2048cbdb7c9","datavalue":{"value":{"amount":"+0.797232985496521","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":"Q1323362$8EDF908D-F75F-4296-AA60-C2C076AA1021","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dd37efe72d7a2a5cc948dcbce447e33d0c8c58a0","datavalue":{"value":{"entity-type":"item","numeric-id":1575880,"id":"Q1575880"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c1314a7e3046ae1d5bd63d585d3fa5b30f25f02c","datavalue":{"value":{"amount":"+0.7869886159896851","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":"Q1323362$2B95C120-693E-4B30-B51D-DFE9AD4A7F55","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"afa25a179bbc62e0a39aaeb0bbfb06ccb1a4cc7f","datavalue":{"value":{"entity-type":"item","numeric-id":4943505,"id":"Q4943505"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2fa9b7e806870bc97f59f47115cc80f40930c90d","datavalue":{"value":{"amount":"+0.785696804523468","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":"Q1323362$6F1DEF92-83A6-46BA-93EE-EFFAE01F062E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d62f170ea73483ba5b0b42f50c8c94b6900b2fe1","datavalue":{"value":{"entity-type":"item","numeric-id":1123616,"id":"Q1123616"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"99f4b196c608448674c9707297350560515617d2","datavalue":{"value":{"amount":"+0.7750200629234314","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":"Q1323362$5F4760DE-4188-4008-9178-69E11C0E9E38","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Logical and schematic characterization of complexity classes","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Logical_and_schematic_characterization_of_complexity_classes"}}}}}