{"entities":{"Q2641104":{"pageid":2651847,"ns":120,"title":"Item:Q2641104","lastrevid":44542065,"modified":"2025-11-23T18:26:09Z","type":"item","id":"Q2641104","labels":{"en":{"language":"en","value":"Ranking and formal power series"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4189183"}},"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":"Q2641104$62272F91-19B3-4757-AF58-25D19F950CD0","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b5f493fff335243696916dc7a39b8d0eead75801","datavalue":{"value":{"text":"Ranking and formal power series","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2641104$C48EA1C9-A571-44F5-8B08-5971F4760AD8","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"55aee5f741c8dd68f5d8d170da7f2718102c0613","datavalue":{"value":"0721.68023","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2641104$849E9F5B-AFF0-4CD2-B5DD-CFAB787613F5","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"1af52b8cb07c6293487302f7fb8bd299bdc5bc69","datavalue":{"value":"10.1016/0304-3975(91)90144-Q","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2641104$F38276D8-47A4-4F3F-B1EA-DFDA361D2057","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"1787eb14bce43122c138b20ecca26156eee15dfe","datavalue":{"value":{"entity-type":"item","numeric-id":1199688,"id":"Q1199688"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2641104$4C43469E-AF67-4519-B993-A9019C0D0299","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"224a23009a193bc3927d2cbe6ef26b7ecad1c0b0","datavalue":{"value":{"entity-type":"item","numeric-id":288797,"id":"Q288797"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2641104$DED64624-5177-4BAD-B616-542C73963A88","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"8771b95719f75a612917e1582dccec9f6e42d828","datavalue":{"value":{"entity-type":"item","numeric-id":590572,"id":"Q590572"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2641104$D626C129-9D6F-40F0-BB6F-ED843762CF6B","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":"Q2641104$E5CCD142-64EF-4709-9803-634F3B033F92","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"391107ffc7a24346d69c573e292e4ff4587e3aaa","datavalue":{"value":{"time":"+1991-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":"Q2641104$6F97F7D2-01E3-4BFB-A177-FCDE6F8DB192","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"d144300e64635638c5c294f285a442ce3fcd1a62","datavalue":{"value":"The ranking problem for a language \\(L\\subseteq A^*\\) is the following: given w in L, compute the integer n such that w is the n-th element of L for the lexicographic order (u\\(\\leq v\\) if either \\(| u| <| v|\\) or \\(| u| =| v|\\) and u precedes v alphabetically). The value problem for noncommutative formal series \\(S\\epsilon {\\mathbb{N}}\\ll X\\gg\\) is the following: given w in \\(X^*\\), compute the coefficient of w in S.    The authors show that the ranking problem for an unambiguous context-free language is \\(NC^ 1\\)-reducible to the value problem for an algebraic formal series. An application to regular languages is given.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2641104$8B081DAE-EB37-418B-B14C-B32BF6764269","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"cdb5d51a2bda6cf4c2922285188fc67ca4b14abc","datavalue":{"value":{"entity-type":"item","numeric-id":213124,"id":"Q213124"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2641104$4265BBCE-09EB-462D-97B5-4933C40F828C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2641104$DD3C741F-0690-4A3B-8691-C3781F2F4B45","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2641104$8D4AA9B8-7EDD-4F34-ADC7-3D6B1E85CA8A","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"9cc70ec41c78991a0b111e041c0b6e67ba4b1d25","datavalue":{"value":"4189183","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2641104$BFA97D47-A303-44D6-9B6B-8C1AA84BF32A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a63f5fdf3038af45049408a9914d671beb783a5b","datavalue":{"value":"parallel complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q2641104$31EA1364-829C-43EE-A305-EE8DEDCC28F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a4df73210227f5dfce7acc604ba8e77684da5f9d","datavalue":{"value":"ranking","type":"string"},"datatype":"string"},"type":"statement","id":"Q2641104$37A6C3F4-7C68-46A2-B68D-4367878A6EB4","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":"Q2641104$A36B0D07-9E9F-4DBC-9567-D09CEF0EEDBF","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"33d0aad367cf52891c508c7e7bfb594600ba61f8","datavalue":{"value":{"entity-type":"item","numeric-id":3756526,"id":"Q3756526"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2641104$A941863B-C374-4A7E-9EC9-65B42A2A7078","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":"Q2641104$6433DB73-C8EF-4C4D-9185-660D7811AADC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3913a579b628d4f8deae9c770eb511538508ca80","datavalue":{"value":{"entity-type":"item","numeric-id":3994777,"id":"Q3994777"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2641104$97111A7B-F347-4689-A9AA-411A646252C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ffb3e46a0deb94f568837a5a711d518011b93539","datavalue":{"value":{"entity-type":"item","numeric-id":3773366,"id":"Q3773366"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2641104$7BDC7807-956E-47B2-8476-8E6AFDE8C8E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e5939d66e136ade0d6f2b74c689276f5852e88d6","datavalue":{"value":{"entity-type":"item","numeric-id":910245,"id":"Q910245"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2641104$B40D31E4-72BE-4DFA-9F71-0732E384ED0A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b90df03a170fcc85d9f6d5af38c0866a51f22b3f","datavalue":{"value":{"entity-type":"item","numeric-id":3694688,"id":"Q3694688"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2641104$5575AB0C-96BA-4942-A3F2-F8842741EB5E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2c0d1fb4e177bc1d0a6797a5e32e81051d24fed3","datavalue":{"value":{"entity-type":"item","numeric-id":3750999,"id":"Q3750999"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2641104$A229FDBD-7EBD-48E0-A713-6FE6FD687B9B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9920c3ac00d626f59f95283223bd4fb6ae680345","datavalue":{"value":{"entity-type":"item","numeric-id":1152951,"id":"Q1152951"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2641104$B0FC3013-2D5B-4BC8-8865-2954B4C05E3C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8eb6290412741acf231ec58be371ffd9c5ecc534","datavalue":{"value":{"entity-type":"item","numeric-id":4155837,"id":"Q4155837"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2641104$CC528A7D-D228-471A-87B7-8FDB9B5CF5C4","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7bd08d1b914657878e042f7f2a51e556a07abbde","datavalue":{"value":{"entity-type":"item","numeric-id":792763,"id":"Q792763"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e526db3d980170f56db5554e6c7a78b2b3b55dfc","datavalue":{"value":{"amount":"+0.9131628","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2641104$10E95D64-7480-4296-A539-A3379FA9D91C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fb17600a1b498b50a1708f98564253b35515fa3f","datavalue":{"value":{"entity-type":"item","numeric-id":5916404,"id":"Q5916404"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bc7e20e7e6643ff3320092b1aebcda768cbb032a","datavalue":{"value":{"amount":"+0.88443273","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2641104$A4F0715D-669E-4BBA-8FD8-165A8A21DC0D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a5671243317e777747809e8503a0482cbbd77fee","datavalue":{"value":{"entity-type":"item","numeric-id":5891671,"id":"Q5891671"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b7a7ebe3c665f2aeda47db525cd8953719efd9e1","datavalue":{"value":{"amount":"+0.8844327","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2641104$9E9682B0-9AD2-4846-ADB2-4515A0DF11AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f744c0001752dd9b4405894b100fb3de1ae582ce","datavalue":{"value":{"entity-type":"item","numeric-id":2400652,"id":"Q2400652"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"224b952bf3eb65d81d7443dd66618f2309c97d43","datavalue":{"value":{"amount":"+0.8803369","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2641104$A75F6098-9690-4AF5-8601-E153DA6122A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5f7856f954fc63822a0004a598a1272e6c6558d0","datavalue":{"value":{"entity-type":"item","numeric-id":5962482,"id":"Q5962482"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"397c3c7085d9e2bc7da9cef2883c264fd1a486fa","datavalue":{"value":{"amount":"+0.8677762","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2641104$6AD0A41D-4587-4741-8750-BD1860C44FB3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"771a23f29b08117aeba8929f06a1b4ffe9e51575","datavalue":{"value":{"entity-type":"item","numeric-id":1608229,"id":"Q1608229"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c046308c211de5eaddc1b5fd0de28855de811457","datavalue":{"value":{"amount":"+0.8653138","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2641104$5215280A-9165-4FFE-8FB5-1F234E7A1400","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0f0716ee84e66d7541fc834c77d5f446b9f994ab","datavalue":{"value":{"entity-type":"item","numeric-id":3774014,"id":"Q3774014"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1fb05e7a40724e5d88802c2f1d7eef0c41b48b92","datavalue":{"value":{"amount":"+0.8626671","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2641104$E58292DD-F679-46B6-A6A9-35393ACEB650","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ce2b58b19d4a2896e9c143a9c4a063c670b1a5cf","datavalue":{"value":{"entity-type":"item","numeric-id":923631,"id":"Q923631"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"20a0130cf311e6a35e9bf6e5ca4fab7e164451aa","datavalue":{"value":{"amount":"+0.8603264","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2641104$0CC08953-F81D-48F4-B65E-BABDD242F0ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bb4fdcec2fcf034f991731e1bc907a5162cfde50","datavalue":{"value":{"entity-type":"item","numeric-id":1770223,"id":"Q1770223"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b799c906f28bbc44d8116aa3e614756175068309","datavalue":{"value":{"amount":"+0.85725486","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2641104$C5857E0A-6A99-40A7-AF14-DC6673A7CC72","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"37baabf661f91442ed0306bd81d1d33ad5ee8a3d","datavalue":{"value":{"entity-type":"item","numeric-id":1388989,"id":"Q1388989"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"47dbca7c92894e4c7a7a7af7717f88beac8db504","datavalue":{"value":{"amount":"+0.8555438","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2641104$E362234A-D54F-42F0-8371-841CC09DD2A3","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2641104","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2641104"}}}}}