{"entities":{"Q1115633":{"pageid":1126382,"ns":120,"title":"Item:Q1115633","lastrevid":42886666,"modified":"2025-07-15T17:45:52Z","type":"item","id":"Q1115633","labels":{"en":{"language":"en","value":"A representation of recursively enumerable languages by two homomorphisms and a quotient"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4087048"}},"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":"Q1115633$A505FC53-539C-4CB9-913B-C75D5653C9B8","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"9a9b780a9fb29b7433b4d438704f28e7aecab686","datavalue":{"value":{"text":"A representation of recursively enumerable languages by two homomorphisms and a quotient","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1115633$2ADBA063-C8DE-4533-B23C-C2014F3D2D25","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"72ade5520999c6ebbeef252ccaf769998dce0fbf","datavalue":{"value":"0664.68075","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1115633$1578D15A-AFDD-41E4-B483-F257D1654FCE","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"5a15be87587742c596e96d9c3548cd080c60a506","datavalue":{"value":"10.1016/0304-3975(88)90068-0","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1115633$7DF02B0E-F19D-4643-BC7B-C661C420C28E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"3336a40cc821600c2cc57c5ef4dc532be5780cea","datavalue":{"value":{"entity-type":"item","numeric-id":442278,"id":"Q442278"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1115633$37521B4E-880C-4D31-8EAB-033D9E5E7560","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":"Q1115633$689DEB05-D262-4A80-8182-C1784AD5593C","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":"Q1115633$74235258-7FDE-4DA6-9BC4-87300E6019CE","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"f548dbfc2a756263c2348685763064ba5265f7f7","datavalue":{"value":"For two strings x and y, \\(x\\setminus y\\) is the string z when \\(y=xz\\); otherwise \\(x\\setminus y\\) is undefined. The author proves the following representation theorem: For each recursively enumerable set L (over alphabet \\(\\Sigma)\\) there exist two homomorphisms \\(h_ 1\\), \\(h_ 2:\\) \\(\\Sigma^*_ 1\\to \\Sigma^*_ 2\\) \\((\\Sigma \\subseteq \\Sigma_ 2)\\) such that for every \\(w\\in \\Sigma^*\\), \\(w\\in L\\) if and only if \\(w=h_ 1(x)\\setminus h_ 2(x)\\) for some \\(x\\in \\Sigma^*_ 1.\\)    The author discusses some complexity issues related to this representation and also some variants of the representation result.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1115633$35F25BB4-B2A4-45F2-A8A6-D7E0F6A821FD","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1115633$69FE7480-C9F5-4999-9132-59C64EDF80A4","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"aeb7e3e9971a345dbed1edd3bea088138244270d","datavalue":{"value":"4087048","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1115633$39F03AAF-CA0E-4FBF-88B5-5BF11AFCA449","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"04cdd5fb884b99b76f46dc32107e7543cf1bbfe5","datavalue":{"value":"quotient","type":"string"},"datatype":"string"},"type":"statement","id":"Q1115633$E15344C5-BF07-492E-9345-248F5D067E76","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"23c7031418e51cc601e012608d4b8d0d0c53a567","datavalue":{"value":"recursively enumerable set","type":"string"},"datatype":"string"},"type":"statement","id":"Q1115633$455CAFF5-250A-4C5F-8F6A-1C8E61C92575","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"db142dd107fdc467fbdf3710d60d5927512fee12","datavalue":{"value":"homomorphisms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1115633$3B5368ED-3522-4A67-9099-BF320269F345","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"729ce7d30b006e0a0feac3738fe17ebb7f491306","datavalue":{"value":"representation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1115633$DBB36D3D-1897-4F22-BB21-81AC736E7EEF","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"cb3a3ba65440da04d49f30062ed2e12f784ddb41","datavalue":{"value":{"entity-type":"item","numeric-id":235683,"id":"Q235683"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1115633$BF6FFD5E-DB0A-4CD9-8D30-231FE8AD3C00","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":"Q1115633$1E478CF3-CC43-4588-ABC6-7C4477079923","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"f4aab9f7026e590e83c84547222528fd12cc11c8","datavalue":{"value":"https://doi.org/10.1016/0304-3975(88)90068-0","type":"string"},"datatype":"url"},"type":"statement","id":"Q1115633$63F80999-1211-4560-A6F5-C0486A710C1E","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"407d9324f023a0910e3945de73e3cea870cff389","datavalue":{"value":"W1986713860","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1115633$25EB35A1-6280-47FA-A460-EE06B1C0CF0A","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"4c822ac56edac078ea752527f73f4d5749976935","datavalue":{"value":{"entity-type":"item","numeric-id":4178516,"id":"Q4178516"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1115633$CC9B87D0-8106-4D07-ACC0-F242BD50C335","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1f66c0dd9a99a1802ad994b252cad0f5fe21cdaa","datavalue":{"value":{"entity-type":"item","numeric-id":3888530,"id":"Q3888530"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1115633$18D1DB57-FD18-4459-B5C9-1B71ED8E64EF","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":"Q1115633$06020A35-C1D1-4C79-9764-49DD52E707E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9883685f8982ef7217af2959a8ae7553faf80889","datavalue":{"value":{"entity-type":"item","numeric-id":3751035,"id":"Q3751035"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1115633$1D4A777C-EE3E-45A7-A680-F513EFD4A49B","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":"Q1115633$425C9C69-4EC2-474F-B82B-2F233B4A7CE5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5af7139c65837eb8115c64cb4d4e1bbefc86dded","datavalue":{"value":{"entity-type":"item","numeric-id":4198075,"id":"Q4198075"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1115633$029A48C0-5F6E-451F-8F04-0B09C5CF66E3","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":"Q1115633$84263318-115B-4244-AF46-1FA6E2430E6C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"073e6727c2910e839775c3deeb4d964ec4fd4862","datavalue":{"value":{"entity-type":"item","numeric-id":3953199,"id":"Q3953199"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1115633$AC016EB0-36C2-4A10-93B0-9C7B759D462A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a9500e19069722efa256e9656f8110bdcd87d826","datavalue":{"value":{"entity-type":"item","numeric-id":4140407,"id":"Q4140407"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1115633$ED020E27-00BB-4473-B7BB-32CD87491553","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c2272aa4973074398e28346f7bb9b2bf856c1a8f","datavalue":{"value":{"entity-type":"item","numeric-id":4194484,"id":"Q4194484"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1115633$34897202-EBBB-4C36-B667-82CB8E920CBF","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":"Q1115633$11B6AC5D-9BED-4B21-818E-423DFE2D0E0E","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e74231ee3733b7488a65df54829086a40571de52","datavalue":{"value":{"entity-type":"item","numeric-id":1061494,"id":"Q1061494"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f5237a9c357121ea9c860c4ea4e22b298d8ee22e","datavalue":{"value":{"amount":"+0.9348943","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":"Q1115633$418A795E-3E13-4BC9-A21E-D342CD164508","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"496d1c04dc0eaef035a066b3ccc09d867c70c2be","datavalue":{"value":{"entity-type":"item","numeric-id":4005180,"id":"Q4005180"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9681e9877a252b7547afb5979312dd03c9e811e3","datavalue":{"value":{"amount":"+0.9022972","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":"Q1115633$9068CDB5-6584-4B36-8DDD-1B621F095581","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9182552e63b828485598dc42348689202948e653","datavalue":{"value":{"entity-type":"item","numeric-id":1589418,"id":"Q1589418"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f8203960db24fb20e38f34ff7808c98a0de108b5","datavalue":{"value":{"amount":"+0.90105796","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":"Q1115633$F156A175-C0A9-4C14-8520-6C89A15C039C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"eee42b14bd6fcfd53d82dd7333d398a6b014da80","datavalue":{"value":{"entity-type":"item","numeric-id":1262786,"id":"Q1262786"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0b72325d9a95e87ac3ae1459b60442a7963035ae","datavalue":{"value":{"amount":"+0.8990208","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":"Q1115633$09EAF2E4-3423-4AE1-8C40-CCDE8A7DD679","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cbb2840bfdc4195581749d4c9bfb7c25d6345f1c","datavalue":{"value":{"entity-type":"item","numeric-id":4005181,"id":"Q4005181"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"30946bfaf0431cdea635ba4fa4078bbf7b7a057e","datavalue":{"value":{"amount":"+0.89696413","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":"Q1115633$46C4D1AE-0DF1-4533-ADE0-A67CA2562BB8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cfa0f0ccc47919955950f7a8fb6701c0e77bd6d8","datavalue":{"value":{"entity-type":"item","numeric-id":4336268,"id":"Q4336268"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0c7c1393e50792d41423f48a02e648acdd31414e","datavalue":{"value":{"amount":"+0.88696295","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":"Q1115633$663A984B-B0D0-4B05-9569-6F369E01DD23","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e958e2765b1605a6e289767f33f54f0fcdd6cf4e","datavalue":{"value":{"entity-type":"item","numeric-id":4541813,"id":"Q4541813"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f4b4f52ae814980fd942da13ba0108265c6bd0b3","datavalue":{"value":{"amount":"+0.879056","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":"Q1115633$F1980B44-8BC8-43DB-B1CB-ABA816C10430","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"282151eaf72b1f708732dac5cdc74d60531ed7f3","datavalue":{"value":{"entity-type":"item","numeric-id":1826643,"id":"Q1826643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"aaca9296b1b49f99a9941478c691155872a99b44","datavalue":{"value":{"amount":"+0.8788255","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":"Q1115633$062CAC3B-0595-40A7-943C-74A7386EC751","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"df56f6378683ac44f53cb3672be428f5bed1c707","datavalue":{"value":{"entity-type":"item","numeric-id":1275069,"id":"Q1275069"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"da7fab2446ae765852fc8e840d0796268c483204","datavalue":{"value":{"amount":"+0.8716411","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":"Q1115633$7E1FA85A-BD1F-49E5-B1C7-53C138DD20E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bdf88225148b54627cb4715bc7191042f082a3b8","datavalue":{"value":{"entity-type":"item","numeric-id":3974879,"id":"Q3974879"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b835ac6d581589d3db234956ec92a94145b074c8","datavalue":{"value":{"amount":"+0.87061274","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":"Q1115633$81F1691E-C02C-4252-B23B-44F846C4C7D0","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1115633","badges":[]}}}}}