{"entities":{"Q800086":{"pageid":801934,"ns":120,"title":"Item:Q800086","lastrevid":55895308,"modified":"2026-02-20T22:28:16Z","type":"item","id":"Q800086","labels":{"en":{"language":"en","value":"On the complexity of iterated shuffle"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3876593"}},"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":"Q800086$6FFEE8AA-BCFD-4D9A-8EC9-EE58DA13BEF0","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"22def10735a1cc6bb316866cea2d396afb7334b6","datavalue":{"value":{"text":"On the complexity of iterated shuffle","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q800086$B2D605A8-2D57-4E86-8F43-C46500467E5B","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"2b76c2703da71ef2873eb586501e9bb7275a26d2","datavalue":{"value":"0549.68039","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q800086$3901A751-A628-47C1-AD88-1F6509A87F5B","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"4d53c29ec6302cbeeda4148afa5ca06742b6a052","datavalue":{"value":"10.1016/0022-0000(84)90018-7","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q800086$6ED137D0-8B31-4DB1-B67F-4C98AD3853F2","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"4d42337cf24b90f5ac095f15e64afb2b57c10dc7","datavalue":{"value":{"entity-type":"item","numeric-id":391735,"id":"Q391735"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q800086$E8DE585E-553A-45F8-8595-95F1E6DDFDDA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"bd2d3ae090b22c3a641be4fedb72aeccd09f0d74","datavalue":{"value":{"entity-type":"item","numeric-id":676241,"id":"Q676241"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q800086$235E27F3-6F4C-455C-948D-75673A2F8278","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"3340243f57e05f2265c56423c388055a14b114fa","datavalue":{"value":{"entity-type":"item","numeric-id":107189,"id":"Q107189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q800086$264BE7E3-25AB-4AD2-BC11-6F3708CC3C6C","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":"Q800086$16FD752E-538C-4FCA-B8A8-CA2B0238A517","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"cbeae4cec517a51389a4d4234181a753bc95b49b","datavalue":{"value":"It is demonstrated that the following problems are NP complete:    (1) Given words w and \\(w_ 1,w_ 2,...,w_ n,\\) is w in the shuffle of \\(w_ 1,w_ 2,...,w_ n?\\)    (2) Given words w and v, is w in the iterated shuffle of v?    From these results we show that the languages \\(\\{{\\$}wc\\!| w^ R:w\\in\\{a,b\\}^*\\}^{\\odot}, \\cup_{w\\in\\{a,b\\}^*}({\\$}w)^{\\odot}, \\{ab^ ncde^ nf:n\\geq 0\\}^{\\odot},\\) and \\(\\{a^{n+1}b^ nc^ nf^ n:n\\geq 0\\}^{\\odot}\\) are NP complete, where \\(\\odot\\) denotes the iterated shuffle. By representing these languages in various ways using the operations shuffle, iterated shuffle, union, concatenation, intersection, intersection with a regular set, non-erasing homomorphism and inverse homomorphism, results on the complexity of language classes generated using various subsets of these operations are obtained. Finally, it is shown that the iterated shuffle of a regular set can be recognized in deterministic polynomial time. Further results: We can show that \\(\\{ab^ nc)^ 2:n\\geq 0\\}^{\\odot}\\) and \\(\\{a(a^ nb^ n)^ 2:n\\geq 0\\}^{\\odot}\\) are NP-complete.","type":"string"},"datatype":"string"},"type":"statement","id":"Q800086$DD972A2C-9B77-478D-9646-B5E910AB26AE","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q800086$47E645AE-6EE7-403F-A843-6A1C7D6943C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q800086$BDCAD444-EE2F-41CE-B7E5-7AD858D6C2B7","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"4585d0cdafd7cd8865cf6c7038c5b94f09543e95","datavalue":{"value":"3876593","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q800086$6CAA5C1E-6EEF-4E39-87E4-6E6F6BE6BB10","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3d75dd85e29570a1648527b6f7876770b7e4b083","datavalue":{"value":"NP complete","type":"string"},"datatype":"string"},"type":"statement","id":"Q800086$E510794A-BBB9-459A-9DE8-E1C13A44CA53","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2977bda8220ccceab9112dd54c73384bf0be45e3","datavalue":{"value":"iterated shuffle","type":"string"},"datatype":"string"},"type":"statement","id":"Q800086$4ED3B6FC-21F7-4F80-A356-756C1CBD1B80","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e9410bc3e4aadf2e287381882fa40e23e2155747","datavalue":{"value":"complexity of language classes","type":"string"},"datatype":"string"},"type":"statement","id":"Q800086$4EA771A8-5402-4285-B761-4F3EDA8AF401","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f241144e7da92fd2b86dfe162d6dd27a44286bc2","datavalue":{"value":"regular set","type":"string"},"datatype":"string"},"type":"statement","id":"Q800086$FA7131C0-2A2A-4139-BDB4-1763AAA4ECFE","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":"Q800086$75237B62-FAAB-41C0-BEB8-EC2D4648C204","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"2a2f4349c2523eba95124ce8d8cf153d82b4878d","datavalue":{"value":"https://doi.org/10.1016/0022-0000(84)90018-7","type":"string"},"datatype":"url"},"type":"statement","id":"Q800086$CDD16C27-65DA-403A-8505-63D75F234ADC","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"bfd49aafd555bccb6a2682229579c139234f3767","datavalue":{"value":"W2036157680","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q800086$C6AFAD69-238A-4791-BE41-229963D600B6","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":"Q800086$FD015A92-687A-4E15-A9F1-CD3D77B005C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"be8a53fe134b0b70830e68dfe27608ac9174a22f","datavalue":{"value":{"entity-type":"item","numeric-id":4140712,"id":"Q4140712"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q800086$9909E8BB-92FA-4F0C-9E9D-BB073F74CC2C","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":"Q800086$155E626D-851E-4DDF-939F-B9CBB0F250BA","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":"Q800086$D8A77AEE-4039-425D-B223-227ED235CBD0","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":"Q800086$ED0F422F-3F91-48C9-A5AE-5A7EEC88FE4F","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":"Q800086$C5091A90-4002-4269-94F4-D70A68F56339","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":"Q800086$EEBACF9D-9D57-4BF5-812E-4421AFD75924","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":"Q800086$EBD1CA7E-B882-4A8E-8ED5-9219D3797218","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a6e931bdced27c838c40a822b6afd4c77181ea4b","datavalue":{"value":{"entity-type":"item","numeric-id":2119066,"id":"Q2119066"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ad2735e3499c07ea16f3123583af98160d84f542","datavalue":{"value":{"amount":"+0.90674067","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":"Q800086$E76333C1-A3B3-4A5E-AB5B-EADF5FFEB1AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e990b7d45ae5b53e2261d4fd822befab44f55fe4","datavalue":{"value":{"entity-type":"item","numeric-id":2870045,"id":"Q2870045"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4d2bff35ba6f062e266549f39f2f40a2eef5110f","datavalue":{"value":{"amount":"+0.88330156","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":"Q800086$FE941ECF-EC1F-4744-A2EA-98D6209B5DD0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e60e813f5c0926762f2b8308ed409c7e082e48b1","datavalue":{"value":{"entity-type":"item","numeric-id":5003075,"id":"Q5003075"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8e31d6e788211fbf7539cda28f3bf7b456cfeec8","datavalue":{"value":{"amount":"+0.87679434","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":"Q800086$016C9981-2D38-40B8-8BE2-FB8D909DA077","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5141287cbc650f4d7a863c3fb0d8b71860224ef7","datavalue":{"value":{"entity-type":"item","numeric-id":4783736,"id":"Q4783736"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0e7d91081869757db985ee75e1cc377da8c5ea29","datavalue":{"value":{"amount":"+0.8748009","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":"Q800086$A7D92CE8-E2F9-46DD-A29C-F1B239ABE275","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d78c0a9868e4aac46607651e4b3269b1b60b2cf0","datavalue":{"value":{"entity-type":"item","numeric-id":5418703,"id":"Q5418703"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bdaf5ba8b977df04cbd9348079e82d10e928e16d","datavalue":{"value":{"amount":"+0.8705814","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":"Q800086$1A9378E2-70E9-4DD4-B02B-D3A435B49661","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9e9fecc3439a819760fc174f9d65e1a519f6b813","datavalue":{"value":{"entity-type":"item","numeric-id":4625662,"id":"Q4625662"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"000019b4c5c665dd4749b1babeb34a2504279d99","datavalue":{"value":{"amount":"+0.8670887","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":"Q800086$D7766E0F-7B8C-4684-A905-B40E4A5A5612","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6dbb4431ac0c88c4d041f4dbda70b0418d29dfd9","datavalue":{"value":{"entity-type":"item","numeric-id":5756642,"id":"Q5756642"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c22ea74f0f208012f57e588425237ee5151bc801","datavalue":{"value":{"amount":"+0.8651245","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":"Q800086$A757715F-7425-40F4-A695-629B76AED88F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ab42d30a32ef0689a472acf4a11abfcb5e661aa3","datavalue":{"value":{"entity-type":"item","numeric-id":3225163,"id":"Q3225163"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c22ea74f0f208012f57e588425237ee5151bc801","datavalue":{"value":{"amount":"+0.8651245","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":"Q800086$890F07F1-A0B7-4910-87A0-DCFFF04C617B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:800086","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:800086"}}}}}