{"entities":{"Q685348":{"pageid":687197,"ns":120,"title":"Item:Q685348","lastrevid":63459465,"modified":"2026-04-11T13:18:13Z","type":"item","id":"Q685348","labels":{"en":{"language":"en","value":"Single-valuedness of tree transducers is decidable in polynomial time"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 417313"}},"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":"Q685348$DB29CFE2-FC70-4AB5-8B74-338D5F824D18","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ff65c15e03f07c1141c902ad24d39ebe575285c6","datavalue":{"value":{"text":"Single-valuedness of tree transducers is decidable in polynomial time","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q685348$99067BA3-FEE2-4291-9F83-3C728ACB0AD2","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"f084090e904f094789f0293bad2053ce8a34a73c","datavalue":{"value":"0783.68086","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685348$62359A23-2E8B-434A-BE49-8E2A714A4152","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"668347ca1f7198ed4a3578a9d0dec55a835d2697","datavalue":{"value":"10.1016/0304-3975(92)90281-J","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685348$5C340C82-5EDB-4043-ADD0-361C7A266583","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"0d8846866e0f2e2874e781dfcefe3a000615efed","datavalue":{"value":{"entity-type":"item","numeric-id":435967,"id":"Q435967"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685348$18846C25-A78E-4C8D-953B-23C31ECC3384","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":"Q685348$CB58049C-737D-42F9-994B-2D3DC0689598","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"ea9458ce3029a7f683c04e43e886fdc910ea299c","datavalue":{"value":{"time":"+1993-10-17T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q685348$5CFD172B-CFFD-4094-93F6-B75E202E2DEE","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"34d0b9aee15e6c3e5d37a47a83c4bfd59f6d63f1","datavalue":{"value":"A bottom-up finite-state tree transducer (FST) is a generalization of a generalized sequential machine that outputs a tree while scanning an input tree in a bottom-up fashion. A deterministic polynomial time algorithm is constructed to decide whether a given FST is single-valued. It follows from this result that the equivalence problem of deterministic FSTs can be decided in deterministic polynomial time.","type":"string"},"datatype":"string"},"type":"statement","id":"Q685348$0F57B1E1-A67F-411C-A9E3-20EB09580A4E","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685348$45EE0746-D356-487B-B718-3D808C4E91C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685348$8BB835BD-E6EA-4504-B808-55E74B96E320","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"63466e171d9b17bb987e00b05f874789cf32d21f","datavalue":{"value":"417313","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685348$98AB91A2-41AA-4D98-8719-D02202C6D47A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c24938459dbf20196734dcf6c3a35c8a8724abee","datavalue":{"value":"trees","type":"string"},"datatype":"string"},"type":"statement","id":"Q685348$16CDBE33-FBCE-4D9D-A067-C8A77E76DC96","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f7f80ab45fa757bd640991a524786e75328c3d16","datavalue":{"value":"tree transducer","type":"string"},"datatype":"string"},"type":"statement","id":"Q685348$90B7EC25-1E40-472C-A0C2-E3FE5C5A94DB","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":"Q685348$09F942E2-DB4C-466F-8ABB-80F42AFDC0F9","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":"Q685348$BCD8A2C4-C844-42BF-911F-9C1B49F6F2E3","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"cc38abbcbe7967bc27f3df504ecabdc1246d5071","datavalue":{"value":{"entity-type":"item","numeric-id":1162363,"id":"Q1162363"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685348$BF632B5C-FBD6-4C26-935C-34C8DB9BECCE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"239e14608bb684951922f9c8bb30036c33157150","datavalue":{"value":{"entity-type":"item","numeric-id":1090467,"id":"Q1090467"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685348$2AC1E2BD-AA20-4B12-A5A1-741203CFCCF4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ae19a70a8616a64987bb08271f6f085e5255b8c5","datavalue":{"value":{"entity-type":"item","numeric-id":3908476,"id":"Q3908476"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685348$99B9CBE6-4A87-47D4-AF3A-8BFE04F932DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8d2d9e161ff28bc5eaed06bd7b5efe2b101686b1","datavalue":{"value":{"entity-type":"item","numeric-id":3906457,"id":"Q3906457"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685348$50DFB8B1-2AD8-41C5-A3CE-8E1C24123106","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5709c2ffa01c029b486c6e705fa60fd703dea1c8","datavalue":{"value":{"entity-type":"item","numeric-id":4179852,"id":"Q4179852"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685348$E61F9C5E-177E-4429-AFE9-985BF29767EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4ec4381951d1090e976da26f9efce8ed4969ea40","datavalue":{"value":{"entity-type":"item","numeric-id":4035247,"id":"Q4035247"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685348$827D87E8-CBF5-43F6-9B27-C4B7B304213C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d6d3b9e332dcc324492fbcea8e6109cb2f093bb9","datavalue":{"value":{"entity-type":"item","numeric-id":4160409,"id":"Q4160409"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685348$8D0A612A-C062-4C94-91D6-484291025BD4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dc974d370f3f3f2c0fa14da1160bbca2b962ae53","datavalue":{"value":{"entity-type":"item","numeric-id":1238433,"id":"Q1238433"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685348$00B78AB4-A32D-4C68-A07C-FF019EC6CAA7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b0be4dd2ae12a720ae36eac84d798bf58f9d5aeb","datavalue":{"value":{"entity-type":"item","numeric-id":1825038,"id":"Q1825038"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685348$2DCEE956-90DA-4413-98C7-D9310445F0C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"068ff9bc22782d1999dd390113545d9fb239fc9c","datavalue":{"value":{"entity-type":"item","numeric-id":3477969,"id":"Q3477969"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685348$56F451EC-4D56-4A31-8343-A49FB3EFBC41","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0c8e38a0f004ff25f744a39b8197ce49ff3b22c2","datavalue":{"value":{"entity-type":"item","numeric-id":4027634,"id":"Q4027634"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685348$C73D43C2-76D6-45E4-ABFA-A4C691438274","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5b14874328e06322f55427a98ad1a9767d46fe80","datavalue":{"value":{"entity-type":"item","numeric-id":1120286,"id":"Q1120286"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685348$16A27D23-C0D0-4D35-8C9C-F482D23216D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1fa22f8aff22e13e4d39e750cd85bc8c4c016386","datavalue":{"value":{"entity-type":"item","numeric-id":3795238,"id":"Q3795238"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685348$FBCBE262-9F51-4495-93F8-BFC28EA5B552","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5f4a9f58ed78bdd3bc1680086a81cd74444e0373","datavalue":{"value":{"entity-type":"item","numeric-id":3975172,"id":"Q3975172"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685348$8FE7431B-AA3D-4350-A3C6-0D95477F01D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4c55b45a3aca375756d29d078b25e4aaeb0c01b3","datavalue":{"value":{"entity-type":"item","numeric-id":1177168,"id":"Q1177168"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685348$3C408AC6-160D-47DA-AA9B-138643B7BE82","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6338adf38cc4f260496173bee61b08c5ff48a323","datavalue":{"value":{"entity-type":"item","numeric-id":4185831,"id":"Q4185831"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685348$09EB60C7-E83F-4B15-8795-96F93A976638","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f93f6cf8d7b62d87679a559f02ff5f9a30ce01a0","datavalue":{"value":{"entity-type":"item","numeric-id":4027634,"id":"Q4027634"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4da223d557675787c260597a979fb59cf0f759e8","datavalue":{"value":{"amount":"+0.8880184292793274","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":"Q685348$A088CCCF-CADC-4ED4-A444-7058393BB93C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bc7c38e72be8f0eff9866845ee1cfd8572ebde50","datavalue":{"value":{"entity-type":"item","numeric-id":4037692,"id":"Q4037692"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"84bc23138099bfbf93b4db9a22c846095709ef16","datavalue":{"value":{"amount":"+0.8850730657577515","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":"Q685348$5F106916-5117-4DC8-AAF5-F4C38656B718","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"95e5cae3320bd3fcbc772e860d59f86ade00368d","datavalue":{"value":{"entity-type":"item","numeric-id":4301635,"id":"Q4301635"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8cb04310ad6dc7933e21a27600d37ee48595af3c","datavalue":{"value":{"amount":"+0.8845076560974121","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":"Q685348$838E3EC0-F422-4A80-9BF6-6C3E0D90ADBF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"30a94a95b9f171292fbc8f24520c91ab0cde143b","datavalue":{"value":{"entity-type":"item","numeric-id":5096729,"id":"Q5096729"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0fd40cf3957634e50198a9ebe210bc5585611f5e","datavalue":{"value":{"amount":"+0.8752948045730591","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":"Q685348$21DA81E4-7E91-4F9E-9C00-2D99433FF725","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f8520d7f7e9dd0e72b98448ad5eaaac31eddb8fb","datavalue":{"value":{"entity-type":"item","numeric-id":4910473,"id":"Q4910473"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6c183cdb9004dab4783b19494975368829bbee26","datavalue":{"value":{"amount":"+0.8422210812568665","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":"Q685348$310382DB-5838-49D3-8AF4-FDE79408EB1C","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Single-valuedness of tree transducers is decidable in polynomial time","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Single-valuedness_of_tree_transducers_is_decidable_in_polynomial_time"}}}}}