{"entities":{"Q793017":{"pageid":794865,"ns":120,"title":"Item:Q793017","lastrevid":64377099,"modified":"2026-04-11T19:27:07Z","type":"item","id":"Q793017","labels":{"en":{"language":"en","value":"Turing machines with linear alternation, theories of bounded concatenation and the decision problem of first order theories"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3855085"}},"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":"Q793017$CD44DEF2-7643-4D25-AC86-BEB896E06F88","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"32b761da8e3e179e3c2d2121087cd3d2495e5086","datavalue":{"value":{"text":"Turing machines with linear alternation, theories of bounded concatenation and the decision problem of first order theories","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q793017$AC2F4761-DEC9-4ED3-9542-49C23D53B59C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"09d925f916e6e19b7ed7e789fec60594fa4aedc1","datavalue":{"value":"0538.03035","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q793017$0F360395-07AB-4B81-9A6E-059887506D4C","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"6977a5f44e38b36adb1d9d96e95b47d3b52884b5","datavalue":{"value":"10.1016/0304-3975(83)90038-5","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q793017$40D83088-F0E5-46BD-B0A5-7F6F6CD62DAC","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"9e918cbe5f2468c40c3b5862fa0b405e268c29e2","datavalue":{"value":{"entity-type":"item","numeric-id":793016,"id":"Q793016"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q793017$57751873-3EDE-4BD5-AF48-425465B89F26","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q793017$1B5AF1B0-F0D4-464A-BC2E-BE7F7937DCA1","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"0136733d5dd7d9f4d36f24c87a0b8375ae1cb2fd","datavalue":{"value":{"time":"+1983-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":"Q793017$D03A6A17-B954-4377-8296-7ED783F7FC3F","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"719db4a7a8583618c20820017e47fcb637414265","datavalue":{"value":"A language L belongs to the complexity class \\(LATIME(t(n))\\) if it is accepted by some alternating Turing machine M which on inputs of length n makes at most t(n) steps and involves at most n alternations. For \\(\\Sigma\\) a finite alphabet \\(BCT(\\Sigma^*| t(n))\\) is the theory of the structure \\((\\Sigma^*,Con(t(n)))_{n\\in N}\\) where Con(t(n)) denotes the concatenation relation on \\(\\{w\\in \\Sigma^*| \\quad | w| \\leq t(n)\\}.\\) The author states without proof that \\(BCT(\\{0,1\\}^*| t(n))\\) (and some variants) are complete in \\(LATIME(t(0(n)))\\) with respect to polynomial time reductions whenever t satisfies \\(t(m_ 1+m_ 2)\\geq t(m_ 1)\\cdot t(m_ 2)\\) for \\(m_ 1,m_ 2>0\\) and t(1)\\(\\geq 2\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q793017$670B8000-70C3-4CB0-8693-C3B224F54BEC","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"33d9ad5fa3901c3c85d59a42af89ee043a9f83fb","datavalue":{"value":"03D10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q793017$18FCEA52-A984-4B65-907A-44401C347AE5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"407654cf92f0702e03297e7fe541e25fa3f13c2d","datavalue":{"value":"03B25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q793017$DFAB4FFE-DD49-4AB3-B2C8-84263C91CE05","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"6c8f899e92461bc6f19a5d7fd1a6ff7a01d9eaa4","datavalue":{"value":"3855085","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q793017$4FC28BAF-1BFC-44DF-9320-94CA214401D2","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ee275ded16c36a722a3d31c47fa029dddf558813","datavalue":{"value":"bounded concatenation","type":"string"},"datatype":"string"},"type":"statement","id":"Q793017$B48EEADE-84C2-4235-B492-5ADF0E9C4DC9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d61206e7416681d99dd05dd2bf66afa0d6cc85a9","datavalue":{"value":"decision problem of first order theories","type":"string"},"datatype":"string"},"type":"statement","id":"Q793017$10383F57-5D02-4620-8A88-104806F34231","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f8db1726c03c7059c08d69b8aca64a6baa1151a9","datavalue":{"value":"complexity class","type":"string"},"datatype":"string"},"type":"statement","id":"Q793017$F8692570-4364-4EA4-BCFE-5AFBD86BDA7E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"92caf16c6ea57f9885da64f74196f15c97c0ebb4","datavalue":{"value":"alternating Turing machine","type":"string"},"datatype":"string"},"type":"statement","id":"Q793017$A54EDBA0-95D6-4BE1-B486-E0AFD835E142","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"49ac28ac151a8a9103bbae52e8a00e91b3069fd7","datavalue":{"value":{"entity-type":"item","numeric-id":590477,"id":"Q590477"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q793017$B56343F1-6129-4AAD-9A00-5D1D8C2B6754","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":"Q793017$5E63ABDD-5C1A-4818-B61D-5E1301EF5388","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"8a1481a74015d9d213c2a051a8237dc0af75863f","datavalue":{"value":"https://doi.org/10.1016/0304-3975(83)90038-5","type":"string"},"datatype":"url"},"type":"statement","id":"Q793017$6BF14BB3-C9DB-46DC-9A38-7CDBB2912C44","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"6b249a86719a1969d8eb68835ea7e695e9050e62","datavalue":{"value":"W1995317845","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q793017$BA7FBFC4-23D3-4893-BCEC-D112A36E04CA","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"d74eec834971a75b92aae841b2c83f9c1a887997","datavalue":{"value":{"entity-type":"item","numeric-id":1159661,"id":"Q1159661"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q793017$1334DAAA-968B-4CCB-8355-A63CFD83120F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f3963b90870a42a133d18084b017239dcd6378b2","datavalue":{"value":{"entity-type":"item","numeric-id":5645036,"id":"Q5645036"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q793017$00CC816D-DF00-4E0F-BED5-565135ADF03F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"98d1f99209118318c5224afcbafe9d76aa7f8425","datavalue":{"value":{"entity-type":"item","numeric-id":1155607,"id":"Q1155607"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q793017$A0F75190-72DE-44AD-BF77-72A376911F96","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"648af4444efef3dfface63422920536bd2b0c180","datavalue":{"value":{"entity-type":"item","numeric-id":3928246,"id":"Q3928246"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q793017$ADC05B4C-B7DA-4E46-A4D2-16CE8C22CC8D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"29035f06020bdf6a821f5c6e4a2fac381017baf3","datavalue":{"value":{"entity-type":"item","numeric-id":1256445,"id":"Q1256445"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q793017$07A2150E-4EC0-4695-BD5D-3926174EF680","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cca8ae3740fcfb5a7e9f346758fcdd72ac5497a7","datavalue":{"value":{"entity-type":"item","numeric-id":4082296,"id":"Q4082296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q793017$C0D637DB-B3D7-42DF-8405-205D2B93A968","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0d246114b8f349e1c103f514a1c6159f4a3cd77a","datavalue":{"value":{"entity-type":"item","numeric-id":3880807,"id":"Q3880807"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q793017$1296BC87-B996-4F45-AD32-CAD9987923E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4a4d1b54f39385e475024bcf36a9244162838f1e","datavalue":{"value":{"entity-type":"item","numeric-id":1137036,"id":"Q1137036"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q793017$A2D11BC3-3850-485D-8AEF-D211B8E3E082","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3a29b87e2819856ba3a9b5fc56343a79c73f46a3","datavalue":{"value":{"entity-type":"item","numeric-id":3949037,"id":"Q3949037"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q793017$CFEA2B20-E806-4A34-A98E-075465EA9CCD","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":"Q793017$8B03A691-78BF-4623-8A9B-1AB93332EA07","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1f33f843778dfabfeef453cdfa627d4b42c24908","datavalue":{"value":{"entity-type":"item","numeric-id":4131648,"id":"Q4131648"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q793017$889A046E-C833-4122-B7D8-390D437E8E82","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c4a9eb62df14c1a9139349268232ba46053a027c","datavalue":{"value":{"entity-type":"item","numeric-id":3446172,"id":"Q3446172"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3e9c5ae63b4620c5b1e7e850a89f3f21b8a02f8e","datavalue":{"value":{"amount":"+0.7100358605384827","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":"Q793017$4B2EA6F4-69A6-44B7-B4ED-89A1FBD3C7E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d9f5ddcbd68d8762cbc31059a6a7b6249136ba27","datavalue":{"value":{"entity-type":"item","numeric-id":3034821,"id":"Q3034821"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a55c77b51fc1063be7db2292997d65ae30cc87e1","datavalue":{"value":{"amount":"+0.7085684537887573","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":"Q793017$F3D38DF6-C2DF-4AAF-91DD-23A630C12C71","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bc4ef181e5eb0842c7aab3fa9fd3478341a09c7b","datavalue":{"value":{"entity-type":"item","numeric-id":810009,"id":"Q810009"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9e55401d1aae3b94b060068c16c6e28d64632f02","datavalue":{"value":{"amount":"+0.7052571773529053","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":"Q793017$81551117-C7B3-4D94-93E0-71FADF2947DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1ce0674eeae3750fdffee905cca9b7c34377f1ea","datavalue":{"value":{"entity-type":"item","numeric-id":3334990,"id":"Q3334990"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1a3ceec8271ce8480026d0d4ef9a6aacd1a5d8ca","datavalue":{"value":{"amount":"+0.7036671042442322","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":"Q793017$7FA8DCBA-5A4A-4A82-8C8F-1EE7F58437F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"961e3330b473d5ba6bf99d977c635c05129edc9b","datavalue":{"value":{"entity-type":"item","numeric-id":5902006,"id":"Q5902006"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8727d5e4aff2979bb387589e00deb855b26c6585","datavalue":{"value":{"amount":"+0.7008429765701294","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":"Q793017$3D5EC481-161E-4462-81BE-1BD8319E3AAD","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Turing machines with linear alternation, theories of bounded concatenation and the decision problem of first order theories","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Turing_machines_with_linear_alternation,_theories_of_bounded_concatenation_and_the_decision_problem_of_first_order_theories"}}}}}