{"entities":{"Q1183569":{"pageid":1194318,"ns":120,"title":"Item:Q1183569","lastrevid":70204779,"modified":"2026-04-13T13:09:08Z","type":"item","id":"Q1183569","labels":{"en":{"language":"en","value":"Parallel parsing on a one-way linear array of finite-state machines"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 33389"}},"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":"Q1183569$3D0B6EB5-64AD-488D-A6CF-6F1CD8C53A27","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"3425675eb576002fc66c67363e4a6ad59da2a2db","datavalue":{"value":{"text":"Parallel parsing on a one-way linear array of finite-state machines","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1183569$B404339C-9807-48C3-BBA8-568FB001E54B","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"51ec128350d9b4c03247e580e7b57586c85e0bd1","datavalue":{"value":"0756.68072","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1183569$CBCB8406-59C2-4DA3-9C11-69ED7D1CDD9A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"7a063034a9775e8bdddd91236996f5ce05265a8e","datavalue":{"value":"10.1016/0304-3975(91)90047-6","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1183569$1EDC3EFF-4E01-4844-8DD1-C3F106353288","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":"Q1183569$85E0B24B-F399-43AF-8190-EC08A0C39FF8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"0ff69d199b2e4b3f62f192bd9e307ef835b69b5a","datavalue":{"value":{"entity-type":"item","numeric-id":185445,"id":"Q185445"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183569$8E38B835-8B82-48B3-8B12-42DCC73F3217","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"0e94e7885da0e46c34212704ee64348b3d7896b7","datavalue":{"value":{"entity-type":"item","numeric-id":1183568,"id":"Q1183568"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183569$4D218410-0FD3-4EDA-8D78-53E7833322F9","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":"Q1183569$1B7DD654-7ADD-4F66-BBBD-CE1EB8A0F705","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"120787504bea9565def539fb4bfb19084956028b","datavalue":{"value":{"time":"+1992-06-28T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1183569$F3DDD120-64E1-47B7-A401-61396C8E7CEA","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"9f50cf5653786421df0d615ce95241a078fb513b","datavalue":{"value":"An one-way linear iterative array (OLIA) for inputs of length \\(n\\) consists of \\(n\\) finite state machines which operate synchronously and which communicate linearly: the state and the output of a machine (excepting the leftmost) at time \\(t\\) depends on its state and the state of its left neighbor at time \\(t-1\\). The inputs and the outputs of an OLIA are serial. The paper shows that the following three problems can be solved in linear time on an OLIA:   --- parsing of discrete two-tape nondeterministic finite state transductions,   --- parsing of linear context-free languages (as a consequence of the former),   --- parsing of languages accepted by nondeterministic one-counter automata.   We remark the way chosen for the presentation: firstly, it is shown how an OLIA can be simulated efficiently by sequential machine and then all algorithms are presented in terms of sequential machines. This gives clearness and legibility to the text.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1183569$B69AC3E2-CA59-474F-AECF-D2F99E27D6C5","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3affb2aa66be15f2a63c60d2aaa92bd143e6d46","datavalue":{"value":"68N20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1183569$EC011A98-E5F3-4D04-926C-CBCD3A92A289","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b65efe51b183d0f4a672427b8171cd1e14211cba","datavalue":{"value":"68W15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1183569$79709377-3D15-4EEC-983D-7E8792482C23","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1183569$1014C37F-AEE9-44A8-911F-0D864F0E7E6D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"e5faa7c3c1e44feacc0945b0ff8472071e9daf36","datavalue":{"value":"33389","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1183569$F4E7B8EA-33F7-4373-86EB-8C0B5AF93D1F","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"94eb7614cb6710a82a20349a24001c13c5239b72","datavalue":{"value":"parallel parsing","type":"string"},"datatype":"string"},"type":"statement","id":"Q1183569$D360BE4D-C9BF-4F06-BFE8-24F2582C8406","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5e25eeaffa867b826fa9b646fdfb93f199f0c30b","datavalue":{"value":"one-way linear array of finite-state machines","type":"string"},"datatype":"string"},"type":"statement","id":"Q1183569$E3FC6F47-5C1F-445C-8133-80DB8D452B72","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"68f90e9e5aa6bdf60696b11b3a76d38c876da93c","datavalue":{"value":"transductions","type":"string"},"datatype":"string"},"type":"statement","id":"Q1183569$E544437B-B413-4196-A6B0-B93FAE412307","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"795414f846fccd6517b35b46d219d01dfd08d3da","datavalue":{"value":"context-free languages","type":"string"},"datatype":"string"},"type":"statement","id":"Q1183569$ED4067BF-6BA5-428E-8928-F8EAD5F7C630","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"e5adb2f5b9beef2201bef72e73c6f511c159db61","datavalue":{"value":{"entity-type":"item","numeric-id":493519,"id":"Q493519"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183569$19BCDF1E-DFD2-4965-98E4-66F92F92B580","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":"Q1183569$B6649AD2-B716-4026-9F5F-7681CDBD0557","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"d50c40fd365b1d6421f46534393bb6458dd301ef","datavalue":{"value":"https://doi.org/10.1016/0304-3975(91)90047-6","type":"string"},"datatype":"url"},"type":"statement","id":"Q1183569$F20855E5-4BE8-43E4-A227-1F23FB220CFF","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"c871909fe5ca050b667b85ef5b79dbefdbfbd76b","datavalue":{"value":"W2020361970","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1183569$780C4076-449A-42D7-B12B-2CA62406E810","rank":"normal"}],"P223":[{"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":"Q1183569$C55A5C5D-98E5-4D8F-9F6D-5A0C0FDE9981","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"64c16e7ed2c27d095a1701542bc50868e83d3461","datavalue":{"value":{"entity-type":"item","numeric-id":1393121,"id":"Q1393121"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183569$D83A89B6-87B5-4ED7-8E29-3647A0845842","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"696366a94654a5d30f96d57b0e6b7e9de909ff30","datavalue":{"value":{"entity-type":"item","numeric-id":4055176,"id":"Q4055176"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183569$0DD44F3F-C15A-4F0B-9061-AEF589211905","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"34d399c657348baa004087caf4bfb28e90f3df58","datavalue":{"value":{"entity-type":"item","numeric-id":792091,"id":"Q792091"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183569$3F4828F0-0EB0-4F40-92C4-23C9BA85E362","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"588bfa165f8d410c142eaa54d718a985b23ad2f7","datavalue":{"value":{"entity-type":"item","numeric-id":1066679,"id":"Q1066679"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183569$D87BD17E-E4B3-4B0C-AF65-CF6296E9AC63","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1e2fab5f38bd4e0e7f1b7e0daec7405d5466dcdd","datavalue":{"value":{"entity-type":"item","numeric-id":1163370,"id":"Q1163370"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183569$40447BBC-4992-4A87-AA1D-0FADB501DE74","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"79e03cd8581db3f1a993a90df4b9b3924df0ec8d","datavalue":{"value":{"entity-type":"item","numeric-id":5528645,"id":"Q5528645"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183569$A5976834-E9E9-4186-8938-C77F8969539C","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"25c4581ad01a6008a12d2534cc1ea676e0e8c2e7","datavalue":{"value":{"entity-type":"item","numeric-id":3355242,"id":"Q3355242"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1a5332ac91c23c56d21c051d61db3870da8d032f","datavalue":{"value":{"amount":"+0.9158784747123718","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":"Q1183569$E3516A3F-FBA4-4303-BEAD-6AD7B43C043F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4e570a0609ba590cdb49ceb14506077ad9acbeaf","datavalue":{"value":{"entity-type":"item","numeric-id":3773378,"id":"Q3773378"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"744f1ea243de7982166eea165029e72a056d1d2a","datavalue":{"value":{"amount":"+0.8659214973449707","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":"Q1183569$097E2451-DFA4-4EB5-8FA1-A3AFB7B16954","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7f0ffbb24c69bda5fce30c411a3d5eb5c1c67613","datavalue":{"value":{"entity-type":"item","numeric-id":3327740,"id":"Q3327740"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d13af018dadc206516178cb0d2298e3396790c8d","datavalue":{"value":{"amount":"+0.791577160358429","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":"Q1183569$9CAA09D5-7065-4FDE-9821-7F98CE804B98","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b949abe6ee00661bfe19fb9451f39454e8988eb1","datavalue":{"value":{"entity-type":"item","numeric-id":3790658,"id":"Q3790658"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"458953d7e908d627846b878318d22c17c422af53","datavalue":{"value":{"amount":"+0.7883568406105042","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":"Q1183569$730A8720-7DDA-493A-B81D-B09A56E47925","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"255978fbbd69ed579b0395334adef749fd4af15e","datavalue":{"value":{"entity-type":"item","numeric-id":1121034,"id":"Q1121034"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5780accd05f2b0d080eb8c2350b8e7687cbb25f6","datavalue":{"value":{"amount":"+0.7862032055854797","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":"Q1183569$219A6008-7C31-43F9-A193-14D36ABD95A0","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Parallel parsing on a one-way linear array of finite-state machines","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Parallel_parsing_on_a_one-way_linear_array_of_finite-state_machines"}}}}}