{"entities":{"Q2850842":{"pageid":2861562,"ns":120,"title":"Item:Q2850842","lastrevid":58020075,"modified":"2026-04-03T11:47:30Z","type":"item","id":"Q2850842","labels":{"en":{"language":"en","value":"Alternating Turing machines for inductive languages"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6213051"}},"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":"Q2850842$CC592ED2-7C5D-41E8-B23C-3AFFCBC17E4D","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"1728e1df218705d7c3e91b13ccdcb90be6e4a8df","datavalue":{"value":{"text":"Alternating Turing machines for inductive languages","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2850842$F7047E90-6132-4C6D-8546-0872BF839C7F","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"365bd7444145fd3d663a94c11c262ed360b765e0","datavalue":{"value":"1322.03030","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2850842$29545FB3-E23F-4874-B048-6F162BC432A6","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"8faf366055cf4a27c89aa0fbfa6aa23c395cf96c","datavalue":{"value":"10.2168/LMCS-9(3:29)2013","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2850842$05737877-66E4-4753-86EF-D64DD78BB6B8","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"96a79d9e749e94f65576b1899e96905ca07e98e1","datavalue":{"value":{"entity-type":"item","numeric-id":234593,"id":"Q234593"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2850842$6470D736-DA13-4436-9914-B826E6096A52","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"da58c52dc46c86e7440f2499c9e1bef3537c5562","datavalue":{"value":{"entity-type":"item","numeric-id":2786118,"id":"Q2786118"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2850842$18199EE0-33AE-45B5-9E70-0C47BCACB501","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"0be16a8cf879826ec9b43c7ef26beec0c95f97d9","datavalue":{"value":{"time":"+2013-10-01T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2850842$2D957B1D-43F7-4440-A5F4-8673B80E0F60","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"35153c3d6296b99cbd97d5bd56d9646c2006f099","datavalue":{"value":"https://arxiv.org/abs/1309.5544","type":"string"},"datatype":"url"},"type":"statement","id":"Q2850842$D039F335-2F60-42C9-B88A-4927AB2DBEB1","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"33d9ad5fa3901c3c85d59a42af89ee043a9f83fb","datavalue":{"value":"03D10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2850842$1EA3952F-FC2C-4AE7-8DF3-4626D6D6AC90","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4c09ea78484192dfb20180fed0b8ec0fbe50483f","datavalue":{"value":"03D60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2850842$4345B38F-92CB-4FB4-B70C-832EEEBE32EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"cde05172e5f9c37cef740a3519be6dc5014d282e","datavalue":{"value":"03D70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2850842$7E5AF8E0-CB6F-4174-8707-199C51BF728D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"0afd88b1963152e20c10cb6008c5709137adf620","datavalue":{"value":"6213051","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2850842$F10C0DBD-2623-46DC-A0A8-BB30EAC9F9C4","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"92caf16c6ea57f9885da64f74196f15c97c0ebb4","datavalue":{"value":"alternating Turing machine","type":"string"},"datatype":"string"},"type":"statement","id":"Q2850842$4CA65347-3043-4C8F-B89E-2864C767C8FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f1d96d709c8f4e9a0a79152c04fa22197c5171ce","datavalue":{"value":"inductive language","type":"string"},"datatype":"string"},"type":"statement","id":"Q2850842$EEE11229-C642-49A8-956E-4833B82D5D17","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5ac7169be004a20e8c87c2a37a03a6963f94b2be","datavalue":{"value":"hyper-elementary language","type":"string"},"datatype":"string"},"type":"statement","id":"Q2850842$E4B3F95D-38F9-4F0C-8645-88371E36E006","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6d3317fee091a183b95c82d29dc1e995b7455f26","datavalue":{"value":"arithmetical hierarchy","type":"string"},"datatype":"string"},"type":"statement","id":"Q2850842$51FDFD83-B4F9-4527-A7D8-572E7DEBD384","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"319f7aef6d48907b019428ced327b73484cf6132","datavalue":{"value":"polynomial-time hierarchy","type":"string"},"datatype":"string"},"type":"statement","id":"Q2850842$4CA57E3F-4746-4B78-AA03-ACC1403F3EE2","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":"Q2850842$E2CFE8CD-D3F5-424E-980B-4B7677A7F67D","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"0f6a0e259a338f20dd381e10ed02bfeea6195977","datavalue":{"value":"W1970516401","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2850842$5FB9A7B7-1002-4B0E-9934-0E0D30B5B1ED","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"a088734a78fdfff638a43caabc0e12caa258f8bc","datavalue":{"value":"In this paper, a new semantics of acceptance/rejection of an alternating Turing machine (ATM) is developed. It is proved that the languages accepted by such machines are exactly the inductive languages. An analogue of Post's theorem is established, which states that a language L is accepted by a total ATM iff L and its complement are accepted by some ATM, i.e. iff L is hyper-elementary. The languages in the arithmetical hierarchy are also characterized, namely as those, accepted by ATM with a bounded number of alterations. The approach deals directly with the inductive definitions and does not make use of transfinite induction on constructive ordinals.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2850842$613F1BD5-E75A-4E97-9323-0AC891E0B88F","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"5a03c77f7b094c62085e038e7319825eeca971a4","datavalue":{"value":{"entity-type":"item","numeric-id":593174,"id":"Q593174"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2850842$4601EFCE-0A6A-4AEB-9F6B-616ED9EB0D90","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9bdc3a3b0abb0fa1ad83e6040892066529f068b6","datavalue":{"value":{"entity-type":"item","numeric-id":4732455,"id":"Q4732455"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0ec7d941711d56146299c3297063bfcffa1915d8","datavalue":{"value":{"amount":"+0.7749518752098083","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":"Q2850842$4BCB5256-513B-41DA-BD6B-45F4A014B92A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"03b643515bd207abce0ede40769ddc1de75d1321","datavalue":{"value":{"entity-type":"item","numeric-id":3787476,"id":"Q3787476"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4a021a4e24df8d37e4539a6a0e10f01339368566","datavalue":{"value":{"amount":"+0.7515230774879456","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":"Q2850842$3699D4FA-65B3-4EEB-94D9-E1818C07A27A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f442fffe25a4fd7a0055e97005a1a7b2150768e1","datavalue":{"value":{"entity-type":"item","numeric-id":672377,"id":"Q672377"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a7fd3f170200ec3e6fb857ef5b9f3aac8189b514","datavalue":{"value":{"amount":"+0.742725670337677","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":"Q2850842$CAA47746-D915-4649-8B0C-9ED407EB02CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"afe8a31706c779d4ad1a32f918707a742efff71e","datavalue":{"value":{"entity-type":"item","numeric-id":4016734,"id":"Q4016734"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2b19e678a6d9818500f88636c85a914c2242f17c","datavalue":{"value":{"amount":"+0.7424596548080444","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":"Q2850842$B32369C7-A46E-4F97-9CDE-3DD89FA6BF44","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"48532a0d72af46793177d956393b76c72b386cb9","datavalue":{"value":{"entity-type":"item","numeric-id":3979274,"id":"Q3979274"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e9c2d320609fee0ae2716086c58752964d469a93","datavalue":{"value":{"amount":"+0.7423117756843567","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":"Q2850842$7F8E3869-59FD-4B9B-8926-4ACF6B71D09E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2850842","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2850842"}}}}}