{"entities":{"Q1637233":{"pageid":1647974,"ns":120,"title":"Item:Q1637233","lastrevid":68189559,"modified":"2026-04-12T22:01:47Z","type":"item","id":"Q1637233","labels":{"en":{"language":"en","value":"On fixed points of rational transductions"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6882163"}},"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":"Q1637233$1F0872B9-A25D-4E05-B9AC-B3711ED9343B","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"2d36f286019c1facd987f36e55d83bc862def8de","datavalue":{"value":{"text":"On fixed points of rational transductions","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1637233$52291C28-F8F7-4FB3-A907-7CDA31B0DF5F","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"cf6ea82047e90699351971fae81680b6545445bd","datavalue":{"value":"1412.03019","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1637233$59F4336E-F781-4A01-AED5-A57E80118F39","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"59d83211de22bb9037eb8bb17627d49ead9fa4a9","datavalue":{"value":{"entity-type":"item","numeric-id":287018,"id":"Q287018"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1637233$2DEB835C-94E7-470D-BDE6-CB052BD6057E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"dd30f3f0d1798b43b8e423e2420eb7e5d7953751","datavalue":{"value":{"entity-type":"item","numeric-id":1637232,"id":"Q1637232"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1637233$79B1E410-3A80-46AD-8A80-77FAA1C6EAF6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"2e1040094bf74402ed6fa4c78436dda64e324757","datavalue":{"value":{"entity-type":"item","numeric-id":1806108,"id":"Q1806108"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1637233$3DB7E7F1-A82A-4EDB-8CF8-D153230C850C","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":"Q1637233$2EBB0038-73F7-4296-9850-0952338DDB47","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"a7242f351a269c151a4bcbb89f8c58bd1bc53a92","datavalue":{"value":{"time":"+2018-06-07T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1637233$7BB08738-39AB-44BE-B3B7-4944DFE79C55","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"700bcded6e34f24ec7a8ea8cdfc39b1276fea46e","datavalue":{"value":"In this short paper, the authors prove that the fixed point problem for injective rational functions is undecidable. A function is called rational, if it can be computed by a transducer (an automaton with outputs). For this, the authors use the undecidability of the Post corresponding problem for injective morphisms and some characterizations of rational transduction functions by Nivat and Latteux-Leguy. As a corollary, it is shown that the fixed point problem is undecidable for injective computable functions (on natural numbers).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1637233$531A8DC4-C556-4D21-B111-520CCF75F4C4","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"4bc285a01ee2fee3db93f6df1148b69669dc8b6e","datavalue":{"value":{"entity-type":"item","numeric-id":590045,"id":"Q590045"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1637233$46A22330-AD0C-43B6-8578-8C2756BC19FF","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"a27f9f06d965be24ec50f61065e06d2029a566a7","datavalue":{"value":"03D35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1637233$6A320491-6A21-4E16-B79E-83DFC2F0F637","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1637233$6C924EF3-6319-4463-842A-0560DE839F58","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"37e194b63c9b072c0bb1081b5f40ff02e589a565","datavalue":{"value":"6882163","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1637233$D08F1B22-BA62-4FD6-8DE1-AC281ADF1D4C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a9a7b0cf17169865b15e8c9d7014c24bafb8410c","datavalue":{"value":"fixed points","type":"string"},"datatype":"string"},"type":"statement","id":"Q1637233$23FDE408-1C72-4B18-819C-E21F0729732B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"afd17ebcd4b5536029790b819e380a81a8678fec","datavalue":{"value":"rational transductions","type":"string"},"datatype":"string"},"type":"statement","id":"Q1637233$3FAB7097-5437-4C52-83AC-66E47E8ACA52","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2167c1603df170ff5458e34a919f1857d40b24b1","datavalue":{"value":"post correspondence problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1637233$2B0CD16D-0653-4F36-ABCF-81DEEE0FFBDE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f2044add9ca8fad740e250d0f997cab331928bce","datavalue":{"value":"injective PCP","type":"string"},"datatype":"string"},"type":"statement","id":"Q1637233$82BB4601-B66F-446E-AE9F-BAC2C3250DE8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"48fe5da30f2000a910dd1a06f280ea2b3174328d","datavalue":{"value":"decidability","type":"string"},"datatype":"string"},"type":"statement","id":"Q1637233$62A54581-7CDE-4DA9-B899-10B9989B4B39","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":"Q1637233$390623BA-996C-40B7-9AE3-52B99422FE07","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"f6d64ef9755c1ef73f7f2c48fe39c0583fecccba","datavalue":{"value":"https://doi.org/10.1016/j.tcs.2018.04.030","type":"string"},"datatype":"url"},"type":"statement","id":"Q1637233$F849F4AD-2E90-48CB-B3F7-C30620D488A1","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"78c4afefa282092b88e1ce5c45a852ebdc349028","datavalue":{"value":"W2802922619","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1637233$E5750550-0A6B-4E64-A3BD-3D133DD7D401","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":"Q1637233$82C20C9F-180D-44D4-B209-45C8E6F41656","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fe929f01fa86af5ec1780a3fd0d8f9ac3346a63b","datavalue":{"value":{"entity-type":"item","numeric-id":4714446,"id":"Q4714446"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1637233$98A51709-C6CD-408D-8A75-238E8972003F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e0c5cfb3d178d43826ee569fdac066339db3f2cc","datavalue":{"value":{"entity-type":"item","numeric-id":5414545,"id":"Q5414545"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1637233$B58743E4-DB04-45F3-9F57-4CDA7F63641E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4d4710ed058b1391d623f9ad5b2f5a085ff13f94","datavalue":{"value":{"entity-type":"item","numeric-id":3674079,"id":"Q3674079"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1637233$65C34767-10D0-44AC-9047-DD0B0370CA05","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"aac892d27a03563e9b14e13872e570d1bd56d99d","datavalue":{"value":{"entity-type":"item","numeric-id":5586335,"id":"Q5586335"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1637233$AF0A1542-EA1D-4304-8237-2C6B53BCE32B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"29a8d14eae1fab181499f44d4720082adebedfb9","datavalue":{"value":{"entity-type":"item","numeric-id":5845383,"id":"Q5845383"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1637233$9D7B417B-C447-4B31-8E7E-D5DC4B15C154","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"06ef6793a6bca14ceb02ba7d1c63fc8a26092bfd","datavalue":{"value":{"entity-type":"item","numeric-id":3741057,"id":"Q3741057"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1637233$A6B2BA57-7E4F-4250-8C89-5F4D0677B378","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f0ee39b073dbcae23fd86625bc24634b1f64ac38","datavalue":{"value":{"entity-type":"item","numeric-id":3644388,"id":"Q3644388"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1637233$B01C2B65-57DB-4BD8-8DAF-F82874A8BB60","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"56aa7a343db226e6c7da9bd7db585a412df58862","datavalue":{"value":{"entity-type":"item","numeric-id":5678435,"id":"Q5678435"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1637233$87A89841-2505-4BA2-88F5-2182571A2849","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"26908873f23060d6e2c3c9b7f95cc07980a3cd1e","datavalue":{"value":"Q129911783","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1637233$D05B78CC-E55C-4211-82DA-183E712C9D7B","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"2abaa12a3722992bf947a3137fa0498211ef0337","datavalue":{"value":"10.1016/J.TCS.2018.04.030","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1637233$3AF5BC66-67E8-4B25-BB82-82FD1C6B1BE2","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"af1de0b6705830a9f8d103da723692404cbea225","datavalue":{"value":{"entity-type":"item","numeric-id":1822509,"id":"Q1822509"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4c4b41658bad62e2756ffc2a9bbec03f2b62c488","datavalue":{"value":{"amount":"+0.8420541286468506","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":"Q1637233$863D343E-9D24-4D9E-8813-7DB721E523B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"669844b2376d9d24de2b898649a387f9b4865df5","datavalue":{"value":{"entity-type":"item","numeric-id":3700861,"id":"Q3700861"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5c3857be7c8e47eca0852a6aec9c037e1d18e84d","datavalue":{"value":{"amount":"+0.7966501116752625","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":"Q1637233$361BCA98-1CB6-457C-BFFE-38188425FA33","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d71adf7da1b300612ec2196533692ae591196734","datavalue":{"value":{"entity-type":"item","numeric-id":1823712,"id":"Q1823712"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1130352b2cfdd39ee3dcb10aac662f4303443b65","datavalue":{"value":{"amount":"+0.7885589003562927","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":"Q1637233$A78DC33F-A6FD-4C96-A262-8817654AD136","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"295f9f49f30f68d0abfa2b0a9d713522fcbb6a93","datavalue":{"value":{"entity-type":"item","numeric-id":4884888,"id":"Q4884888"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1493c792e171f3c44ae89996a7ed279749796f12","datavalue":{"value":{"amount":"+0.7756184339523315","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":"Q1637233$6025A992-3ECA-401F-8812-2E71420F212A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1bf1643a7e279a4b01d5ce736e997906d115bdd2","datavalue":{"value":{"entity-type":"item","numeric-id":2805459,"id":"Q2805459"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2278dbf21d421359a699c8453b5336561fe13127","datavalue":{"value":{"amount":"+0.7624360918998718","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":"Q1637233$85859BE6-E5E2-48C0-B8FA-F85D6CA798D0","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On fixed points of rational transductions","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_fixed_points_of_rational_transductions"}}}}}