{"entities":{"Q1111386":{"pageid":1122135,"ns":120,"title":"Item:Q1111386","lastrevid":66688653,"modified":"2026-04-12T11:59:39Z","type":"item","id":"Q1111386","labels":{"en":{"language":"en","value":"Alternating real-time computations"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4076624"}},"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":"Q1111386$C811BE29-3328-4E06-A23F-03AFF73D0626","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"2d76ca7c3e245d632b2110e36fcb825aab786ff0","datavalue":{"value":{"text":"Alternating real-time computations","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1111386$6D2909D1-2F56-4AEA-9DAD-A63BD7686AC3","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"2020ed2625a599257da6e450f8b52aa1307619a1","datavalue":{"value":"0658.68056","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111386$D6F30F06-8A25-4FC3-83C1-91B8F4F0E785","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"44186dee9ca6fe73009c34db0d0f47972d509d22","datavalue":{"value":"10.1016/0020-0190(88)90179-2","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111386$0A54A272-91D9-41DB-8EFD-CE13975A71AF","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"ae43f76052d81f9179fca07ae9c5059d792ae26d","datavalue":{"value":{"entity-type":"item","numeric-id":393130,"id":"Q393130"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111386$0CD0E92C-6EEA-4CAF-A5A9-FAD3E4086AA5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"b4a3cc0bfe801f09cbd0937faf566970ccae56d7","datavalue":{"value":{"entity-type":"item","numeric-id":1102113,"id":"Q1102113"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111386$89316F97-D050-4C6C-8DDF-496FBB28F95D","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":"Q1111386$844AF453-B801-495E-A710-7C72B8796C9D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"31a1937240ca4a323604b4728c31d242b5596d7c","datavalue":{"value":{"time":"+1988-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":"Q1111386$3938D717-F192-4CB9-88BC-850FD9BEF498","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"92943d83ccd8a9da4512f787d135afd8986c400b","datavalue":{"value":"The effect of the number of work tapes on computational power of real- time Turing machines is considered. Well known results state that k tapes are better than k-1 tapes in the case of deterministic machines and, for nondeterministic ones, two tapes are as good as many tapes. We show that alternating real-time pushdown automata recognize the same class of languages as multitape alternating machines working in linear time. It is also shown that the automata making a constant number of alternations and only one reversal recognize exactly rudimentary languages.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1111386$D08B8A0B-2509-4E4A-AD1D-CB0316E4156E","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7dde57cbaf704d564d8f981ca98d6340e3d4aaf","datavalue":{"value":"68Q05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111386$E7204EB8-793C-418D-96F4-CA5DB0FF7584","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111386$FDADDAF4-2A22-4548-BA1A-34802BF997BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111386$528845ED-33E0-44C0-A328-E58525A4881F","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"f118cf07a36b59dfede5bb295bbb5bd0c84178fd","datavalue":{"value":"4076624","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111386$93676413-7311-4FE0-A38E-EA7ADBA23B9B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"92caf16c6ea57f9885da64f74196f15c97c0ebb4","datavalue":{"value":"alternating Turing machine","type":"string"},"datatype":"string"},"type":"statement","id":"Q1111386$79C19912-599D-47C3-A0C6-87745F604EF1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0b04b0c12ba853bc6991c30e0d7b78a10ae28b65","datavalue":{"value":"real-time computation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1111386$718C87CE-06BA-412E-9E54-98B27F52485C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"456c672ca15cab74651e643baa7549046be81ae8","datavalue":{"value":"pushdown automata","type":"string"},"datatype":"string"},"type":"statement","id":"Q1111386$7E0A6EF7-033B-4F95-BACD-24F8ABD831C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0a5dd5acc6a9659d1e4123bef03c2ea2a150aee3","datavalue":{"value":"rudimentary languages","type":"string"},"datatype":"string"},"type":"statement","id":"Q1111386$A056B20E-C80D-4CF0-BF4D-DD3FC2EB6607","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":"Q1111386$35767B65-2DB5-4B36-AE2A-CD913A4BB210","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"ce9fd4540a5d12ec56b0d86b9e578107ff268a42","datavalue":{"value":"https://doi.org/10.1016/0020-0190(88)90179-2","type":"string"},"datatype":"url"},"type":"statement","id":"Q1111386$FFB21F22-680A-4E60-AB5D-083F72D5E4C4","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"47aabddad4c04a51926134e5a544832c4db560a6","datavalue":{"value":"W2073116366","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111386$F9A8CF02-E110-4B20-95B0-E6D0009F417F","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"248ec5667ec5a52c84f7c9aad98d22c2ca290e71","datavalue":{"value":{"entity-type":"item","numeric-id":4077448,"id":"Q4077448"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111386$805FEA5C-1C87-4722-BD9F-6FEB23333C98","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"80840438dbadfbf434a3cf20cc51a4c646a82e17","datavalue":{"value":{"entity-type":"item","numeric-id":5582342,"id":"Q5582342"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111386$DE3FA49D-0665-40F1-8668-04033AE74279","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8731edb0c474d8d59bfadb099ada71679c69643b","datavalue":{"value":{"entity-type":"item","numeric-id":4044135,"id":"Q4044135"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111386$CF6E02EA-00DE-4047-B25B-69CFC7222435","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9b3d2070efa35255ffc99b902e96d17375260cd5","datavalue":{"value":{"entity-type":"item","numeric-id":3347301,"id":"Q3347301"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111386$528785F9-BF76-4A3D-85D9-5E9E1BB94833","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5a589b2b8385ccd4be46b5ea02a14f7621bb80bc","datavalue":{"value":{"entity-type":"item","numeric-id":1141480,"id":"Q1141480"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111386$ACC4A92A-A497-4C77-95C6-6434F21ECA96","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a6f110f1fdd1b1965a6a71deaa20a3ec523c9cbf","datavalue":{"value":{"entity-type":"item","numeric-id":2526723,"id":"Q2526723"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111386$8A263486-D349-4EA6-9C38-2A0A9FF7E867","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4cce85947fd71c4f5850f59f036a4dd761cfae66","datavalue":{"value":{"entity-type":"item","numeric-id":4154070,"id":"Q4154070"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111386$5D6A6706-2AC1-4127-B192-0B996F87AF7D","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"11ff46c52b2b4cf5c87da4fb7499f7c693a6988a","datavalue":{"value":{"entity-type":"item","numeric-id":3330503,"id":"Q3330503"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6976dd5a4bc254c18405eca5d508c3cf8cb2cd8a","datavalue":{"value":{"amount":"+0.8864887","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1111386$D518F462-640D-4AAC-AAAF-347E8BA4782D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f2a58bb2bca2eff6614470819a4450ffa5e409d6","datavalue":{"value":{"entity-type":"item","numeric-id":1881935,"id":"Q1881935"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4527c39fc9a38cdbaf80806f554c175791cce670","datavalue":{"value":{"amount":"+0.8660829","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1111386$E7F984E3-B4D2-485A-AEBA-E47F54A6C51A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"227eb97a87ea4fe5c32ae163c407efbacf970581","datavalue":{"value":{"entity-type":"item","numeric-id":5089091,"id":"Q5089091"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d4e831e1c5adb9c2f7aca8cd55ad654f1ce4aee0","datavalue":{"value":{"amount":"+0.8615662","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1111386$960D897F-EBC8-4F9A-852F-E253AC523D0F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"67f9c82d25d81d6476902c239480196bacaac384","datavalue":{"value":{"entity-type":"item","numeric-id":1198025,"id":"Q1198025"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f3b4251458edc7a7270e1a02f105d9951fc09973","datavalue":{"value":{"amount":"+0.85756177","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1111386$80D6AF2D-0264-4C78-90D9-9C79F59EF2EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"42baa332527a80dbd4f733b16e965f3ffdc6957a","datavalue":{"value":{"entity-type":"item","numeric-id":4250651,"id":"Q4250651"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0fadab4e98749f4b5de375ef771b06027e087368","datavalue":{"value":{"amount":"+0.85679024","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1111386$89094141-C370-4950-A29C-E3F7F36B8178","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"76c75df99936b071ceb181e88df3a085e4ae623c","datavalue":{"value":{"entity-type":"item","numeric-id":6062514,"id":"Q6062514"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"be29965fbee22cf351c410ed4bd646a7b9b5bfff","datavalue":{"value":{"amount":"+0.85533196","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1111386$25D1C0DD-4CE9-443D-B958-3CB37D42521D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b06717c60dddef2e1da098bfef1d1e28214e4179","datavalue":{"value":{"entity-type":"item","numeric-id":2758309,"id":"Q2758309"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d657e1ef40b6437b3b12895f989ebdf8664c9802","datavalue":{"value":{"amount":"+0.85482675","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1111386$ABF56ED8-015A-4CBB-92F4-EBB5BE51540E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9fd784231969c9a6df6ff0a223392656be2fdf55","datavalue":{"value":{"entity-type":"item","numeric-id":438179,"id":"Q438179"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"880b9631369533b0da7bcb1a673e320f7857964a","datavalue":{"value":{"amount":"+0.84995735","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1111386$A7E0C70A-E357-4384-8E8A-A91069A84589","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7ff80af42b21fc1bebd0b63dfd9bf84f9d3df884","datavalue":{"value":{"entity-type":"item","numeric-id":2933634,"id":"Q2933634"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f063a0f4c490252fafda4ac170dca2654e0402da","datavalue":{"value":{"amount":"+0.84761107","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1111386$15E4B9CE-DC33-4430-A6DD-2309AC553474","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"24799c609db0d897c9ca6c709bad0933ceacc8c8","datavalue":{"value":{"entity-type":"item","numeric-id":5417713,"id":"Q5417713"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f063a0f4c490252fafda4ac170dca2654e0402da","datavalue":{"value":{"amount":"+0.84761107","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1111386$EE7A91D6-F1B2-4F53-8945-2E4B33849294","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Alternating real-time computations","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Alternating_real-time_computations"}}}}}