{"entities":{"Q1177164":{"pageid":1187913,"ns":120,"title":"Item:Q1177164","lastrevid":66768939,"modified":"2026-04-12T12:43:40Z","type":"item","id":"Q1177164","labels":{"en":{"language":"en","value":"A complete description for a monoid of deterministic bottom-up tree transformation classes"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 20018"}},"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":"Q1177164$BCCEF6E9-F90C-4363-BDBE-26A72E2898A8","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"f5bbc6a2886d73221b6fb7550b177b72e75cd15a","datavalue":{"value":{"text":"A complete description for a monoid of deterministic bottom-up tree transformation classes","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1177164$8C776086-31B1-4290-A23A-E4A01C8A7AA9","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"14b3564185605f89564fdef263ed6cb8be37774c","datavalue":{"value":"0741.68077","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1177164$A9F27BA0-8663-4A6C-834B-9650BAD36F13","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"3add890f11ee72f3e5a91ac824971ce6e2ca9b48","datavalue":{"value":"10.1016/0304-3975(91)90376-D","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1177164$DF1C2EEE-7D98-42CF-AD90-118A12621667","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":"Q1177164$3B0EAE8C-CBD4-4BC4-9E3D-CAC097AA730C","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"1422b5e3113eee9dc98f0455d275631058399b8b","datavalue":{"value":{"time":"+1992-06-26T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1177164$D0F8B280-394A-440E-813E-A149386CCAC4","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"96dd96a4b3be86b77328b6c73da4645e4ca3006e","datavalue":{"value":"Let \\(DB\\) denote the class of tree transformations defined by deterministic bottom-up (frontier-to-root) tree transducers. The subclasses of \\(DB\\) obtained by requiring that all rules of the transducers are deterministic or nondeleting, or both, are denoted by \\(LDB\\), \\(NDB\\) and \\(LNDB\\), respectively. One-state transducers yield the class \\(H\\) of tree homomorphisms. The subclasses \\(LH\\) and \\(NH\\) are defined in the natural way. The composition \\(A\\circ B\\) of two classes \\(A\\) and \\(B\\) of tree transformations is the class of all relational compositions \\(\\alpha\\circ\\beta\\), where \\(\\alpha\\in A\\) and \\(\\beta\\in B\\). The author studies the monoid \\([M]\\) generated by the set \\(M=\\{DB,LDB,NDB,LNDB,H,LH,NH\\}\\). It is finite and a complete inclusion diagram showing the relationships between its elements is given. The monoid \\([M]\\) is isomorphic to the quotient monoid \\(M^*/\\theta\\), where \\(\\theta\\) is the kernel of the homomorphism from \\(M^*\\) to \\([M]\\) which maps each word \\(X_ 1X_ 2\\dots X_ n\\) to the class \\(X_ 1\\circ X_ 2\\circ\\dots\\circ X_ n\\). The author gives a finite Thue system which generates \\(\\theta\\). Hence, a finite presentation of \\([M]\\) is obtained, and then the word problem of \\([M]\\) is proved to be decidable. In fact, the inclusion problem \\(``X_ 1\\circ\\dots\\circ X_ m\\subseteq Y_ 1\\circ\\dots\\circ Y_ n\\)?'' of composition classes formed from elements of \\(M\\) is decidable.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1177164$BFA3588E-F19B-4127-94CF-E8C41337D8BE","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":"Q1177164$8A142B98-196A-465D-B5BC-C9D06791AEF8","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1177164$047B271E-25FB-4B94-88D2-7B9901AE1621","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"c636094cc8b933189eabd7c009d327f829bc6ac4","datavalue":{"value":"68Q42","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1177164$DEDA33D6-E996-4721-9BBD-728DDA0E64BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"79c9a014785e41c94f76c463174af5cf2a59ec70","datavalue":{"value":"03D40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1177164$3A71C745-91FD-4988-95F2-385616CD14BE","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"219cf7404a3d8c190e928d7f13543000467744d5","datavalue":{"value":"20018","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1177164$B161CFCD-D20B-489C-9229-BF48091F5294","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4ba259c5c06af63100955fccf8bc8b370e89eaee","datavalue":{"value":"word problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q1177164$107B8C5A-61B8-43AF-A995-0EF5F0C3E12E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9bf5b1135aec66c7dfd4efb40de398bbfb469f69","datavalue":{"value":"tree transformations","type":"string"},"datatype":"string"},"type":"statement","id":"Q1177164$7D8ACBE3-D0DC-4FBB-BAA4-16B8364F69ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"121d3cd06600b0c796ffebf43959f5eb0036e791","datavalue":{"value":"Thue system","type":"string"},"datatype":"string"},"type":"statement","id":"Q1177164$28099051-6AFE-485F-9F03-B82A0533A3C2","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":"Q1177164$8CECD75E-3078-45A1-B714-AAEE312E46AD","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":"Q1177164$48B2DC3D-F844-4E29-8589-7F37C84937D7","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":"Q1177164$A663F08E-0AB3-4467-806C-085C2B2A3B40","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"84a5beb4ffbe4d8447ef8b9d68fdfb1a8b24a65e","datavalue":{"value":{"entity-type":"item","numeric-id":3677188,"id":"Q3677188"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1177164$CE7B2672-E8D6-4FE8-9DC0-9D5DFC3748CD","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":"Q1177164$B8535132-8956-4ED8-A5B9-23278F040B6D","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":"Q1177164$464FDAEA-DF14-4B12-84F0-78F36F0D887B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bce97b33fe7be9de55b855b33cfe29fa798238e2","datavalue":{"value":{"entity-type":"item","numeric-id":807029,"id":"Q807029"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1177164$80F52B6B-E6EA-4C00-9D13-68A8CE73CBD6","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":"Q1177164$356B6E84-8DFD-4288-A412-A3762D2B582D","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":"Q1177164$372DBB1B-F794-4C1B-8F78-DB606DE27199","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"1fa51f596095dda2fbb184f73a847b629c8e6b5f","datavalue":{"value":"https://doi.org/10.1016/0304-3975(91)90376-d","type":"string"},"datatype":"url"},"type":"statement","id":"Q1177164$3232E09E-8B79-41F7-A71F-8454C8457D4F","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"1d07481a1847f87b84bf411a5229a07a20799ff7","datavalue":{"value":"W1993168958","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1177164$A839558E-BC22-498E-85C1-2F2F110C57C2","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0eb9e5469a5c7d3b57691496dafbe1bf432e7c0a","datavalue":{"value":{"entity-type":"item","numeric-id":5286134,"id":"Q5286134"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3f356f3ee5f2b211073e7c1ab00d3cf052247c74","datavalue":{"value":{"amount":"+0.9093447923660278","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":"Q1177164$CDFA2E22-82EB-4E33-A072-242C7806CB14","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"de1d99612d2e16b907feb374701560beafdb375b","datavalue":{"value":{"entity-type":"item","numeric-id":4273673,"id":"Q4273673"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"08864bbe25a48cfd4b93acf332fc5668c73423f3","datavalue":{"value":{"amount":"+0.8898915648460388","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":"Q1177164$9485785D-7125-45EA-B207-9B8C302AD1D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2ea5618b3efb17e918a9bf7c74f666d60493824a","datavalue":{"value":{"entity-type":"item","numeric-id":1127541,"id":"Q1127541"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bbf2fe4918d422e958b0405db38c4c2541a215d3","datavalue":{"value":{"amount":"+0.8845950365066528","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":"Q1177164$2650925D-B51F-4741-B700-BD7E397F1369","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A complete description for a monoid of deterministic bottom-up tree transformation classes","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_complete_description_for_a_monoid_of_deterministic_bottom-up_tree_transformation_classes"}}}}}