{"entities":{"Q1063422":{"pageid":1074174,"ns":120,"title":"Item:Q1063422","lastrevid":67026345,"modified":"2026-04-12T14:24:50Z","type":"item","id":"Q1063422","labels":{"en":{"language":"en","value":"Extending regular expressions with iterated shuffle"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3917740"}},"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":"Q1063422$0334C257-6FA9-4220-B175-BF239AC96CAC","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"35449f147d99bbca322a16a879f1ab968f3d92ee","datavalue":{"value":{"text":"Extending regular expressions with iterated shuffle","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1063422$3F93064C-44D8-4C45-9063-DF5E54989FF4","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"b1e3a473f8c9759e8ff9d35701150d53af0e000b","datavalue":{"value":"0574.68069","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1063422$BD817800-F6E8-466A-A250-FFBEF70EE7D8","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"399403249d49612eb2ad456bd33ea73df28d1703","datavalue":{"value":"10.1016/0304-3975(85)90221-X","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1063422$255F13B9-35BB-4A10-A236-4B7673BD7541","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"2b7c4206a91812d650d472fa3b3ce96a70a084da","datavalue":{"value":{"entity-type":"item","numeric-id":795512,"id":"Q795512"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1063422$22A87817-6545-4197-99BC-A4C429CF31A7","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":"Q1063422$0A568781-3EB3-496F-8AD9-E609259A6376","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":"Q1063422$DE97D8FC-4DC2-49B4-8E9A-CC6C4DEAC578","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e1b3f4e81a673626322dc6c47804e595a18d393f","datavalue":{"value":"By using the result operations (union, product, and star), the shuffle operation {Russian{Sh}}, and its closure, the iterated shuffle \\(\\dag\\), the three slip-families \\(Shuf:=(v,\\text{Russian{Sh}},\\dag)(Fin)\\), \\(ER:=(v,\\cdot,*,\\dag)(Fin)\\) and \\(SE:=(v,\\cdot,*,\\text{Russian{Sh}},\\dag)(Fin)\\) are studied. While there exists a simple one-counter language L, whose iterated shuffle \\(L^{\\dag}\\) is an NP-complete set [\\textit{M. K. Warmuth} and \\textit{D. Haussler}, J. Comput. Syst. Sci. 28, 345-358 (1984; Zbl 0549.68039)], it is here shown that the family ER defines only sets that are acceptable by some multicounter language in quasi-realtime, thus are acceptable in nondeterministic logarithmic space and consequently are in P. The result obtained corrects Corollary 3.11 in the author's paper in Theor. Comput. Sci. 14, 127-154 (1981; Zbl 0477.68034), generalizes Theorem 5.1 in the paper of Warmuth and Haussler (loc. cit.), and adds to the research by Shaw, Riddle, Kimura, Araki and Tokura, Slutzki, and others.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1063422$C812D219-BA15-4904-BE35-98E9DA26C04D","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1063422$50CF7CDD-8803-49D6-A766-25191DA93C38","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b8f412c62952107f7ff74e77578c2ab25d3e121a","datavalue":{"value":"68Q85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1063422$FF40E6D1-9633-4A77-AEAF-60070448AEBC","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"46b12223574f16bcc584000674c92c9ae4595a3d","datavalue":{"value":"3917740","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1063422$3CD4439E-5791-4FD8-AB21-23505CCCE3F7","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2f7dbb083469517deae9a0197b0e3e5229ddf4b5","datavalue":{"value":"shuffle expressions","type":"string"},"datatype":"string"},"type":"statement","id":"Q1063422$48EFCFE6-9A3F-4DDA-85A9-FCDB0369ACD9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0c3ceff1405cd910bb3fd7785fbb02ee3886bee1","datavalue":{"value":"Petri net languages","type":"string"},"datatype":"string"},"type":"statement","id":"Q1063422$B8F9EC54-7A4B-4830-936F-7E4CD4B3225B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"203e5a911788125c8ba7bcf8b0df6a8b4e2efe1b","datavalue":{"value":"multicounter language","type":"string"},"datatype":"string"},"type":"statement","id":"Q1063422$4325C13E-D0CD-4B27-82CC-69622895A97A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e60aff191d07317ce19ff0b7849d11fe5f27bc8c","datavalue":{"value":"quasi- realtime","type":"string"},"datatype":"string"},"type":"statement","id":"Q1063422$0E7481C3-A1C7-4A5C-9EC3-C9866767087C","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":"Q1063422$346E2DCC-8A4C-4FC7-B562-F658D9B94863","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"9e70f1dff538fdca6e324d47dad314fe3617ffdf","datavalue":{"value":{"entity-type":"item","numeric-id":1158771,"id":"Q1158771"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1063422$94AC6298-2A20-4108-B9B4-504C0C8CE5DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4a0382e0bd1e410eca3d97bd76be70e4bf8af669","datavalue":{"value":{"entity-type":"item","numeric-id":1151054,"id":"Q1151054"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1063422$A5D33120-DFD1-4089-B6C5-4C6914D9970F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3632afaf7c9124694de853efafd5cd84e2a50881","datavalue":{"value":{"entity-type":"item","numeric-id":3859267,"id":"Q3859267"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1063422$78F20735-5986-4899-BF2E-6248D876C11E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ae6dbdfb8e4006fb3dd873470728fc9496f82f28","datavalue":{"value":{"entity-type":"item","numeric-id":1143803,"id":"Q1143803"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1063422$11723ADE-3060-429E-ADE3-E0698DCEF5FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"243a974194fa34fd25722575e1666811518331c8","datavalue":{"value":{"entity-type":"item","numeric-id":2542523,"id":"Q2542523"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1063422$D1FF7C58-ABD3-4B37-AA75-997DBAF7C663","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":"Q1063422$0478ECEE-9237-4768-8555-E5F840B71FE6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4b6a23a1c0d74876b60ffc488928469cc10439c2","datavalue":{"value":{"entity-type":"item","numeric-id":3926067,"id":"Q3926067"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1063422$8014CC78-BD0D-4C34-A7B5-76B485C4610F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c275f00bd2b1625717370185ca0dbd8464de5303","datavalue":{"value":{"entity-type":"item","numeric-id":1251070,"id":"Q1251070"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1063422$2CACA7AF-385D-432F-AFDD-B1F5ECBA5B47","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2cec41b663dc2993dc92ada7db9014e2dab75761","datavalue":{"value":{"entity-type":"item","numeric-id":3907111,"id":"Q3907111"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1063422$2EC25426-8BEB-435A-B9D9-E93B127CFAB4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e41085ab187796e90a7b396d19c84db2e1c4a21e","datavalue":{"value":{"entity-type":"item","numeric-id":4190159,"id":"Q4190159"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1063422$34D3A236-E6DD-4613-B26C-BCDC2D935B3C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5ba9718692541d09b1cb683eab4cf3178d98ddbf","datavalue":{"value":{"entity-type":"item","numeric-id":4198084,"id":"Q4198084"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1063422$FB4D050A-E263-4362-A1E3-D6B64F1FF1E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f256b121b5960183092d61923f4090ee7435150d","datavalue":{"value":{"entity-type":"item","numeric-id":1161057,"id":"Q1161057"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1063422$610694C3-8C35-437E-A3AC-FC08F6C103F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c5c5f61c7ca00d5272c042ee2a7885acd7803494","datavalue":{"value":{"entity-type":"item","numeric-id":1063422,"id":"Q1063422"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1063422$974A4EA0-6FFC-4D6F-A91C-C83FEA066B81","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dd15a6dc8ba82abdfc9beba774819ed68b520dfb","datavalue":{"value":{"entity-type":"item","numeric-id":760799,"id":"Q760799"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1063422$6E11FCD1-82D5-4EED-8A7B-A2FE4D0F902A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"657452dbab5687b4165773cff8849d89f34ed4bf","datavalue":{"value":{"entity-type":"item","numeric-id":4140399,"id":"Q4140399"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1063422$9B549159-C56E-4568-93E5-E9A0E3BF285C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c3eb0472ff2f6627a314bfe79b0ee69d75c93f98","datavalue":{"value":{"entity-type":"item","numeric-id":4195931,"id":"Q4195931"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1063422$2D3B8618-6AC6-41D3-AE5C-05812E202B6A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d3e79c1198a5adad0b28f20fcd66d4c98012ceb6","datavalue":{"value":{"entity-type":"item","numeric-id":4162475,"id":"Q4162475"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1063422$05B0F52F-BADF-435F-92FA-D8AC31E93F85","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d84c3283cfca05145bf5644b397ac5451fbc2129","datavalue":{"value":{"entity-type":"item","numeric-id":3883468,"id":"Q3883468"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1063422$02D25808-02DB-464A-9F26-54F0ABF8C7CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6a200920fb3c87ae0a99bb88fd138bf2ad3736fa","datavalue":{"value":{"entity-type":"item","numeric-id":800086,"id":"Q800086"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1063422$74EF52C1-372C-46A7-A509-B1426A53E80E","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"20af56a0548e09403dc352265eb9ef0449eadcd9","datavalue":{"value":{"entity-type":"item","numeric-id":800086,"id":"Q800086"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ed748156f8b8b75caf7d211c143d82e057117cfd","datavalue":{"value":{"amount":"+0.8352176547050476","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":"Q1063422$D6679408-9179-499F-BED4-4399F1253FA6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b92eee32c05f840dfbb7c7ea0b88efd17e83f09a","datavalue":{"value":{"entity-type":"item","numeric-id":3499370,"id":"Q3499370"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1970819db4922b7a97b3ab4aa567fe5bd8081851","datavalue":{"value":{"amount":"+0.8208649158477783","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":"Q1063422$ADEF753E-529C-425B-B519-DA6D31834921","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"479bc4c06f3ba5309cc51fa5a0b9a324673239a9","datavalue":{"value":{"entity-type":"item","numeric-id":4331053,"id":"Q4331053"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b620b87c19566f4a9e67f96f3a558ef86ec8c67f","datavalue":{"value":{"amount":"+0.7706760168075562","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":"Q1063422$C5F6D31E-D54D-4115-90EB-B691C0A38277","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6035a36bcdd297f29ff69dfdb523a0fd9d129705","datavalue":{"value":{"entity-type":"item","numeric-id":1589415,"id":"Q1589415"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0794dec1c4c5221ea4d9fb7d45e7a64110b43c39","datavalue":{"value":{"amount":"+0.7512361407279968","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":"Q1063422$BF5FD71C-26DF-4855-94C0-D2555036D53A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"189421969ad941d4e0042e21d26e6e7f14e3d4fb","datavalue":{"value":{"entity-type":"item","numeric-id":760799,"id":"Q760799"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c92d3da1aeecab1e46599387d88fee526497d12e","datavalue":{"value":{"amount":"+0.745999276638031","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":"Q1063422$D51A83CE-B3E0-45E9-8CBF-473955F4E762","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Extending regular expressions with iterated shuffle","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Extending_regular_expressions_with_iterated_shuffle"}}}}}