{"entities":{"Q2105419":{"pageid":2116162,"ns":120,"title":"Item:Q2105419","lastrevid":78336506,"modified":"2026-05-06T11:21:04Z","type":"item","id":"Q2105419","labels":{"en":{"language":"en","value":"Converting nondeterministic two-way automata into small deterministic linear-time machines"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7629132"}},"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":"Q2105419$22BD455E-7EFA-4FFE-8F7A-3DE509390A1B","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"011e2dfa21c4af2a2b83e01b49999bdb8fb64310","datavalue":{"value":{"text":"Converting nondeterministic two-way automata into small deterministic linear-time machines","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2105419$65B8F5E7-1823-4167-811A-2BBE55EA4F69","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"ee80d33249f6fe61dc3fab7e3289aad7c356b7dc","datavalue":{"value":{"entity-type":"item","numeric-id":476167,"id":"Q476167"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2105419$CD2E8A0E-1B12-41EE-B590-1A773C784601","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"9f920db5aff0a8e6518a5a866c3161192fca7ec8","datavalue":{"value":{"entity-type":"item","numeric-id":383364,"id":"Q383364"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2105419$0A04C429-0333-44B4-B48D-EEDCA855A674","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"924b6ec4e7d17376e49057a32e6bc29eccfc0fb3","datavalue":{"value":{"entity-type":"item","numeric-id":777994,"id":"Q777994"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2105419$82523A3B-E6A3-4A49-95D3-E527FB498F20","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"624988392b6d2b54af82e42a16a992d36a135073","datavalue":{"value":{"entity-type":"item","numeric-id":896687,"id":"Q896687"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2105419$98B5CF18-D97A-47CB-97E9-4EA1C31D7619","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"fa2d1ad91af9619c8dd37ab889fe279a84c4057e","datavalue":{"value":{"entity-type":"item","numeric-id":259032,"id":"Q259032"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2105419$4DCF60F0-8136-4043-867E-A8F4AD773F51","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3ffbf7a5071d227412d80225c3d73ff104ccb41d","datavalue":{"value":{"time":"+2022-12-08T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2105419$9B1235A1-3AC7-4BFF-9B03-FEC42CD4FF5A","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"77938d552b5bd34a21bffc1958d028247eb3958d","datavalue":{"value":"https://arxiv.org/abs/2103.05485","type":"string"},"datatype":"url"},"type":"statement","id":"Q2105419$0984FAFA-5C3F-4706-BBE2-69A5D362BEFB","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"f969879f531643f058f8dd4c87a7dd4eb7b8c4c8","datavalue":{"value":"68Qxx","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2105419$60C4DA9E-DF81-4CBB-8212-6E8AB7EE431C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"9aac6d6d97c6ae18862b23417a629877bff39d7c","datavalue":{"value":"7629132","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2105419$C7DE8709-81A9-4A63-91BD-B562C41DB5A1","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5f1d0a4717e5e83922eac100c9f71e41e4772e9d","datavalue":{"value":"one-tape Turing machines","type":"string"},"datatype":"string"},"type":"statement","id":"Q2105419$EF6D517C-283E-4C55-A78E-C4FB868C1ADA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"30b76c413e003a911fe85e63ea43fc46735e7524","datavalue":{"value":"two-way automata","type":"string"},"datatype":"string"},"type":"statement","id":"Q2105419$6D3D8944-FA43-4301-83C9-0F9883423DBF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d6b3ac5948a51082073fe08b55937180405a1900","datavalue":{"value":"descriptional complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q2105419$D9F6889D-CA46-49A1-AC81-8EC297D67B85","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"67a78c1d18ef24838aa51e433ee207c15ff219c8","datavalue":{"value":"Sakoda-Sipser conjecture","type":"string"},"datatype":"string"},"type":"statement","id":"Q2105419$D260AB74-3D99-4AC1-AF0A-53E85C930588","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":"Q2105419$922633CD-78E1-49EA-AC30-52FCD409ADEF","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"b19a8d53c8d66554802a85e338b11b10a5618e67","datavalue":{"value":"W3134046426","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2105419$AAA76C75-E440-4C36-A030-EC994F912AFB","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"8242097883fe910594abf948861efbc5efe6f9d3","datavalue":{"value":"Q114172424","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2105419$7CCF342B-27E0-4926-9D09-DE39C3940C85","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"52f06b5088af884619b650afcefaab169691ff5c","datavalue":{"value":{"entity-type":"item","numeric-id":5404943,"id":"Q5404943"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2105419$B974D9A8-62BF-48BB-B639-952695897A9A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e276e9b980cb8a917c2ac52bfc256219d9a02973","datavalue":{"value":{"entity-type":"item","numeric-id":1622984,"id":"Q1622984"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2105419$D1FEC9A3-4FB0-4180-B96E-17367AA00785","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a900a1b2fff17c3475869d05f2ce6a6836bfa390","datavalue":{"value":{"entity-type":"item","numeric-id":4991691,"id":"Q4991691"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2105419$D10E4AF8-BFB2-45EA-B797-45D801E475EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2895d38e84959fa044f17e857d94d9610315ab03","datavalue":{"value":{"entity-type":"item","numeric-id":5541340,"id":"Q5541340"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2105419$819B9734-68AC-46A6-81AB-65E589E0A9E8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ccdc1c059ddccdc607bb186ec3b0db43c984f471","datavalue":{"value":{"entity-type":"item","numeric-id":963066,"id":"Q963066"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2105419$D4494FCF-05F1-4E4F-BD0C-AC986E47D548","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b144b493fd00490d34a81eb64611653df5187a38","datavalue":{"value":{"entity-type":"item","numeric-id":5859666,"id":"Q5859666"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2105419$D738BD5E-E3A1-44E9-A827-FE055EB1215A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dab107e270539e08732f99ceb4b022a863c9a7e2","datavalue":{"value":{"entity-type":"item","numeric-id":3707408,"id":"Q3707408"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2105419$0AB8CF6F-C042-451D-A1EA-7B59B41AF8E9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e4b234829d96b424c51e7a47a4c66f651ee99cb9","datavalue":{"value":{"entity-type":"item","numeric-id":5173292,"id":"Q5173292"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2105419$5F044E75-B9AF-4260-9D09-2EC1568824B9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3774babb4e5b030b84bfaa31934d5cbb1c567be7","datavalue":{"value":{"entity-type":"item","numeric-id":5915989,"id":"Q5915989"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2105419$C95EA4C2-F6FC-48B7-BA39-2FBDC9C29681","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"14fb011395b085a0ad4513663cab5f1c04c8f557","datavalue":{"value":{"entity-type":"item","numeric-id":5638291,"id":"Q5638291"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2105419$223814CB-B21E-4A61-BE87-8576FAD6590D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8728ed2ad3f041fd3c8e463f372116c6b1527275","datavalue":{"value":{"entity-type":"item","numeric-id":5599173,"id":"Q5599173"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2105419$9815ACD5-BD26-451A-985B-A1E27EFFE612","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"48ef22420c094c9829c91a792531abc0f9cd47bf","datavalue":{"value":{"entity-type":"item","numeric-id":5545959,"id":"Q5545959"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2105419$9A2EAD59-594F-49B8-8078-90A7DC14BDE1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d4ac4318fc0fef5b6593a17522dc23886246b7c7","datavalue":{"value":{"entity-type":"item","numeric-id":1183577,"id":"Q1183577"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2105419$A1A76845-8951-49E8-9C27-8E329EDA6044","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fc685d5ff47f8019349b0b0b238cb6f820c63bbe","datavalue":{"value":{"entity-type":"item","numeric-id":5192993,"id":"Q5192993"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2105419$A09019D9-13C1-44C0-B3CB-7FCDA085309A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"269d3916085b6fbd314908c8f6c2115d9dc2dce7","datavalue":{"value":{"entity-type":"item","numeric-id":1041220,"id":"Q1041220"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2105419$46E7522D-74EC-476A-AA72-BFB64BCC0557","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fd7c6229f4b94d10acb3721769855cfef4d3336a","datavalue":{"value":{"entity-type":"item","numeric-id":5402568,"id":"Q5402568"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2105419$28A12B53-5F4B-4A00-AABE-7F7DA558942A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8cefb9a02cd8afa92c4f64025ce5aa38fd77268d","datavalue":{"value":{"entity-type":"item","numeric-id":1145513,"id":"Q1145513"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2105419$09C5143F-EC9E-4EB8-8469-92C73D4B8DEC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b869e4b3f51a07116e5255bcca043e67cc40af26","datavalue":{"value":{"entity-type":"item","numeric-id":4449194,"id":"Q4449194"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2105419$C11C936A-B56E-4037-8FC6-4E244B62BB99","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"143ce62f94785035f75b6abbf71ffc58d57e659c","datavalue":{"value":{"entity-type":"item","numeric-id":1951583,"id":"Q1951583"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2105419$91CCBB84-D093-40E7-950F-3B60B8BF3BB3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d519a35259c49cddeb671f34227cf4294f3065e7","datavalue":{"value":{"entity-type":"item","numeric-id":1401239,"id":"Q1401239"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2105419$758175F4-0C65-4EE7-B85D-6EEE7FE4E3A0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e8f111504c80b9c33d4868eb46b14fa0f842d84d","datavalue":{"value":{"entity-type":"item","numeric-id":2354593,"id":"Q2354593"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2105419$D187CA36-99F9-41F3-A449-FDAF84212F28","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dc702350a57e33c22ee8ce3abc1d9026d4316b3d","datavalue":{"value":{"entity-type":"item","numeric-id":5747095,"id":"Q5747095"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2105419$2AB1DB05-9CE5-435F-A342-2A64A6B0B8D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5245f78de6b31d7733250de52e4d885bfce4143a","datavalue":{"value":{"entity-type":"item","numeric-id":5596247,"id":"Q5596247"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2105419$9FD4B073-3E14-4B63-B665-4F214801973B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b1758902a66e2332f9d1d0268ecf38eeeb4d377f","datavalue":{"value":{"entity-type":"item","numeric-id":3862379,"id":"Q3862379"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2105419$F132C72A-5D7D-4A04-8F3F-FE529476DBD0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6926e920f34ad943bbe1de8ce4a6882fa67a950c","datavalue":{"value":{"entity-type":"item","numeric-id":5596812,"id":"Q5596812"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2105419$35DD02A2-6BA9-42DB-84ED-A80EC5D9AF1D","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":"Q2105419$438B4C63-3708-47BB-A899-02A0BB105388","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1333d7e64c043713bf2f2b186ba99d32252a526d","datavalue":{"value":{"entity-type":"item","numeric-id":2254505,"id":"Q2254505"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2105419$BC3B211D-3E62-4672-B3AB-FA730B8737C5","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"e0b0d8c8cf13b0635171b72a2b501d38054ac7c0","datavalue":{"value":"10.1016/J.IC.2022.104938","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2105419$7DD679E9-A47E-427D-A651-952FD0C52F97","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d090350a5d2872a231cfc2506d37a4bac14e9282","datavalue":{"value":{"entity-type":"item","numeric-id":1622984,"id":"Q1622984"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a4c47fddf36cdc6f549807823fb5ee5c6be7aacf","datavalue":{"value":{"amount":"+0.8725974559783936","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":"Q2105419$92AEFF19-2F9F-42BE-A6CC-DFE737579B94","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6a439db001bbe3595b7e59340c3ea7f165eb390f","datavalue":{"value":{"entity-type":"item","numeric-id":4986301,"id":"Q4986301"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"22208d480c847faa7d439599a66f09a838c4c8b8","datavalue":{"value":{"amount":"+0.8153505325317383","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":"Q2105419$D5920A54-E220-431B-B65A-E0083D26BD32","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"47681e7d03783bdd50f595146ed9f2b04f80755a","datavalue":{"value":{"entity-type":"item","numeric-id":4785462,"id":"Q4785462"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7daf51c13fe3b7d5b6dc5829131193e3687b7514","datavalue":{"value":{"amount":"+0.7929621338844299","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":"Q2105419$89E15796-0295-4706-AC8E-D15DE25BCE28","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"02fabeac7d24dcceb13d777d140129110a25b2a7","datavalue":{"value":{"entity-type":"item","numeric-id":1401239,"id":"Q1401239"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d5dc6b73108f0362810517afbc586d87f51c9832","datavalue":{"value":{"amount":"+0.7892934679985046","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":"Q2105419$FA678BA6-F5CD-470B-8343-33F76D81DC49","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Converting nondeterministic two-way automata into small deterministic linear-time machines","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Converting_nondeterministic_two-way_automata_into_small_deterministic_linear-time_machines"}}}}}