{"entities":{"Q1058864":{"pageid":1060712,"ns":120,"title":"Item:Q1058864","lastrevid":66651609,"modified":"2026-04-12T11:33:59Z","type":"item","id":"Q1058864","labels":{"en":{"language":"en","value":"Fooling a two-way nondeterministic multihead automaton with reversal number restriction"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3902071"}},"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":"Q1058864$DE4BF034-CC74-48A5-BF64-8F51364650EF","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"d87a45ad74d115e96589a1cfdbbd2e66a5ca4835","datavalue":{"value":{"text":"Fooling a two-way nondeterministic multihead automaton with reversal number restriction","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1058864$FDDE0428-A32C-47D3-9703-26DF796AAD35","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"a1c1ecacc11e734f10b370a0df2c70674d436af5","datavalue":{"value":"0565.68078","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1058864$09B59335-1210-449A-82F6-FDB9B9C7A9F5","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"7d0f02e85530cd06ceb2c58a40dc9c2e0258e194","datavalue":{"value":{"entity-type":"item","numeric-id":161641,"id":"Q161641"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1058864$147D50C4-8B08-455F-A46E-2F4257672958","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":"Q1058864$A9C53062-1578-48F9-9157-118B770B0053","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"6fe9187ecb19136320ceb302a7a253a3ea9addba","datavalue":{"value":"We define a language L and show that it can be recognized by no two-way nondeterministic sensing multihead finite automaton with \\(n^ a\\) reversal bound, where n is the length of input words, and \\(1/3>a>0\\) is a real number. Since L is recognized by a two-way deterministic two-head finite automaton working in linear time we obtain, for two-way finite automata, that time, reading heads, and nondeterminism as resources cannot compensate for the reversal number restriction.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1058864$18B3BEF5-E14C-4BC7-82A6-3DA5EB780ADE","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1058864$544C6933-2B12-4F7A-89EC-A1D6D93ECC56","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"46622472f9f5ca1134e9006d02a09baa6be06b82","datavalue":{"value":"3902071","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1058864$2ADEDC27-1D6D-4162-8CE7-168F705B6C30","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3185021b00685258fcbe972d85da90b82d2ed2cd","datavalue":{"value":"multihead finite automaton","type":"string"},"datatype":"string"},"type":"statement","id":"Q1058864$47A8E660-E205-4D94-BCFD-318BDD2C6E99","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a32bf88c7c8ec5610d5711694a5739d5304ef7fd","datavalue":{"value":"two-way finite automata","type":"string"},"datatype":"string"},"type":"statement","id":"Q1058864$66B6E976-F3CE-4F93-B8CA-71B89D6C7A55","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f532e2b08234dd6967fc70eafbf0c8f20a836d3e","datavalue":{"value":"nondeterminism","type":"string"},"datatype":"string"},"type":"statement","id":"Q1058864$D8D863C5-54EF-4329-99B0-559B1092E2F6","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"e7330faa8aa9bfbfa602624605066aa6301d76b4","datavalue":{"value":{"entity-type":"item","numeric-id":208754,"id":"Q208754"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1058864$2E14311E-4101-4C1E-B552-9DC3BFD93EEE","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":"Q1058864$43E1951F-E53A-464B-9FE5-16E89AED40FA","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f44e0e7ffe3935a21e28f28f54373356aaa68323","datavalue":{"value":{"entity-type":"item","numeric-id":3100940,"id":"Q3100940"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d92d6967ecbede3c71805006bbc3c17a2c16f10d","datavalue":{"value":{"amount":"+0.87074864","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1058864$3AB8C329-8159-4030-AC58-8AA3041396FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a6915fa9d2f66f57533bd0de973b93fa3df72158","datavalue":{"value":{"entity-type":"item","numeric-id":3793732,"id":"Q3793732"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cd694b93b5b2aee7f519175ee670090997282d96","datavalue":{"value":{"amount":"+0.86547196","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1058864$093D6CE5-3D4A-4327-AFEE-4A957030559F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"68022ec70cfcf9446b023bcbeddd2947e892c07b","datavalue":{"value":{"entity-type":"item","numeric-id":1763701,"id":"Q1763701"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e8bfa992f5eb1638519b6f350866cbc6c89899bc","datavalue":{"value":{"amount":"+0.858923","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1058864$3BEB7C3C-16AF-4D18-865F-5D4A1AE40979","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9bc4916464d8ff62e0f591af0eca2a3626d6f86d","datavalue":{"value":{"entity-type":"item","numeric-id":3453732,"id":"Q3453732"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fe2a3721025eb5ccb687db9e8f91da89a39f3c63","datavalue":{"value":{"amount":"+0.8486414","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1058864$6A9DEC1B-59B1-412A-96C7-291AFFA088C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ab59205b088b2ab620901be4c6ed2967445ee9c3","datavalue":{"value":{"entity-type":"item","numeric-id":2378520,"id":"Q2378520"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c441504bde2aa06c9845570c25d13d482d0383b5","datavalue":{"value":{"amount":"+0.8480123","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1058864$52056600-A375-4609-9D86-5B90E1F8FB7C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2fbe0692e98e440a1847fe62fbcafb5071abe426","datavalue":{"value":{"entity-type":"item","numeric-id":4941906,"id":"Q4941906"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e47dbfd3f07c28c8fe2c506b1c222b2c78796b5b","datavalue":{"value":{"amount":"+0.8450975","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1058864$9239D5FA-81B3-4A9F-87C2-CCB735E2BD08","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8dbb698c8add825bea6fb661cbfe5d700d104a1a","datavalue":{"value":{"entity-type":"item","numeric-id":3453731,"id":"Q3453731"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a7e58924972675430208e297cd5588b2cdd21361","datavalue":{"value":{"amount":"+0.84387046","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1058864$F64F624D-A9B3-4F64-91BE-BEC3A5C2C462","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b9c513bcf593b27d062bbe51327ab53cbd2af3c6","datavalue":{"value":{"entity-type":"item","numeric-id":2358688,"id":"Q2358688"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a7e58924972675430208e297cd5588b2cdd21361","datavalue":{"value":{"amount":"+0.84387046","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1058864$7799EF06-C3F2-43A4-8687-12F55204BE26","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a3dcd164e48b174f72034a3553f6340245b8d765","datavalue":{"value":{"entity-type":"item","numeric-id":714812,"id":"Q714812"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b25793a99beb7b13582dc8fdcf5ac8aeae25746b","datavalue":{"value":{"amount":"+0.84200597","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1058864$5C036D9E-0DB6-40CC-B656-1488C6A40C02","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e6a4e08341e5ed6b01190b85440c8d3204558cdc","datavalue":{"value":{"entity-type":"item","numeric-id":3075514,"id":"Q3075514"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b25793a99beb7b13582dc8fdcf5ac8aeae25746b","datavalue":{"value":{"amount":"+0.84200597","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1058864$C003014F-3FD9-4E5E-A7EE-9E30F443BC3A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Fooling a two-way nondeterministic multihead automaton with reversal number restriction","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Fooling_a_two-way_nondeterministic_multihead_automaton_with_reversal_number_restriction"}}}}}