{"entities":{"Q1124356":{"pageid":1135105,"ns":120,"title":"Item:Q1124356","lastrevid":69842007,"modified":"2026-04-13T10:42:44Z","type":"item","id":"Q1124356","labels":{"en":{"language":"en","value":"Prefix and equality languages of rational functions are co-context-free"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4112039"}},"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":"Q1124356$832CA93A-F057-4F7B-9943-AB6DC47951A4","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"20976348bc29c5a2d810b2f033be58ef6a45dc53","datavalue":{"value":{"text":"Prefix and equality languages of rational functions are co-context-free","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1124356$E700AF5F-2E19-4339-8C0A-ECD0587D1ED4","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"a3d09b88e8b76dc79e6fbae8a30753e736b78860","datavalue":{"value":"0678.68066","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1124356$C924DE64-8B0C-4129-90FD-21921458225A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"2b1d9349cb992a0cf28b1138528582e7467db4d5","datavalue":{"value":"10.1016/0020-0190(88)90167-6","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1124356$085D42AC-8AB8-4A38-95D6-23F02813993A","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"fdaa763056574d670db49d3b9b4fb6f07d823420","datavalue":{"value":{"entity-type":"item","numeric-id":255286,"id":"Q255286"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1124356$239F0804-DF80-4E8D-A05F-8E586B30BF7C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"0d3b51f718829bdc40d57f1305c80d06e624ee4b","datavalue":{"value":{"entity-type":"item","numeric-id":396843,"id":"Q396843"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1124356$E687D89F-7D5B-4925-B49C-D703BA5F0A5A","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"52fa7d44b58d0511cb8993765bd916aef86052d8","datavalue":{"value":{"entity-type":"item","numeric-id":63092,"id":"Q63092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1124356$DEB027F7-0F32-4E62-9858-388A1A9888E8","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"31a1937240ca4a323604b4728c31d242b5596d7c","datavalue":{"value":{"time":"+1988-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":"Q1124356$63DC91CB-62E3-46CA-A532-E4F02ABA1524","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"3c40d0cf04ef193653e9d4073c95e6e6faac9929","datavalue":{"value":"The authors show that for every two rational (partial) functions F and G, the complement of their prefix language Pref(F,G) \\(=\\) \\(\\{\\) w \\(\\in\\) Dom(F) \\(\\cap\\) Dom(G)\\(| F(w)\\leq\\) G(w) \\(\\vee\\) G(w) \\(\\leq\\) F(w)\\(\\}\\) is a one- counter language. In the above, ``\\(\\leq ''\\) is the usual prefix order relation on strings and the concepts of the rational function and one- counter language are in the sense of \\textit{J. Berstel} [Transductions and Context-Free Languages (Stuttgart, 1979; Zbl 0424.68040)]. Some consequences concerning equality languages, fixed-point languages and recursively enumerable languages are easily deduced. The general method of proof is not entirely new [see, e.g., \\textit{J. Berstel}; Inf. Process. Lett 22, 7-9 (1986; Zbl 0584.68082)].","type":"string"},"datatype":"string"},"type":"statement","id":"Q1124356$CCD9A063-B8B4-48AA-8638-901CBAC623A3","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1124356$1CEF5D3D-B1CC-4FE9-8298-16EE23AFE888","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"1f346fe9ca4d89da08932a8afb4e36cf1b307e33","datavalue":{"value":"4112039","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1124356$85C05E64-C29E-4B53-8C61-967CDC873CDB","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ba52aa75d4877d3488fc0127d7e1466db12a9070","datavalue":{"value":"prefix language","type":"string"},"datatype":"string"},"type":"statement","id":"Q1124356$CF8F4179-ECF9-43A9-9E8E-3876DA6533DA","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":"Q1124356$612B3A72-B039-45FE-962E-B2B8596245AA","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"605b4f2fc66559a3ccde56c2414e6852c3d2a539","datavalue":{"value":"https://doi.org/10.1016/0020-0190(88)90167-6","type":"string"},"datatype":"url"},"type":"statement","id":"Q1124356$F9E62E69-A3CB-42BC-886A-699EDC1B6272","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"22e910938c40408c58b3d25a26b1c10dd2791df1","datavalue":{"value":"W1966523679","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1124356$DEC3ED85-6501-4ACC-B80B-94976EEA1AC2","rank":"normal"}],"P223":[{"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":"Q1124356$56D56725-939E-4F50-98F4-DD2EE270FAD6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8ae4e9b1f14e220740fd08a99e4c277b28a9993b","datavalue":{"value":{"entity-type":"item","numeric-id":1069710,"id":"Q1069710"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1124356$E805D3B5-79DD-43A3-B8C0-7C29A9BC1EB1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ca9c4d0378db61d4529bee932fdb85a442f47565","datavalue":{"value":{"entity-type":"item","numeric-id":3856116,"id":"Q3856116"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1124356$C41EFFB0-8EAF-44B0-BCDC-7AF9C5DB6548","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ad14a7dd4f445a4e52bb9ac7dce1af5f5adb91c7","datavalue":{"value":{"entity-type":"item","numeric-id":3930659,"id":"Q3930659"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1124356$A50B6BBD-3CC3-4403-8034-3A9F7B91699F","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":"Q1124356$AD2C88AD-FC1C-4BEC-A039-5A5FBB9FD6D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"522b2a12012b04970578e80003874032a766bbde","datavalue":{"value":{"entity-type":"item","numeric-id":3680282,"id":"Q3680282"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1124356$E4FC70E8-B75B-4928-8CEE-EECB79F69121","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c67e7310d71a3ff5db7aa06fe30017f241c342d5","datavalue":{"value":{"entity-type":"item","numeric-id":3968472,"id":"Q3968472"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1124356$AEF26360-EA83-4E0D-8D69-4F22E30308C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9164970ac8079b23f3401b96cb337e6626e45eb2","datavalue":{"value":{"entity-type":"item","numeric-id":2540268,"id":"Q2540268"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1124356$6903068E-73A5-4921-B603-9D3AA79F0A3F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"63f6e93c6ebff3e0f9f24e9852a8d52922c49014","datavalue":{"value":{"entity-type":"item","numeric-id":3769982,"id":"Q3769982"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1124356$CD061DA8-E192-40C2-9F71-3F0EDE4C398C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c9d8f6bcc2e50d3a2dcdf05730f1c128a959f919","datavalue":{"value":{"entity-type":"item","numeric-id":761044,"id":"Q761044"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1124356$8CD3E47B-73A2-4057-9F95-F7E754E9513F","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fdb8dffc9b44d3c5d3fa6c71cefa0e3a10be205c","datavalue":{"value":{"entity-type":"item","numeric-id":5485977,"id":"Q5485977"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e2cfb80ac44e1641862ba4a650ffbc788f3de21e","datavalue":{"value":{"amount":"+0.8639244","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":"Q1124356$7F86D894-4EAD-4EE9-B524-DA3B272F56FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"93bd8b612ebdb04a3ac415158c65350f2dd9cdec","datavalue":{"value":{"entity-type":"item","numeric-id":4502584,"id":"Q4502584"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"244ba92a8dfa5b38a7996f5d47764572b4acf2d2","datavalue":{"value":{"amount":"+0.84975505","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":"Q1124356$10A02A82-09B8-44B1-9141-C012F6380649","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"401c760709c092fd929be64eba04237a6309305b","datavalue":{"value":{"entity-type":"item","numeric-id":1041740,"id":"Q1041740"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d3a6b07ddf0aedd569346a9eb2e6678f8fc23d1d","datavalue":{"value":{"amount":"+0.8486247","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":"Q1124356$B3EB65F9-7735-4900-B6A2-4775A6B60C2E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1305684ea96beb1fbd5b31814dce73878421f9dc","datavalue":{"value":{"entity-type":"item","numeric-id":4589610,"id":"Q4589610"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"14e3c7adb7976c587d988e93abe16fb5c5d15e82","datavalue":{"value":{"amount":"+0.84480464","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":"Q1124356$3051EF72-E824-4314-B795-21AAF86E5CE4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2e9fd0b05fad1052ec04963740bab4d772b185a4","datavalue":{"value":{"entity-type":"item","numeric-id":4992897,"id":"Q4992897"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"14e3c7adb7976c587d988e93abe16fb5c5d15e82","datavalue":{"value":{"amount":"+0.84480464","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":"Q1124356$AD46F34D-308D-4019-92F0-DACF08C8DA1E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b7b58e07f91fc97e5da153dcaea55db21cd96cce","datavalue":{"value":{"entity-type":"item","numeric-id":1622958,"id":"Q1622958"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7363991d130fc8a8ea7ad95c69b96b2dc7d00e79","datavalue":{"value":{"amount":"+0.8436984","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":"Q1124356$0611D525-9616-44CD-9CFD-269E24D3341F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3dc523f13d30ce43f9d0524fbc24d6589218739e","datavalue":{"value":{"entity-type":"item","numeric-id":1110344,"id":"Q1110344"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9af601ee7893ab21123f47f3e7e480f94f0b0007","datavalue":{"value":{"amount":"+0.843256","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":"Q1124356$258BA765-9FF7-4EAF-B5D8-C2AE6018A7FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"59113fcbed1a11b4e3c784c1f076a74cc0ed73aa","datavalue":{"value":{"entity-type":"item","numeric-id":1066675,"id":"Q1066675"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"19d2c61c22285dcb6d2cd4c98703c5e5df01d61a","datavalue":{"value":{"amount":"+0.8413128","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":"Q1124356$008B56D1-2364-4811-8B78-0260A47D0BA9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b0868a39b9aa458fc14066835fb5eb7df9045682","datavalue":{"value":{"entity-type":"item","numeric-id":3340178,"id":"Q3340178"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3dd27e2d8ae7b8006d2116d46f2369881537c828","datavalue":{"value":{"amount":"+0.84114784","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":"Q1124356$66A4BE13-EA7B-4000-A72C-9C816EFAAA0F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6e31e8f1ccf46fd035314bbae1785551c5dbf4e3","datavalue":{"value":{"entity-type":"item","numeric-id":3028987,"id":"Q3028987"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"19eb28174099e327654ce6c73108bdb1a3fa937e","datavalue":{"value":{"amount":"+0.84005356","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":"Q1124356$5E2B24B0-71F0-4D5E-A376-2CBC9EF9EA57","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Prefix and equality languages of rational functions are co-context-free","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Prefix_and_equality_languages_of_rational_functions_are_co-context-free"}}}}}