{"entities":{"Q1075759":{"pageid":1086511,"ns":120,"title":"Item:Q1075759","lastrevid":66792624,"modified":"2026-04-12T12:53:18Z","type":"item","id":"Q1075759","labels":{"en":{"language":"en","value":"Three-way automata on rectangular types over a one-letter alphabet"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3952017"}},"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":"Q1075759$874CC21B-6BD9-449E-A9FB-DD20D4C592BC","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b53aa764162949c8c11d3af43669f7fc11babaa6","datavalue":{"value":{"text":"Three-way automata on rectangular types over a one-letter alphabet","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1075759$C55DAF36-E1D0-410A-99A6-77CD0EC3A53B","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"82d6339ba9359f2cee4c25de23185657575b7b22","datavalue":{"value":"0592.68051","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1075759$A5D66D8F-E794-4776-B903-6474A000927C","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"f05069281658d4faaefd0323eaeb67a3c631b6a0","datavalue":{"value":"10.1016/0020-0255(85)90041-6","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1075759$D8C03ACD-2CCE-42E1-9C3A-583B87AA2759","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"ec3b29744c0c4a5e008618686519803ba2d0b097","datavalue":{"value":{"entity-type":"item","numeric-id":760794,"id":"Q760794"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1075759$4A080B1D-BFD0-47F9-9486-82EF6F550D6F","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"c144f0fb88440afe4b13555aedcc8676a016b6d2","datavalue":{"value":{"entity-type":"item","numeric-id":70466,"id":"Q70466"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1075759$282D4A15-430B-4043-A39E-D10AB98AC7D7","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":"Q1075759$4733F825-E70D-4A24-9A38-E7A17BBA85B8","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"5ff8ecddbce61e09c89a278ba23c08ce7b5b57c9","datavalue":{"value":"Three-way automata (in short: TWA) are automata working on 2-dimensional tapes which can only move in the three directions: ''down'', ''right'' and ''left'', - but not in the direction ''up'' as the usual 2-dimensional automata, thus being somehow the generalization of 1-way finite automata.    For deterministic TWA over rectangular tapes with a 1-letter alphabet a necessary criterion for a 2-dimensional language to be acceptable is given, which is based on the calculation of linear and bilinear forms by which such a language has to be representable as a set of pairs of non- negative integers. Using this criterion it is shown that the non- deterministic version of these TWA is more powerful than the deterministic one, and also that the disjointness and the inclusion problems are decidable for languages acceptable by such TWA, while these problems are proved to be undecidable if non-unary alphabets are allowed.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1075759$07986FB3-CEA9-479C-824E-CFAEE20533AC","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1075759$B9C1F4A2-E122-4477-8CA7-DB80EB78B077","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"7a09631852aa109972657266d9779b972642c9de","datavalue":{"value":"3952017","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1075759$E0E2F5CE-B447-4134-81A7-C2C5907B7156","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"548cb01edc097b73c5b245342a50b1bd3a631877","datavalue":{"value":"nondeterministic three-way automata","type":"string"},"datatype":"string"},"type":"statement","id":"Q1075759$2FB838E7-88A9-4B39-A25E-FBEC42F6F977","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"27638d630e18a79d37aae3ab247a2d08a15508a4","datavalue":{"value":"decision problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q1075759$14BE8B4B-A6F0-448B-B800-D9AD30B79B7B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b5b832a1d8c01e147767c3ed4849695fe2f65cbd","datavalue":{"value":"2-dimensional language","type":"string"},"datatype":"string"},"type":"statement","id":"Q1075759$DD5C0FC0-0EC1-4F34-9102-21D8587A1A9D","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":"Q1075759$CD87BC58-B9A6-49B7-A03E-EBA714B40028","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"804f957f274b19896bc952469281056df2e1454c","datavalue":{"value":"https://doi.org/10.1016/0020-0255(85)90041-6","type":"string"},"datatype":"url"},"type":"statement","id":"Q1075759$7314F69B-8D2D-4DD0-8CAE-CB659A2B21E3","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"de749cf7049ae12bae8e5f18beca24dc69ae37c0","datavalue":{"value":"W2033612691","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1075759$E65B7093-681D-4001-9047-FACDD295AFAA","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"6a48351eb9ce98139556478b870511c74c7f43f4","datavalue":{"value":{"entity-type":"item","numeric-id":3926078,"id":"Q3926078"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1075759$A6EB5B72-A7AB-4E50-8DE2-33C78F402E90","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3a65188b05885df1e8d62c4b63a1df182d0f915a","datavalue":{"value":{"entity-type":"item","numeric-id":1149774,"id":"Q1149774"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1075759$A2D4EC71-8F97-4F4B-8A14-8C11EC2DD53C","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":"Q1075759$6B2F5E78-7D6F-418C-92FB-060262D908BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c4b1d274c6ee4b9c24930fb83b43c12797e99121","datavalue":{"value":{"entity-type":"item","numeric-id":5590814,"id":"Q5590814"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1075759$1DA91FC1-CA7A-47D8-9E97-CFF2F0473A00","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7c985543fdcaa4256c65675c41fa22f42e889c77","datavalue":{"value":{"entity-type":"item","numeric-id":3051389,"id":"Q3051389"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1075759$3B55DE25-D321-4156-B75C-10CCB818F6F8","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1412a90e6514546ff8eeb33144eada6e8b115ef7","datavalue":{"value":{"entity-type":"item","numeric-id":2177610,"id":"Q2177610"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f39909b3953d421d5346c05ad5291ad85769c158","datavalue":{"value":{"amount":"+0.8065523505210876","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":"Q1075759$D1F01418-BA36-49DD-81D7-8F1C6B61D128","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"87fb350e7d639e5cafcf9c6b234390318a39e1cb","datavalue":{"value":{"entity-type":"item","numeric-id":2489224,"id":"Q2489224"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c13f70650d1e9020a0ecc5e65f52f251f1621a6b","datavalue":{"value":{"amount":"+0.8029974102973938","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":"Q1075759$5E0E60E5-73A8-4FAC-9494-E518707E270F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2a1f0474389746133792ef0a23a834c36f200fef","datavalue":{"value":{"entity-type":"item","numeric-id":1077165,"id":"Q1077165"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"42dad28b0be8586cc4bb37bdda5503db79a9237d","datavalue":{"value":{"amount":"+0.7999294400215149","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":"Q1075759$224E70E9-F851-427C-811D-9B3863E90D29","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b7c17cdb9919b160ccfbbdbe3eb596ebc5a24556","datavalue":{"value":{"entity-type":"item","numeric-id":1193834,"id":"Q1193834"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6be99bb50233e0f43fa7302e12021889c4131fa3","datavalue":{"value":{"amount":"+0.7963898777961731","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":"Q1075759$4E15222E-B03C-41BE-BEBA-BD111C8359B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e3a55d693deeb3ace4bd3cc1600fbfd63c81abd1","datavalue":{"value":{"entity-type":"item","numeric-id":1116697,"id":"Q1116697"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6be99bb50233e0f43fa7302e12021889c4131fa3","datavalue":{"value":{"amount":"+0.7963898777961731","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":"Q1075759$722037DD-9847-4B58-9C93-5E0FD4A06E40","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Three-way automata on rectangular types over a one-letter alphabet","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Three-way_automata_on_rectangular_types_over_a_one-letter_alphabet"}}}}}