{"entities":{"Q792091":{"pageid":793939,"ns":120,"title":"Item:Q792091","lastrevid":42695557,"modified":"2025-07-08T13:51:10Z","type":"item","id":"Q792091","labels":{"en":{"language":"en","value":"Characterizations and computational complexity of systolic trellis automata"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3852434"}},"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":"Q792091$764B8140-068C-48CD-985F-5B21B2B536B6","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"d4e91e035f446e5c4a60f0bb79310af18a718cf3","datavalue":{"value":{"text":"Characterizations and computational complexity of systolic trellis automata","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q792091$4337C7B7-BB39-4531-A0B3-D955728DEBB6","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"19aaaa66adc9e058c06aec5a18ff647171091f82","datavalue":{"value":"0536.68048","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q792091$4F212DC2-91BC-495A-B971-1FD9E23BABBC","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"44257e285ad6cfb2485de49ad6c3f01969795db7","datavalue":{"value":"10.1016/0304-3975(84)90015-X","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q792091$39D40D2D-596A-4E48-9A1F-EEF98A0A66DC","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"d0ccf6eb6c37793d5bd821ffa019f577d6c7be3b","datavalue":{"value":{"entity-type":"item","numeric-id":243823,"id":"Q243823"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q792091$3825910A-9C07-4EC7-B69A-A566208CEF9E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"2c8ac2dd7e9a6ac8b1c666a65fae2b8a9cc6917d","datavalue":{"value":{"entity-type":"item","numeric-id":792090,"id":"Q792090"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q792091$9E041F4D-7038-4E15-AC8F-A20D795A1D67","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":"Q792091$D2A8036E-0F8C-4270-8E91-CFA960627FE7","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"2ee0f220147ae8bc749a64db56839865dbc4f127","datavalue":{"value":{"time":"+1984-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":"Q792091$F60E7228-3114-4F57-838B-5075BEAAD9F7","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"6d536c239f1d98e2a83c62e0fe6f0dfb88d5b9f1","datavalue":{"value":"Recently, \\textit{K. \u010culik II, J. Gruska} and \\textit{A. Salomaa} [''Systolic trellis automata (for VLSI)'', Int. J. Comput. Math. (to appear)] have introduced the notion of systolic trellis automata. In the paper under review, various types of triangularly shaped trellis automata (roughly speaking, networks of finite processors) both deterministic and non-deterministic ones used as language recognizers have been studied. Their computational power is characterized in terms of suitably restricted Turing machines. These characterizations allow translating of Turing machine programs into programs of systolic trellis automata which is remarkable insofar as systolic trellis automata work to a certain extent in parallel. Further results included concern the Turing machine time and space complexity of language families recognizable by systolic trellis automata.","type":"string"},"datatype":"string"},"type":"statement","id":"Q792091$B23A5BCB-701F-4889-A010-843D5C83B676","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7dde57cbaf704d564d8f981ca98d6340e3d4aaf","datavalue":{"value":"68Q05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q792091$FA883566-2A39-493D-B69C-61477B5AC67F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q792091$56A8C80A-09AE-4D31-B0CB-4A47E32A68A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q792091$6D044A84-AB62-492E-A808-BE71613BAA1C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"1cfee8f194ab6ee97598642e66af6391c7e844ef","datavalue":{"value":"3852434","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q792091$3045320D-F1F8-4DEF-B392-30B545079D29","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"203aa2220e42dda522d543c61cc9e25832c440e4","datavalue":{"value":"systolic trellis automata","type":"string"},"datatype":"string"},"type":"statement","id":"Q792091$5DF80665-DFF0-4BA9-BADA-C874E5C48C7D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4b2518fecb1c0b57735793eae5817ca06057a14d","datavalue":{"value":"Turing machines","type":"string"},"datatype":"string"},"type":"statement","id":"Q792091$13B1CD5C-1D51-4F3F-9935-7F979E7D2BED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dc8cd0ce5f8dd466fdf6e044ffa48a60932d73df","datavalue":{"value":"networks of finite processors","type":"string"},"datatype":"string"},"type":"statement","id":"Q792091$9FE83762-FE04-4C41-B8BB-DE1D36D6E0B3","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":"Q792091$E7EDA03B-BF12-46A6-8947-4723C8C3E598","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"2dc5e34cd32b22bbfaa8f9a52031cede94df9bc6","datavalue":{"value":{"entity-type":"item","numeric-id":5402502,"id":"Q5402502"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q792091$5DD7C37C-2215-4CAE-B0EB-AB610E12075A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0445ca81f1046c8b5bea1a2062f174b139078383","datavalue":{"value":{"entity-type":"item","numeric-id":1217591,"id":"Q1217591"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q792091$7420D19E-7EB5-4C53-89DD-A5F3522562D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"038a7e4418ac17f21ed0f4437cc57844c7dfca4e","datavalue":{"value":{"entity-type":"item","numeric-id":1230508,"id":"Q1230508"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q792091$4C796DC2-AF0A-44FF-B296-D81C8EDFC2E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"be8001a5615e3f4fe974a4d5d59e09f623287067","datavalue":{"value":{"entity-type":"item","numeric-id":3687723,"id":"Q3687723"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q792091$7E8CD9B4-984D-4982-9BEB-65940A752AC5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5d63c294dcd541a6bbb3f611bf33620bef8707e9","datavalue":{"value":{"entity-type":"item","numeric-id":3030260,"id":"Q3030260"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q792091$93C9BF0B-F312-4955-B10A-EFED54F98144","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"24f174e5eb3103f889bc208312e4071066863a13","datavalue":{"value":{"entity-type":"item","numeric-id":1168737,"id":"Q1168737"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q792091$76D64766-18C6-43C1-AA5A-0F8747848254","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"65ac23ff0d4cd9001f838ae713deecaccdfe50ad","datavalue":{"value":{"entity-type":"item","numeric-id":4089754,"id":"Q4089754"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q792091$9B529319-D701-4977-8BA8-145AADE2A233","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5af7139c65837eb8115c64cb4d4e1bbefc86dded","datavalue":{"value":{"entity-type":"item","numeric-id":4198075,"id":"Q4198075"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q792091$9B6CAEF0-252C-4B09-890F-0C4CA93FFB66","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":"Q792091$0CDBFA5B-0312-4429-81F3-2CC2B13C148D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c9d9a351340c0a47caca277d12ce9de6df36b217","datavalue":{"value":{"entity-type":"item","numeric-id":5536637,"id":"Q5536637"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q792091$F3120FA5-267F-41E4-BE9F-7B626F085473","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"755b705d434743289f1c33d94607b3327759f7e3","datavalue":{"value":{"entity-type":"item","numeric-id":4142699,"id":"Q4142699"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q792091$B9DBBF36-622F-4820-9CAE-8475304335A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bd6de3de50fb0979d02f6151c82cfa63f5ddf149","datavalue":{"value":{"entity-type":"item","numeric-id":4190126,"id":"Q4190126"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q792091$EDC3ABFE-0CD1-49D5-9666-CB0B90C8A36F","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":"Q792091$2DBF111C-CFD3-47E7-AC2E-C999C0A70341","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"aef4db4b14d21f10cc9279707ef41c59e564aba6","datavalue":{"value":"https://doi.org/10.1016/0304-3975(84)90015-x","type":"string"},"datatype":"url"},"type":"statement","id":"Q792091$BEEF9F51-238E-4200-AE03-46D90604E7E7","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"b4eb25b2bf350bba06b0b6bca9846b6f80c16b6f","datavalue":{"value":"W2085862166","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q792091$A3A83AA1-E195-4C7F-AD5A-1E74571979B9","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"614031b66fc02512b7bfff3250d984f078e6554c","datavalue":{"value":{"entity-type":"item","numeric-id":3030260,"id":"Q3030260"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cf1f84383f18b057c14523a9905e5267bf563209","datavalue":{"value":{"amount":"+0.95174676","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":"Q792091$8778CB38-37FA-4FED-AEB9-74D64325B140","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f7f6c5ab66bf5405dea2de169e77f0dd8a311a97","datavalue":{"value":{"entity-type":"item","numeric-id":3771620,"id":"Q3771620"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"942c4c999ce40045207f8171ccc019414c8cfc22","datavalue":{"value":{"amount":"+0.9200522","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":"Q792091$669BDF28-F068-4CB0-8A57-BF9A04FE8061","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"17922a95e19fb4f7d1bdd8a905fdf61f53ae5827","datavalue":{"value":{"entity-type":"item","numeric-id":3687723,"id":"Q3687723"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ed5a698ea7cb3e50e4752eac627331d2a747643b","datavalue":{"value":{"amount":"+0.9118684","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":"Q792091$6007BADA-A757-4A4E-B621-20E869239D7F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"30aefddf1eac8d132a51da577170a53fb36dd6a4","datavalue":{"value":{"entity-type":"item","numeric-id":3348431,"id":"Q3348431"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"49da839ddaf32e662f7fcfb66da83a64bd13fc33","datavalue":{"value":{"amount":"+0.9079497","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":"Q792091$ED2BAEEC-6E72-466E-B5D7-38F0B49FC89D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"de592608303281c87674d01bceecc1caba2d7f6c","datavalue":{"value":{"entity-type":"item","numeric-id":4206409,"id":"Q4206409"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b7b07d232861f8a625149d90feeb6d6aff00e2a3","datavalue":{"value":{"amount":"+0.9074594","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":"Q792091$F3658AA0-EF52-4B27-BF57-11154C462094","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"741567db0fcdeded139cbb98a8375c3dc7382bc0","datavalue":{"value":{"entity-type":"item","numeric-id":3687722,"id":"Q3687722"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"eee88c85a2449496f48eff43ddcfcd9152d9f633","datavalue":{"value":{"amount":"+0.9025388","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":"Q792091$1A152532-ACD5-4E2D-9535-13A3BD2409F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7905f401487041fc9d74e4666ff6de1507aad201","datavalue":{"value":{"entity-type":"item","numeric-id":1704113,"id":"Q1704113"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d7397bdd066cb77ac25ccd5d52152faf29073351","datavalue":{"value":{"amount":"+0.8945493","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":"Q792091$42CCA63E-8457-4D8B-9D9F-2B0D1C1556EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"94c96ba92e16a8b2f4c0f2933bdfa1743cd193c6","datavalue":{"value":{"entity-type":"item","numeric-id":3974870,"id":"Q3974870"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"db419f862344f0cea24d7578690fff75836b0efd","datavalue":{"value":{"amount":"+0.89428145","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":"Q792091$2E0B0DC9-5E76-4053-AA52-3A0008465AB1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5d818fabc759c090d5d834edc005fe2edbe66afc","datavalue":{"value":{"entity-type":"item","numeric-id":3677178,"id":"Q3677178"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7949b84eec5d54cfdd97c74ca46aafc16eb84b41","datavalue":{"value":{"amount":"+0.8905806","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":"Q792091$B49D9B3A-9BA8-4E79-85D1-B09CB6C2409E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:792091","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:792091"}}}}}