{"entities":{"Q1861212":{"pageid":1871954,"ns":120,"title":"Item:Q1861212","lastrevid":73905780,"modified":"2026-04-14T17:41:11Z","type":"item","id":"Q1861212","labels":{"en":{"language":"en","value":"The homomorphism problem for the free monoid"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1882149"}},"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":"Q1861212$AC0D98D2-DCE4-4ABC-B091-836E40470632","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e66239c6d45e889a1518c8d931581bfe98e8163b","datavalue":{"value":{"text":"The homomorphism problem for the free monoid","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1861212$D5248966-6749-46A6-BB21-A7DDF1800F38","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"35bd1c8286aff4434b1baf5a35fad3d5ec9da44c","datavalue":{"value":"1022.20027","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1861212$635714A9-5D3E-4B30-AC6D-DF54DC63B651","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"ad5c3a4e2ac1a0dd611e40d5ae92d46bc32b4d07","datavalue":{"value":"10.1016/S0012-365X(02)00380-1","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1861212$ED446CC2-0698-4AB8-84F8-41B7CD845BE9","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"03848aafebd36dae93d3398974c0009436f0a4c6","datavalue":{"value":{"entity-type":"item","numeric-id":232529,"id":"Q232529"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1861212$EA184B52-C376-40B1-A106-FB10B65F3B8E","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38665fe4ed2b835132254a58832c329597060029","datavalue":{"value":{"entity-type":"item","numeric-id":175483,"id":"Q175483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1861212$8CB52170-4EA4-49F0-B866-1CDF25540131","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"f8bf6de10654777949678e7fb8229d0ea51a7448","datavalue":{"value":{"time":"+2003-03-16T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1861212$0CC06841-3171-4AB6-8AA7-6CC13B507285","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"82a73b2ee2a99db4cac983436396e7c2b95da914","datavalue":{"value":"The following extension problem for mappings is shown to be algorithmically decidable: given a finite subset \\(F\\) of words over an alphabet \\(X\\) and a mapping \\(\\varphi\\colon F\\to X^*\\), determine whether or not \\(\\varphi\\) can be extended to a monoid homomorphism \\(F^*\\to X^*\\). This result gives another solution to the isomorphism problem for finitely generated submonoids of free monoids, a result due to \\textit{C. Choffrut, T. Harju}, and \\textit{J. Karhum\u00e4ki} [Theor. Comput. Sci. 183, No. 1, 83-92 (1997; Zbl 0901.68096)].","type":"string"},"datatype":"string"},"type":"statement","id":"Q1861212$2A01CECD-D6ED-4B35-8527-E064360C7B20","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"6e0db3e87cf0564d4c180dc3531c145e91e81ccd","datavalue":{"value":{"entity-type":"item","numeric-id":1806108,"id":"Q1806108"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1861212$FC3D7E23-9748-494E-A46A-45444B639D3B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"03468f1d5abafefed311cc9ccae9ddd73ff4dbd8","datavalue":{"value":"20M05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1861212$E4F934CF-2126-4A4C-8C98-DA0ED7F775DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"23149673dde05813672617e26c3fcb130092997c","datavalue":{"value":"68R15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1861212$F0C53254-1EAB-4B4D-B7A8-502832AA5E16","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"161452d058224a660e3b8a96064cc184f10828db","datavalue":{"value":"20M15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1861212$AA525037-5213-4BED-8C9E-1966F72B1A47","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"9a1ec3614f00e6dcf5bbb84aa27f49dab96e1537","datavalue":{"value":"1882149","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1861212$2239DAB5-40D8-4FF1-8CA4-49C20F849F07","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"290dd772808bcb257f93b2eb167b09578a0fdf51","datavalue":{"value":"homomorphism problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1861212$C601200C-7B2D-4EBB-B0B4-EABA83D8EEB4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b181606adcba6432b0019d481c67f516d9807857","datavalue":{"value":"isomorphism problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1861212$1E55388E-F30C-4B47-B31D-BD1A4372A099","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c48b241c2e53ac9c4073e4f6a37f6442b7c79d7d","datavalue":{"value":"free monoids","type":"string"},"datatype":"string"},"type":"statement","id":"Q1861212$28AAD38D-9E7E-453C-9DEB-1636BF0D702B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"48fe5da30f2000a910dd1a06f280ea2b3174328d","datavalue":{"value":"decidability","type":"string"},"datatype":"string"},"type":"statement","id":"Q1861212$EB430427-C9D8-4B9C-BAF0-B3922AB60252","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":"Q1861212$19137C5C-278B-432D-BD9E-09A71A0EDA67","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0818d5ee449955ecf61043fffbd93e06099913ef","datavalue":{"value":{"entity-type":"item","numeric-id":1426045,"id":"Q1426045"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6e2b5c2a8d310a11651ed70a39fd43dc9309133f","datavalue":{"value":{"amount":"+0.8311333656311035","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":"Q1861212$B6DEB318-2534-46F4-B3E8-69CA1885C51F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"70c9aa4d0a0c62fb4add370e1fb8353baa13bc94","datavalue":{"value":{"entity-type":"item","numeric-id":974649,"id":"Q974649"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"34cb7eb5747847bf1153c8f447078b29998e7992","datavalue":{"value":{"amount":"+0.7966938018798828","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":"Q1861212$404DF8A6-2D8A-48F3-BEBD-D70A80ED873E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cb9bd0e0c25f7417063a64a65fadb0ad625aff3a","datavalue":{"value":{"entity-type":"item","numeric-id":5478640,"id":"Q5478640"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"111115ed97bcea069e27cfb4e24c4ecc913b9b75","datavalue":{"value":{"amount":"+0.795645534992218","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":"Q1861212$72447686-02D5-4057-91C8-7EC9C4A3629E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f00f93dbc81f3c62e4614894dacf33aac07fb647","datavalue":{"value":{"entity-type":"item","numeric-id":3818494,"id":"Q3818494"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e1819f7dd3f0a27484ca0606d784143e992d9e0b","datavalue":{"value":{"amount":"+0.7795428037643433","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":"Q1861212$B4F716EC-2EA2-435D-B151-E4B5DE616078","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8578e6b375ee216a2671afdacc5230421661dce3","datavalue":{"value":{"entity-type":"item","numeric-id":3688567,"id":"Q3688567"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a2714024878013ee1504fd58a3a188dc09b7b0a5","datavalue":{"value":{"amount":"+0.7675876617431641","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":"Q1861212$1FD0ECE3-BF38-4699-91D1-EC20486AEAFA","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The homomorphism problem for the free monoid","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/The_homomorphism_problem_for_the_free_monoid"}}}}}