{"entities":{"Q1082092":{"pageid":1092844,"ns":120,"title":"Item:Q1082092","lastrevid":70576497,"modified":"2026-04-13T15:33:31Z","type":"item","id":"Q1082092","labels":{"en":{"language":"en","value":"Reductions in tree replacement systems"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3972223"}},"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":"Q1082092$6C669FDE-3691-4C53-8CC4-5790B21464FA","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"7b47e930fcd8e8731044ea26ce07a08a85fd28f2","datavalue":{"value":{"text":"Reductions in tree replacement systems","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1082092$FA055340-F685-4E93-AA06-16F92FEE6699","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"1a929b4f2441f78e8f61557ac12ceff48a61c1bd","datavalue":{"value":"0602.68072","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1082092$60EE6697-C30F-413C-B4E9-1ED8F9522D2B","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"65b0d148435b15e0bdef9aa9a8f3117179b885f7","datavalue":{"value":"10.1016/0304-3975(85)90089-1","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1082092$91E64F78-DD75-4EEF-B510-9582994CE2AC","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"d25ac9b447f10c901ed8f4d14165c543498fe122","datavalue":{"value":{"entity-type":"item","numeric-id":579924,"id":"Q579924"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1082092$59221E57-D305-4756-A79A-4FD100AEEA61","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ab539a58a8a767731665253837c1bc29c4d22a7e","datavalue":{"value":{"entity-type":"item","numeric-id":593774,"id":"Q593774"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1082092$A0F3F36C-F9C5-4544-9239-139B46652E9A","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":"Q1082092$62F00E03-EE98-4E19-9CDB-3E051C84B382","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3c94df5c9af0ede578c52141befd29044de13172","datavalue":{"value":{"time":"+1985-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":"Q1082092$547E057B-C6A9-4E23-883A-9CDBCDB03FE1","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e77e1cf28762f43e81db147b69b8571966eb4e9e","datavalue":{"value":"Certain kinds of Church-Rosser tree replacement systems called ''reduction systems'' are studied. The concept of a tree rewriting system with a ''norm'' is introduced and studied. A new ''tree reducing machine'' which reduces every input tree to an irreducible tree is defined. As a consequence, when the norm under consideration is the size of the tree (the number of nodes), the word problem for finite Church-Rosser reduction systems is decidable in linear time (in the size of the input tree). Church-Rosser monadic reduction systems generalizing the monadic Thue systems of \\textit{R. V. Book} [J. Assoc. Comput. Mach. 29, 171-182 (1982; Zbl 0478.68032)] and \\textit{R. V. Book}, \\textit{M. Jantzen}, and \\textit{C. Wrathall} [Theor. Comput. Sci. 19, 231-251 (1982; Zbl 0488.03020)] are also studied. It is shown that every congruence class and every finite union of congruence classes defined by such a system is accepted by a deterministic bottom-up tree pushdown automaton. This new form of a tree automaton is briefly studied.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1082092$6A476397-7D54-4139-ABAB-FBDFC53978B3","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1082092$24055A28-537D-452B-A559-360ED35F77FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"21699a423435669f291d1bd1ba3da28fa1465b3f","datavalue":{"value":"03D03","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1082092$22245712-F96F-437B-87DA-9464C8A37721","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"0c1a11af71ef6d2cd7c16d70455a2bf2567d6c11","datavalue":{"value":"3972223","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1082092$249B6CA0-0351-4C2D-8B8E-91C331443E0A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"494293d23fd751413e5794af18fc947226c7149a","datavalue":{"value":"confluent system","type":"string"},"datatype":"string"},"type":"statement","id":"Q1082092$B983F8EB-E9B0-421E-B036-CE75A173E21F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7261974f930a2d780f2ea6cf46767415cfe0a02d","datavalue":{"value":"Noetherian system","type":"string"},"datatype":"string"},"type":"statement","id":"Q1082092$8C86AA17-3F97-4197-933E-7168FC3CBA41","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5c176184f9f6c7ad0de0928a64641237536cd188","datavalue":{"value":"normed rewriting system","type":"string"},"datatype":"string"},"type":"statement","id":"Q1082092$0CAC0149-3569-422B-8093-5BD684BE01E7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9ec07f36c72771dd844e33e30b7b13bb9fd676f3","datavalue":{"value":"Church- Rosser tree replacement systems","type":"string"},"datatype":"string"},"type":"statement","id":"Q1082092$1EB457DB-BE4E-4E53-B2C9-4FF1364B51C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ce3f7ff6a86072c50e90104de323066f50a120a1","datavalue":{"value":"reduction systems","type":"string"},"datatype":"string"},"type":"statement","id":"Q1082092$DF84FFA4-B105-4A12-B033-7C6A422AACBB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"056e92b96aeca58c4d6e42ee61da510419de636e","datavalue":{"value":"tree reducing machine","type":"string"},"datatype":"string"},"type":"statement","id":"Q1082092$B463FDE9-AC41-4EE5-BFB7-68751205DBC8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cc4ad2295c5b0bd8d0e9ea29ee4cb8ec7aa5c0a8","datavalue":{"value":"irreducible tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q1082092$7577444C-F79D-4861-85D7-C50664EB0EA7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"541e14ca1a9bb27a1cfe827610ca5ddb594a16de","datavalue":{"value":"word problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1082092$1AF0CBFC-F045-4168-BDF8-57266C3DF70E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c9e4acaa4e353e49e50ee05b5d2a6e65d906dcbe","datavalue":{"value":"congruence classes","type":"string"},"datatype":"string"},"type":"statement","id":"Q1082092$41DB31A4-8E9D-4CFC-B173-750A12DE303E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dda6124a071534150d8611fd734db7a45960ebd9","datavalue":{"value":"tree pushdown automaton","type":"string"},"datatype":"string"},"type":"statement","id":"Q1082092$AC6F78C8-2C0D-469B-A0E2-0ECE4A117B56","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":"Q1082092$4F12075A-B551-41A4-8349-162BD67E9E05","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"d1e33b7d9920407bb12c887d5de52871ba17308f","datavalue":{"value":"https://doi.org/10.1016/0304-3975(85)90089-1","type":"string"},"datatype":"url"},"type":"statement","id":"Q1082092$4E3DCAA2-D3C1-49E0-A57F-2F549F4E8F19","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"f600ac328a14322cc947a1d7aa597af25a309c52","datavalue":{"value":"W1979568806","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1082092$58BE85E5-20CD-4831-A192-163C842C969E","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"39f8caa4d24218ecf63bb6d39ed1b79a4c2266ea","datavalue":{"value":{"entity-type":"item","numeric-id":3936184,"id":"Q3936184"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1082092$629B7899-0DFA-45C4-97D1-97A12C005764","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"937911e42f68d251c82fa9be54759bda8aea4ecb","datavalue":{"value":{"entity-type":"item","numeric-id":1165842,"id":"Q1165842"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1082092$E6D65693-F43B-4783-9D7E-7DF56590C323","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6824ca0eb3ec9969eb4e49bea0fb0cfa82d8a361","datavalue":{"value":{"entity-type":"item","numeric-id":3888979,"id":"Q3888979"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1082092$EE81B2C6-3189-4EA5-89F7-90D7D4DEE759","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eb713495b9ea7313f59f292ec295ea082246771a","datavalue":{"value":{"entity-type":"item","numeric-id":1162144,"id":"Q1162144"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1082092$29E66EE2-F79C-4F79-8FA8-0C288E2DE81E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ebf9a355bba398f2dd7869850f6aa11775daec8c","datavalue":{"value":{"entity-type":"item","numeric-id":5895987,"id":"Q5895987"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1082092$113A5A07-D188-4715-AC8D-3DC9251146FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4ae9f2e8b71d939ae0323423011a38c781ecf5c0","datavalue":{"value":{"entity-type":"item","numeric-id":5556444,"id":"Q5556444"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1082092$1E352313-ED0B-4C11-BA79-060603374292","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"378088a63ec20245823db74d6a8845609e39ce21","datavalue":{"value":{"entity-type":"item","numeric-id":593789,"id":"Q593789"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1082092$EC3D51A2-F627-4DB9-8D53-51F0D357D1F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8d17eb8e40f56b25f178197677473f6105c881e4","datavalue":{"value":{"entity-type":"item","numeric-id":2544414,"id":"Q2544414"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1082092$EA32A0B9-8F6B-403F-8A1C-87CC72FF585E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1082092$67E894A2-FB54-4FCD-B759-FF9EA3FF5DF5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d34b279e5665ff3f0c5e6f8ec73982d94e9f3ec4","datavalue":{"value":{"entity-type":"item","numeric-id":3036724,"id":"Q3036724"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1082092$EB301553-0C9A-4DB8-A984-84BF20D36101","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"972bc1fa971fc360b4e9b78570fbe5c71387879c","datavalue":{"value":{"entity-type":"item","numeric-id":3939197,"id":"Q3939197"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1082092$53EE383E-B97B-4EAE-8F55-0E9D3A28A4F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"599c5dbf52817fbbe5f2f15e33a96dc6ac97514e","datavalue":{"value":{"entity-type":"item","numeric-id":3908463,"id":"Q3908463"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1082092$7E8F495A-8D75-4D9E-A732-F0F2533A8827","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a1e0b4fc54e8c62a86959e50d4b1b27d9d9a092c","datavalue":{"value":{"entity-type":"item","numeric-id":5581665,"id":"Q5581665"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1082092$D3341792-9BD2-4502-B920-DAA362B19E15","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e57dada08276bdfd975413149fdc809775588d67","datavalue":{"value":{"entity-type":"item","numeric-id":1147232,"id":"Q1147232"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1082092$B77DE1E1-240B-404C-8760-213CCEACFC8A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"224fe5205d72f8b7bf3d1117c14acd86046e588d","datavalue":{"value":{"entity-type":"item","numeric-id":2652528,"id":"Q2652528"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1082092$C7C18747-E614-4AD6-B7C6-6E88B0D01586","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3d48410a7583156d1131964150b5eab11998283a","datavalue":{"value":{"entity-type":"item","numeric-id":4105657,"id":"Q4105657"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1082092$EE127F5B-A128-4AB2-B264-9C5B78742E42","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2202ea6b7a5f8b2bf37b129e53958a44d2d21d02","datavalue":{"value":{"entity-type":"item","numeric-id":1133323,"id":"Q1133323"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1082092$0618C912-8E7D-4684-8E36-974A06A1C233","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8670a1cb5138f59a7607a06c6c33e9eef7f2c9ea","datavalue":{"value":{"entity-type":"item","numeric-id":3938536,"id":"Q3938536"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1082092$F03C5AEF-2970-40FE-8105-B65DD3E88E5F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8533cf00ebc930b9b782e1fc7f8971f87db31c20","datavalue":{"value":{"entity-type":"item","numeric-id":5684229,"id":"Q5684229"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1082092$861B5C47-D654-49AD-AB13-FFA0B14954DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6b48fcb02d6e81a5897367606519605757835a93","datavalue":{"value":{"entity-type":"item","numeric-id":5538923,"id":"Q5538923"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1082092$EC22120B-8F55-4C6A-A185-6D65678B0A8C","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7bcf9448d7033c32b4275bd4376f2d4813d887fc","datavalue":{"value":{"entity-type":"item","numeric-id":3796797,"id":"Q3796797"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fb5dba0b3c2c72fb5426e5b3004471791e8af931","datavalue":{"value":{"amount":"+0.8183910846710205","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":"Q1082092$E4BB1758-1968-4DF7-9F5B-6A285AF74062","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c0a85f4d29c76a52720883f94c305ebb8aa35245","datavalue":{"value":{"entity-type":"item","numeric-id":3588388,"id":"Q3588388"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b75e3604221adfadc066427479a24ca071fdd819","datavalue":{"value":{"amount":"+0.7958145141601562","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":"Q1082092$72AE6E58-52C1-422D-9165-B07CFC815C10","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b17d9f70f88e5b8d38a365d4297e445124bffd4f","datavalue":{"value":{"entity-type":"item","numeric-id":3166166,"id":"Q3166166"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ea63f2a1fe1da6fe3f73daf1daf6e4b6ff081e7d","datavalue":{"value":{"amount":"+0.7949119806289673","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":"Q1082092$1873B020-43E5-4013-AD8C-21D86F768EE2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"030e762ed7eaa4151216e8effc8a605e73b09bfa","datavalue":{"value":{"entity-type":"item","numeric-id":1098283,"id":"Q1098283"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"adf159a2f1b73d786b645b991de44cc029e66cde","datavalue":{"value":{"amount":"+0.7920750379562378","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":"Q1082092$298553C5-6A13-49CC-9D2E-B4CAE32200D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"543faedc79909ccf97fc246218bfa871371de0c9","datavalue":{"value":{"entity-type":"item","numeric-id":3677188,"id":"Q3677188"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8823f50613d6f17ddd7ebda1ca254b3ccd0559cf","datavalue":{"value":{"amount":"+0.7900910377502441","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":"Q1082092$61DFC7E5-2919-4CCA-8143-DE7B313F4C35","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Reductions in tree replacement systems","badges":[]}}}}}