{"entities":{"Q1589415":{"pageid":1600155,"ns":120,"title":"Item:Q1589415","lastrevid":43228892,"modified":"2025-07-22T14:31:21Z","type":"item","id":"Q1589415","labels":{"en":{"language":"en","value":"Shuffle languages are in P"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1542256"}},"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":"Q1589415$8C298B62-C0AD-4860-9D18-1D2A0091663F","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b71265390f866939411b5fe052a05aab30e02e50","datavalue":{"value":{"text":"Shuffle languages are in P","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1589415$2837EBD8-DF15-40B3-A421-735A4FD79AFA","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"3065ab1bb4aaeeeca5517951ed94e5393ed6f53a","datavalue":{"value":"0952.68079","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1589415$690942F5-8C0A-4EB0-9E63-A2A1F1B12A30","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"e9a39a4b7072a2b0fbbf83e6a168cbb44fb3cca9","datavalue":{"value":"10.1016/S0304-3975(99)00109-7","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1589415$F44DB6F3-311E-4772-9BC9-741E2E0438E6","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":"Q1589415$41249F7D-649E-4567-A87D-4EECF5CB8014","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"1fc98fd02909f39fc4d6749553781a25cceed046","datavalue":{"value":{"time":"+2000-12-12T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1589415$663E72C4-91AB-4BE7-B248-8343B03F25B0","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"8eb290c1f3c9f65e13a817f051e26dac4580a015","datavalue":{"value":"In this paper we show that shuffle languages are contained in one-way-NSPACE\\((\\log n)\\) thus in P. We consider the class of shuffle languages which emerges from the class of finite languages through regular operations (union, concatenation, Kleene star) and shuffle operations (shuffle and shuffle closure). For every shuffle expression \\(E\\) we construct a shuffle automaton which accepts the language generated by \\(E\\) and we show that the automaton can be simulated by a one-way nondeterministic Turing machine in logarithmic space.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1589415$A66B9580-C8F3-4144-9C30-69A98584D733","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1589415$304EDE02-ED39-41DF-9AA8-E93E1937CAE1","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"ea091af9dfdfb095c0f73f1fe923fc795d986ed8","datavalue":{"value":"1542256","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1589415$B45E9141-4F4C-4375-A385-FBA51DB3E92C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c5f8382ba04f9f05f645b4d0e4b9ea28f0619583","datavalue":{"value":"complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1589415$6B570C8D-74A9-47DC-906F-2EF2F907D03D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d8be6c3794120e9ae59d4fa98167aec1929cd618","datavalue":{"value":"polynomial-time complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1589415$4C61B4E3-7CA0-41F0-BC6A-767CEC2093F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6498e5aada53d26324b926c7f994934ced3169b4","datavalue":{"value":"shuffle languages","type":"string"},"datatype":"string"},"type":"statement","id":"Q1589415$B3B3F43A-4CCB-4C36-9DC0-ECE2945C919D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7d1112fb5de40d368464718ab4150dd1951dd0b8","datavalue":{"value":"shuffle","type":"string"},"datatype":"string"},"type":"statement","id":"Q1589415$0150EB81-207A-42C9-9434-26FEEA811B44","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dae07fe120276ee4c21c2b056394433e1dd18622","datavalue":{"value":"automata","type":"string"},"datatype":"string"},"type":"statement","id":"Q1589415$77FDA5CE-CA9F-4CE6-9872-E991F5554ABF","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"e0527eb4d6b60ee1f8f564f0b5442173fb58d76e","datavalue":{"value":{"entity-type":"item","numeric-id":760798,"id":"Q760798"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1589415$AA54C686-29D9-441B-B252-EDA8F26A32B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ab04ccff5257bfd7d9df0e67238421f4fa3b71ef","datavalue":{"value":{"entity-type":"item","numeric-id":293472,"id":"Q293472"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1589415$9A799603-5F23-4A45-A17F-B49B43D8F848","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":"Q1589415$BBEC152E-07D4-4A12-8DCC-7E35AAF6F6B3","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"197d19b905774e3dc3f0785486379fd80c1c771e","datavalue":{"value":{"entity-type":"item","numeric-id":1184987,"id":"Q1184987"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1589415$727304D7-AC04-43A2-99B4-8147C1E43187","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":"Q1589415$BBC7BDAD-2C1A-4A29-BCBE-0868647F5955","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":"Q1589415$F7952D8C-3A26-40D4-AA79-A5C302FAAE95","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":"Q1589415$09590354-B6E3-4F9E-82DF-F068B82BF961","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":"Q1589415$86D7B215-7AD9-42CB-8FE8-86AABA22A03F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"277fb752c98d4990ab5de2c77c7db79f256f984a","datavalue":{"value":{"entity-type":"item","numeric-id":1096398,"id":"Q1096398"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1589415$0DDC2B5E-10F7-402D-9E4D-3D29570711C0","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":"Q1589415$E1AC21F5-804F-47A0-B45B-A37B97F2EB87","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"28a5734b3d72ae960c96d4305d986241d488b444","datavalue":{"value":"Q127186276","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1589415$3BCC878A-D451-4796-9F7F-BE4C0CE56754","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0e7370e4d0c833a3b1f911b5576b29412cb55096","datavalue":{"value":{"entity-type":"item","numeric-id":4884893,"id":"Q4884893"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"79fd68f8dda5cc16526a5392a7d2c5d013aff6f7","datavalue":{"value":{"amount":"+0.8949153","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":"Q1589415$4C33D7FA-CEF6-401A-8E36-E28EC852FCC7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"930d53c0ca1cbc1a0f4c50890f2a1f2a012c53a6","datavalue":{"value":{"entity-type":"item","numeric-id":1884959,"id":"Q1884959"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f3c4d0c92ef5a67647525aaeb35281291ce724b0","datavalue":{"value":{"amount":"+0.87844414","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":"Q1589415$8F686980-1992-4CD1-B3B5-3CDCD35D9AC0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b2541f9139cf45412c6be7a8f1e00da70931b453","datavalue":{"value":{"entity-type":"item","numeric-id":1592922,"id":"Q1592922"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"94061cd6b4acefe555305f57e9465e117fab93a6","datavalue":{"value":{"amount":"+0.8612751","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":"Q1589415$0DD23920-FA23-4FA2-A213-79F67F8A1AEE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d3fbe0e841fb349ed08e86d4e168ba0a81861867","datavalue":{"value":{"entity-type":"item","numeric-id":2928664,"id":"Q2928664"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5c25fe3bb5424e09c751d512d2578d54822e404d","datavalue":{"value":{"amount":"+0.8596411","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":"Q1589415$228D0E98-B88D-4BE6-A69A-848A67C20D12","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ecc20f35f086b5e84a475b65f37f34ea2de97509","datavalue":{"value":{"entity-type":"item","numeric-id":4327410,"id":"Q4327410"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d08b9bdce81be039919c859e9fd21b1981e3c5fb","datavalue":{"value":{"amount":"+0.85895354","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":"Q1589415$B652AF79-652A-41C5-BB06-A3311ABBAAE7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a98d3c1f88c173a577e0b4dd2fe512df1365f91e","datavalue":{"value":{"entity-type":"item","numeric-id":4421594,"id":"Q4421594"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1b65f8ecdd822b7a4a6932328cc8b53eaa848f3b","datavalue":{"value":{"amount":"+0.84707594","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":"Q1589415$3A817982-1BB1-4D39-A020-BD2F3B864E54","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"07524de2788c4dfd730315e298e6ec417b36ace6","datavalue":{"value":{"entity-type":"item","numeric-id":388107,"id":"Q388107"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a6a8b10e3f8f747c369c8e39a6a842dd6ebb30eb","datavalue":{"value":{"amount":"+0.8467254","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":"Q1589415$19AEB513-2FE8-424A-BB23-51C373B2C648","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5f870eaa7fd8e8fdd5868bfdeec9b09ac8869f80","datavalue":{"value":{"entity-type":"item","numeric-id":5411651,"id":"Q5411651"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"474f3248a2e2a6b61293c3e3c3d74ae2d144ac44","datavalue":{"value":{"amount":"+0.8466368","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":"Q1589415$65395DEC-DB07-4B02-8EB2-175818367187","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"58dae037116aace0e59176f933ba967ab02e91be","datavalue":{"value":{"entity-type":"item","numeric-id":3004574,"id":"Q3004574"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9073d401c139fb7aca746236f91fa22175c73409","datavalue":{"value":{"amount":"+0.8465504","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":"Q1589415$7EDE346B-BD9B-440A-9693-458F4B802E3A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fecd932d6b4ca0843d789f695afc2e930a443648","datavalue":{"value":{"entity-type":"item","numeric-id":3167517,"id":"Q3167517"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"da75d691b0a76e3ac329f7e794af88c4ae3eec7b","datavalue":{"value":{"amount":"+0.83973813","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":"Q1589415$DB48E636-084C-412D-BBBA-4C6E02CDFFC9","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1589415","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1589415"}}}}}