{"entities":{"Q807029":{"pageid":808877,"ns":120,"title":"Item:Q807029","lastrevid":64480851,"modified":"2026-04-11T20:10:16Z","type":"item","id":"Q807029","labels":{"en":{"language":"en","value":"A complete classification of deterministic root-to-frontier tree transformation classes"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4206003"}},"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":"Q807029$149A2C5C-4F36-4105-8670-C31813D6C9A8","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e5f85184738b3ed7d82282b0f708f035f46c2158","datavalue":{"value":{"text":"A complete classification of deterministic root-to-frontier tree transformation classes","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q807029$4CBC5B84-EBA7-4537-B62D-07B13132DC03","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"b0e216d07ecfe28d348f79b1dfc198c0e16f3d27","datavalue":{"value":"0729.68048","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q807029$ADB32353-30D4-49D1-84D4-C7963F64C0E6","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"b64b592157a314cd23d1706e99f2dda91bb3ad95","datavalue":{"value":"10.1016/0304-3975(91)90312-P","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q807029$4792674E-B630-43CE-AA43-835AC8568328","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":"Q807029$13D241EE-B069-46ED-9548-052775672BD6","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"391107ffc7a24346d69c573e292e4ff4587e3aaa","datavalue":{"value":{"time":"+1991-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":"Q807029$987B1178-5E68-44EF-9357-C4CCF80D65BE","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"08512149710a2d6d5b5a205a596d7950586a1aaa","datavalue":{"value":"A root-to-frontier tree transducer is a finite-state automaton which transforms trees (terms) into trees by processing the input tree from the root towards the leaves. The class of all tree transformations (TTs) definable by such transducers is denoted by \\({\\mathcal R}\\). Some of the natural restrictions imposed on transducers are determinism (\\({\\mathcal D})\\), linearity (\\({\\mathcal L})\\), the property of being nondeleting (\\({\\mathcal N})\\) or of having just one state, in which case the induced TT is a tree homomorphism (\\({\\mathcal H})\\). Any combination of such requirements leads to a special class of TTs; for example, \\({\\mathcal L}{\\mathcal D}{\\mathcal R}\\) is the class of TTs definable by linear deterministic root-to-frontier tree transducers, and \\({\\mathcal N}{\\mathcal H}\\) is the class of nondeleting tree homomorphisms. If \\({\\mathcal A}\\) and \\({\\mathcal B}\\) are two classes of TTs, their composition \\({\\mathcal A}\\circ {\\mathcal B}\\) is the class of all relational compositions \\(\\alpha\\circ \\beta\\), where \\(\\alpha\\in {\\mathcal A}\\) and \\(\\beta\\in {\\mathcal B}.\\)    The authors present a complete inclusion diagram for all compositions which ca be formed starting from the classes \\({\\mathcal D}{\\mathcal R}\\), \\({\\mathcal L}{\\mathcal D}{\\mathcal R}\\), \\({\\mathcal N}{\\mathcal D}{\\mathcal R}\\), \\({\\mathcal L}{\\mathcal N}{\\mathcal D}{\\mathcal R}\\), \\({\\mathcal H}\\), \\({\\mathcal N}{\\mathcal H}\\) and \\({\\mathcal L}{\\mathcal H}\\) (\\({\\mathcal L}{\\mathcal N}{\\mathcal H}\\) is uninteresting in this context). All pairs of incomparable classes, all proper inclusions and all proper hierarchies are shown to be so. For this a great amount of earlier work done in this area is utilized, but also several new results are needed.","type":"string"},"datatype":"string"},"type":"statement","id":"Q807029$559BCCE4-4884-49C9-A320-55106E7B6D29","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"6e07306c48ccd2e9c29ec0a26f6f3afb07223426","datavalue":{"value":{"entity-type":"item","numeric-id":591314,"id":"Q591314"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q807029$577137B2-E4BB-4582-88E0-0D9244044F8A","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"deb5f9f43f355c6575c467b17adc4a680e013b41","datavalue":{"value":"68Q70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q807029$60AB5D3B-156F-4F56-861B-051FE3F09E48","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"c636094cc8b933189eabd7c009d327f829bc6ac4","datavalue":{"value":"68Q42","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q807029$D5393BA7-257C-4F01-B3BD-A9CAFEF26A3A","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"75880d255e899bfd2d3d607b6d4f39c1919af8dd","datavalue":{"value":"4206003","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q807029$4AF14E6E-7CBF-40CB-A0D0-0BB02546242A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9bf5b1135aec66c7dfd4efb40de398bbfb469f69","datavalue":{"value":"tree transformations","type":"string"},"datatype":"string"},"type":"statement","id":"Q807029$08840431-00ED-4099-8992-F2A6B458DF96","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"4d00fa627735b22d11a5ec2028150137b2160228","datavalue":{"value":{"entity-type":"item","numeric-id":404009,"id":"Q404009"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q807029$D9004047-4549-470B-934D-9608C4BA6C0F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"1be1e97a61ec61b6b5428ec7bf911ab8a63c8c39","datavalue":{"value":{"entity-type":"item","numeric-id":389935,"id":"Q389935"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q807029$71850587-14F1-484F-AA7A-85CFC6C7F1EF","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":"Q807029$FEF0DAA0-3E57-49E2-9567-7E455F76332C","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"d0ccb3d15dea78d633cda8dffcef636710c8cbd7","datavalue":{"value":{"entity-type":"item","numeric-id":4195956,"id":"Q4195956"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q807029$9C9E1080-17BB-414B-BD37-5F1F51B6C4ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5abbb4252e48e81c9e2eb5b65ddb12bb1724efde","datavalue":{"value":{"entity-type":"item","numeric-id":4167603,"id":"Q4167603"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q807029$B08117E0-70A1-4E2D-8E66-8F8A5B5CCD4C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ef24932abd74e01a026e2e349f03bfd5726d23f7","datavalue":{"value":{"entity-type":"item","numeric-id":4102764,"id":"Q4102764"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q807029$0E0754BC-F7BA-4764-BEFD-65025B710308","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7c3941948c78b1b4e598e643befcf898affe34a2","datavalue":{"value":{"entity-type":"item","numeric-id":1247295,"id":"Q1247295"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q807029$156D2F2A-5ACC-4936-9632-A135B012A73F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9a18c8ab6e2d2a9acc4d84df0c9eccee124cc9dd","datavalue":{"value":{"entity-type":"item","numeric-id":4747534,"id":"Q4747534"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q807029$CCBA0828-A4A2-4DE7-9D1D-D44AE4023517","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9f7f9ed14f47635349292dc1fc5be666cede90cf","datavalue":{"value":{"entity-type":"item","numeric-id":4146263,"id":"Q4146263"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q807029$F2001FE1-6DDD-49E6-9701-B26D93266B01","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3bcf9290a285df8153ca9b953a5084489d9040e3","datavalue":{"value":{"entity-type":"item","numeric-id":918216,"id":"Q918216"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q807029$2C0B0E4F-43C4-471A-9969-400B44DD36C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"48af75edc282cb4ea570d6a644216b81edcc9766","datavalue":{"value":{"entity-type":"item","numeric-id":3832055,"id":"Q3832055"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q807029$D2B987FE-A5AA-419C-8B18-BEA3F8C0B834","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cb4ea97960134aeb7944d6d6ef33a7f8b8c05292","datavalue":{"value":{"entity-type":"item","numeric-id":3813315,"id":"Q3813315"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q807029$28DFE352-2E03-4F85-BE9D-E479470B0145","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9a934c95343f5669a8d2db134905f65dede6d62d","datavalue":{"value":{"entity-type":"item","numeric-id":3028362,"id":"Q3028362"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q807029$937035A1-1403-44A8-B8AC-AB921CEB7750","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":"Q807029$1C3977FA-74F2-4679-8638-76521B957FAA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1d63be057f1dbf872e8af155ca01c9414977fab2","datavalue":{"value":{"entity-type":"item","numeric-id":5603192,"id":"Q5603192"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q807029$C76CAE94-0BD4-4611-864D-91FF96273B61","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b966808ee9c0072c8088b0c39fe14c48405ed89f","datavalue":{"value":{"entity-type":"item","numeric-id":2540272,"id":"Q2540272"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q807029$7A31789D-273C-4EC7-AC29-8EBA3ED935FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9d4a8db546bd4002de0d898b78cf037d04755bd0","datavalue":{"value":{"entity-type":"item","numeric-id":3779776,"id":"Q3779776"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q807029$E6657B38-C947-4983-9E01-94D263627EB3","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6e755d42bd8fac8c4843a2bd2d899a57fbe9cc27","datavalue":{"value":{"entity-type":"item","numeric-id":3028362,"id":"Q3028362"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"90184946ffded3fd6027a4ca7346d7b631424819","datavalue":{"value":{"amount":"+0.908564031124115","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":"Q807029$EFB8138B-A3B9-43CD-8AF0-213BF3B9D20E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6b4e92aa946a1dd31e3a4a57332e2eb524b6ea62","datavalue":{"value":{"entity-type":"item","numeric-id":3779776,"id":"Q3779776"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"520ff8a32dd562f577d39299bd559d03a9408d31","datavalue":{"value":{"amount":"+0.863436222076416","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":"Q807029$E6E53FB4-E904-46C1-96DB-0D4EFF780176","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"76c57273f8e881f5adbed4b435d4257703146160","datavalue":{"value":{"entity-type":"item","numeric-id":1177164,"id":"Q1177164"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"96a270457399f58333fa0b361cb3111e7bdb1c47","datavalue":{"value":{"amount":"+0.8585864305496216","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":"Q807029$4646C3A9-626A-4604-B4A7-00A129955604","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"471ebfe8c6d0624ec6213a633f4aa784f597e9a3","datavalue":{"value":{"entity-type":"item","numeric-id":4284265,"id":"Q4284265"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3c0966bd6f7d6b13317567bc4a6094786752eee5","datavalue":{"value":{"amount":"+0.8570555448532104","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":"Q807029$5695D005-AE06-4FE6-A410-F263BC93F01D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4d5ab33657f26aa5efaf7c56a9f491c65d818774","datavalue":{"value":{"entity-type":"item","numeric-id":4866680,"id":"Q4866680"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5703ebbbcbc44e267eabab72cc4b0fe231fa41ad","datavalue":{"value":{"amount":"+0.8553546071052551","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":"Q807029$81762C89-2E59-459E-B2A6-A92990875C4D","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A complete classification of deterministic root-to-frontier tree transformation classes","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_complete_classification_of_deterministic_root-to-frontier_tree_transformation_classes"}}}}}