{"entities":{"Q1058853":{"pageid":1060701,"ns":120,"title":"Item:Q1058853","lastrevid":66651510,"modified":"2026-04-12T11:33:57Z","type":"item","id":"Q1058853","labels":{"en":{"language":"en","value":"Alternating simple multihead finite automata"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3902048"}},"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":"Q1058853$EF201661-47D7-4779-9B77-D9A63AE77D3E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"5fb52570a5b796a3568082fbd78d6e4599ef9db7","datavalue":{"value":{"text":"Alternating simple multihead finite automata","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1058853$9FC9DFE3-DC1D-4BAA-9C39-B5B06B62CE6E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"44f401773e609e299e1f9919ae2c0e80762279bf","datavalue":{"value":"0565.68055","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1058853$FB42586E-A026-421E-A462-698EDCBA8BE0","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"26b05b2c432ab86746376d320f009cf7812769b9","datavalue":{"value":"10.1016/0304-3975(85)90048-9","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1058853$F9227B69-CC35-47BE-A9C6-5997EE35891B","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"6ad446f53048d18e17e90daa8df27d575d795a65","datavalue":{"value":{"entity-type":"item","numeric-id":610145,"id":"Q610145"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1058853$0F9083EB-BF5D-4758-8707-C8550EC24A2B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"31bccc448a658f3cebcea86acdb202419da8ddc4","datavalue":{"value":{"entity-type":"item","numeric-id":235704,"id":"Q235704"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1058853$0FC96921-B8A9-4290-B6E4-4F3B51386867","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"82a53663cfa905d5404409589cc6c9ad6ae3c848","datavalue":{"value":{"entity-type":"item","numeric-id":593783,"id":"Q593783"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1058853$76C0A572-6B59-4274-AB1D-842D73D4DA2F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ef7ca1ef17249af5269bfc02ced493a4476940cd","datavalue":{"value":{"entity-type":"item","numeric-id":593782,"id":"Q593782"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1058853$CBBA9E57-4C0B-4DB9-8B37-7FC17479BC72","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":"Q1058853$09349D53-53EA-46D2-91D7-6E24B7819971","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3c94df5c9af0ede578c52141befd29044de13172","datavalue":{"value":{"time":"+1985-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":"Q1058853$81634F94-6E70-436E-A005-F76A3D514904","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"5c06e4c16058dde9565734cd3f1d2d3d15087870","datavalue":{"value":"This paper introduces the alternating simple multihead finite automaton (ASPMHFA), which can be considered as an alternating version of a simple multihead finite automaton (SPMHFA). We first show that ASPMHFA's are equivalent to ordinary alternating multihead finite automata. We investigate a relationship among the accepting powers of SPMHFA's, ASPMHFA's, and ASPMHFA's with only universal states. We next introduce a simple, natural complexity measure for ASPMHFA's, called 'leaf-size', and provide a spectrum of complexity classes of ASPMHFA's, based on simultaneously leaf-size, the number of heads, and the move directions of heads. We finally investigate closure properties (under Boolean operations) of ASPMHFA's.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1058853$FAF2053D-AD15-4D97-969D-7A1D96B9FAF7","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1058853$928F0A0C-6ADA-4BD0-8879-731BBC15FB04","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7dde57cbaf704d564d8f981ca98d6340e3d4aaf","datavalue":{"value":"68Q05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1058853$C6F496F0-A7D4-484C-BAE9-D26B9F5251F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1058853$C256E8EA-D8D4-45F0-8792-CAA912C414EC","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"e969842d7c73d69d329dc46b66d268d5da640ec4","datavalue":{"value":"3902048","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1058853$ADB935EB-5236-4738-B99E-2C56F2E2788B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ab9aacd18c8eb22168e54bfedd7659da22e33282","datavalue":{"value":"accepting powers","type":"string"},"datatype":"string"},"type":"statement","id":"Q1058853$524CFFDA-1032-4A69-B626-F650B31EAED1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4ec171027d1650ccf5b7f14821b846bd5dc75680","datavalue":{"value":"complexity measure","type":"string"},"datatype":"string"},"type":"statement","id":"Q1058853$3F6A1978-62F4-4A87-8131-3BD4CDB69F91","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1408da7db4c03e08918a50622f2fb337e63ab39f","datavalue":{"value":"complexity classes","type":"string"},"datatype":"string"},"type":"statement","id":"Q1058853$7EA73C2A-9E4E-425F-8027-CBAEDEF02A58","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c9a7b03c1290f4420f511d8fcb71a4d38b5c445b","datavalue":{"value":"closure properties","type":"string"},"datatype":"string"},"type":"statement","id":"Q1058853$CED229E6-9636-449E-9AEB-A626C1ACDE71","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":"Q1058853$84BC7773-E37A-4ADA-AAE9-2A99D848438E","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"ba014acc991cff2be3b18590b3b770cef006302b","datavalue":{"value":"https://doi.org/10.1016/0304-3975(85)90048-9","type":"string"},"datatype":"url"},"type":"statement","id":"Q1058853$458DCE1C-7978-4F22-A5D6-3807469C602F","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"fb11f13c6d52482df847f09a4f62b11891626e89","datavalue":{"value":"W2034524526","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1058853$8CF43D8D-F07C-4285-9BE7-75E68CB388F2","rank":"normal"}],"P223":[{"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":"Q1058853$A139D598-38AC-4DD2-B04E-4BDF82E49DA7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"deb16111673c622cc1b0a57288970f5efa3d4a7a","datavalue":{"value":{"entity-type":"item","numeric-id":1056554,"id":"Q1056554"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1058853$E6345C04-C310-462E-A36E-257F2197820B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"efaa00c8a5f012e81078b9151d9eb7bc76ac3ae6","datavalue":{"value":{"entity-type":"item","numeric-id":3959454,"id":"Q3959454"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1058853$251EB49D-356A-4738-B6D1-556D97772E45","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d82c623f3446812c39e5ac3592eb9bf23663f505","datavalue":{"value":{"entity-type":"item","numeric-id":5561967,"id":"Q5561967"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1058853$5F726D8D-0C0F-47F6-B49F-61B93A47B3E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2043397a54eaa38033021fac24881dafefacec7d","datavalue":{"value":{"entity-type":"item","numeric-id":5592246,"id":"Q5592246"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1058853$471CD887-EB8B-42CC-BD6C-C4B1C0778906","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a5fceb2bd9c7d07fcf97a47a3cc2f3f7fc5055e4","datavalue":{"value":{"entity-type":"item","numeric-id":2559145,"id":"Q2559145"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1058853$356CE426-AFDF-4BB8-A77F-70FF803559B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d37a7732801448172e8ef7852ef3c4251ba24a4d","datavalue":{"value":{"entity-type":"item","numeric-id":1230657,"id":"Q1230657"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1058853$3FF15F92-3884-4196-BCD8-BF5A3FD2EE81","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d6e2f29ca49f5728b0cf7ea6bf3e38e11010db49","datavalue":{"value":{"entity-type":"item","numeric-id":1233317,"id":"Q1233317"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1058853$BC5E3BBD-11D5-45FE-89BF-3B3EDD060FB7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"723d1d7935ee6ee713edd9d034a6ee1341be2ccc","datavalue":{"value":{"entity-type":"item","numeric-id":1258608,"id":"Q1258608"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1058853$6C3C721A-4BC0-456E-9FB8-319C75C71F46","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"761e28b7c1c92f464b30b393991255d96d8e817c","datavalue":{"value":{"entity-type":"item","numeric-id":794169,"id":"Q794169"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1058853$1E17CB73-7A78-471D-B93B-8A18766BFF8C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f01762fa8f7ded31a8f52ad73e1fb766d8ae424e","datavalue":{"value":{"entity-type":"item","numeric-id":1116353,"id":"Q1116353"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1058853$AABC3C2B-CD3A-48EB-92F0-E32332CE0032","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2d7a5cbe509970988d7cea018b5abff3388bc71d","datavalue":{"value":{"entity-type":"item","numeric-id":1058853,"id":"Q1058853"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1058853$2EC742D3-3812-4459-9AAD-2B29626BB051","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":"Q1058853$085FBD7E-F113-4A75-B3E4-EF9EDEEBB774","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0751213ac1721d4b7bcbd9ddb031d0ca4971a705","datavalue":{"value":{"entity-type":"item","numeric-id":1145502,"id":"Q1145502"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1058853$3DC2A30F-1AE0-47CD-A89A-4F3C30CBB7E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a4f200ddc20c2d33390fb94670a066f08d95c0e9","datavalue":{"value":{"entity-type":"item","numeric-id":1215271,"id":"Q1215271"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1058853$7E86E138-CBB6-44FC-88BB-F0CC4BC0122B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0c27222bf14f645ce5dcbf19a53405c7ec8ff4d4","datavalue":{"value":{"entity-type":"item","numeric-id":4103516,"id":"Q4103516"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1058853$83F3E3A6-300F-4400-8C3C-964BB0F4E73C","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fa6241102352ba8b8aaa5e736fb56a4fe30c122a","datavalue":{"value":{"entity-type":"item","numeric-id":1116353,"id":"Q1116353"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"354be46535322835af68e356fe39e03d9ae8671c","datavalue":{"value":{"amount":"+0.8454368710517883","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":"Q1058853$CB11A8C7-1A4B-4229-B487-3881903448D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"71c5d6e817558c5f8af13843738b8d19d33e2e8e","datavalue":{"value":{"entity-type":"item","numeric-id":3745283,"id":"Q3745283"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7d6b34f7f53baef8b3081da732b51855127411f2","datavalue":{"value":{"amount":"+0.8346951007843018","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":"Q1058853$EC7463FB-963B-4DDD-A8DF-9B038D95BB09","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cfb8d1d1904c2d8695d34068e31dcb87fbd23e84","datavalue":{"value":{"entity-type":"item","numeric-id":3985352,"id":"Q3985352"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"df1ccb93d799154dbe46587ca61ed82df202953c","datavalue":{"value":{"amount":"+0.8287382125854492","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":"Q1058853$8EE19C1D-0A01-4337-BD07-5F0024DD2171","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"977bebe787146a4020ea17dbdea46499216b8911","datavalue":{"value":{"entity-type":"item","numeric-id":4364599,"id":"Q4364599"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c690e1f8d27518ed616912d2998848af14f81db0","datavalue":{"value":{"amount":"+0.8287244439125061","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":"Q1058853$D97A3F9E-DED2-4CD2-96AD-A57FE9D797C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3d229e6418e42a9ee49e5500e7ac2710f2c370b9","datavalue":{"value":{"entity-type":"item","numeric-id":3687716,"id":"Q3687716"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"29f3b5f638d28cc67bc21cefd72e3be58f3d2824","datavalue":{"value":{"amount":"+0.7897292971611023","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":"Q1058853$AE0A8634-77F1-4981-A6D3-D9ABFE1BF543","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Alternating simple multihead finite automata","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Alternating_simple_multihead_finite_automata"}}}}}