{"entities":{"Q685700":{"pageid":687549,"ns":120,"title":"Item:Q685700","lastrevid":63462375,"modified":"2026-04-11T13:20:01Z","type":"item","id":"Q685700","labels":{"en":{"language":"en","value":"Another variation on the common subexpression problem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 423588"}},"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":"Q685700$B44FD096-CDE4-4695-B1CA-30A61738CA10","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"f08e82a9709edfd311813a6379b283c680ea5b33","datavalue":{"value":{"text":"Another variation on the common subexpression problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q685700$1A7222D9-E0A3-4031-9C83-0FD8AFDD8BCA","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"1079e59b2475f1fd5394b26f772299ea9b8e9dab","datavalue":{"value":"0787.68071","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685700$770F15AD-0AB1-42F9-93DE-BE69C4BB99C0","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"bcb7f0afbc358ac99cfe48a8096b9a8100a8df22","datavalue":{"value":"10.1016/0012-365X(93)90379-8","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685700$3E8982E2-3F04-4F0D-9B8C-8114637F131E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"5392602cebfb387ee7516fe8118e538d44d0b430","datavalue":{"value":{"entity-type":"item","numeric-id":221594,"id":"Q221594"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685700$AACC06CF-F195-40B6-ACF0-C5C3FBE75052","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"3527a91821d36e757e1613c0da59458b564b0344","datavalue":{"value":{"entity-type":"item","numeric-id":225062,"id":"Q225062"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685700$826776A0-4A82-4471-A6AD-0B687C66C0C2","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":"Q685700$43CCDA0C-958C-4C0E-96CC-AA76E8065219","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"1a4582cf37b19337c7eae16fd67b6e107844c9e6","datavalue":{"value":{"time":"+1993-10-24T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q685700$11812EC7-57A3-4941-8300-EC2F5437D014","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"c65de0273f2ecb1dadf5c9df475a5cef3b3cbf68","datavalue":{"value":"An algorithm for deciding the equivalence of two deterministic finite ascending (frontier-to-root) tree automata is presented and analyzed. The algorithm constructs a Nerode equivalence on the disjoint union of the state sets of the two automata by means of special test sets of `pointed trees'. For binary trees with a fixed alphabet the algorithm is shown to perform in time \\({\\mathcal O}(n^ 2)\\), where \\(n\\) is the total number of states. Since this is also the order of the input size, it can be deduced that the complexity of the equivalence problem is linear in the input alphabet and \\({\\mathcal O}(n^ 2)\\) in the number of states. For general ranked alphabets with maximal rank \\(k\\), the complexity is shown to be \\({\\mathcal O}(n^ k)\\). The case of incomplete automata with sparse transition tables is also analysed. Finally, the parallel complexity of the problem is considered and it is shown to be logspace-complete for \\(P\\). In the introduction the authors point out that the present problem is closely related to some other problems, the common subexpression problem, for example.","type":"string"},"datatype":"string"},"type":"statement","id":"Q685700$8FD8A2F3-9D63-4B02-9968-BDCCD471DC9D","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":"Q685700$8A6F0776-14F0-4805-B72C-62B963921217","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685700$3AC2DEA5-E9A4-4AB1-A40F-6E883CED5533","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1de3565cfd3393000dd87ca545f95ff84d4c1446","datavalue":{"value":"68W10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685700$930A0478-A364-438B-869B-70AF9F75E50B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685700$F62FCCDC-6F28-4507-9C34-B8B643454C39","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"23149673dde05813672617e26c3fcb130092997c","datavalue":{"value":"68R15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685700$533B83D6-4A52-4E67-84C0-A59324C7A222","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"822947342a2b28d0dd9d1e666bb58f6907417ac6","datavalue":{"value":"423588","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685700$80E488CA-9F82-480A-A03A-083031F17FAE","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a7fe2f2415709197ca17d2732570ef76c1e4f0b0","datavalue":{"value":"tree automata","type":"string"},"datatype":"string"},"type":"statement","id":"Q685700$15A300EA-78BE-4784-A241-BDACA5CDEED9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5e167344edd0ee738a6a356189c1a3e1f5de5a00","datavalue":{"value":"Nerode equivalence","type":"string"},"datatype":"string"},"type":"statement","id":"Q685700$1E937E29-4886-4F40-92CD-B59BCAA69CDB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a63f5fdf3038af45049408a9914d671beb783a5b","datavalue":{"value":"parallel complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q685700$20A66A56-B3A4-42CA-AADA-4BF806981AB1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6ce47ccb519fc1a0d95e68f6ff1eb5d598658211","datavalue":{"value":"common subexpression problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q685700$25C2C397-B668-457E-81AF-58646E1F04D0","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":"Q685700$7FE6ED8C-D6DE-4263-960E-176E3EC90D14","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"340ea97c0f2f383d364057042ebc9f9438fcc85a","datavalue":{"value":{"entity-type":"item","numeric-id":4091421,"id":"Q4091421"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685700$B178D858-2E51-480E-92DF-99272E8AAF95","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"400f20ecf79d81a3d3b5792afa45f1f4a9cee7d2","datavalue":{"value":{"entity-type":"item","numeric-id":1093359,"id":"Q1093359"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685700$C30897BF-D0E4-4D79-B5BF-0F8A42FB518D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"372d4f122419147bead9900706bf72cc04a0bdd8","datavalue":{"value":{"entity-type":"item","numeric-id":5570935,"id":"Q5570935"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685700$D798C2DD-46C9-430C-90BF-FF510A311680","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":"Q685700$2EF0AF5B-594A-4199-981C-513E1B945810","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e81d57b58abc3a82b100d072439fecb147f7ea86","datavalue":{"value":{"entity-type":"item","numeric-id":3716320,"id":"Q3716320"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685700$AE501307-5B47-4159-BA56-2D0F3CB32248","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0079b0c7d694a397659be503d6216c85129b1bb1","datavalue":{"value":{"entity-type":"item","numeric-id":3323279,"id":"Q3323279"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685700$A24DE391-7880-4DB1-8923-589316699447","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c9843845d878a00ba9e2b944abf98503a9652179","datavalue":{"value":{"entity-type":"item","numeric-id":1124338,"id":"Q1124338"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685700$6D7437A4-358E-4BEC-B3D7-B0BC5EF19269","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"975126c2667d6964e52988e556bf8223ff836bfd","datavalue":{"value":{"entity-type":"item","numeric-id":3883564,"id":"Q3883564"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685700$59271759-F3E8-469E-A0F8-6A8719D12E20","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":"Q685700$C9EBFE5B-0CEB-4AEF-B7BD-4DB45C2BC3AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"932383d1ac997ed208ef47dcb574b592efaf75b3","datavalue":{"value":{"entity-type":"item","numeric-id":4065031,"id":"Q4065031"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685700$633D0C7C-E5DA-483F-A951-A0D85B464FC8","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":"Q685700$E210211D-2249-4267-B20B-71E164EA595F","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7d87cdfd11f0eabca02afe81bb5a18c3cc1d117d","datavalue":{"value":{"entity-type":"item","numeric-id":5096180,"id":"Q5096180"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9bd694bf62657a4dc8b37468d1c8ae8d81eb18b7","datavalue":{"value":{"amount":"+0.8125061392784119","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":"Q685700$D45F9F0A-B3F5-4F7C-B283-2B31762163CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"caf0e5ebc5d3d72bd55beb148c254b4ba13c614b","datavalue":{"value":{"entity-type":"item","numeric-id":3477969,"id":"Q3477969"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"efff8a831bfb3715add20ab03743333c7573438a","datavalue":{"value":{"amount":"+0.8089906573295593","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":"Q685700$C00BFA00-CFD6-4A3F-8B4B-78291E1CEFCF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ab8f0a7846eefd683c1b477943a2cb8a17a0b29e","datavalue":{"value":{"entity-type":"item","numeric-id":1060562,"id":"Q1060562"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e6342eeb3fc0e5393e76df16f1de66cf2e142c94","datavalue":{"value":{"amount":"+0.7727422118186951","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":"Q685700$E21B33E9-A836-4A0C-A1CB-C91FD58203DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"78ec730c3e7192fc99980e9fc56f77afe052c540","datavalue":{"value":{"entity-type":"item","numeric-id":4963261,"id":"Q4963261"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b023d187d37b892d6638feb219ecbb5c6d553494","datavalue":{"value":{"amount":"+0.7674405574798584","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":"Q685700$A11C4758-3B36-42C8-97B8-EA6F7799DEE6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4d44f6f77cc38395cf2f4b7194d649c296e21c40","datavalue":{"value":{"entity-type":"item","numeric-id":5175903,"id":"Q5175903"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"323efdc07ac5443b59a0c134d41f1e2a55cd2497","datavalue":{"value":{"amount":"+0.7600541114807129","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":"Q685700$CFBD7643-0CE6-4965-A512-CC2666A2905E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Another variation on the common subexpression problem","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Another_variation_on_the_common_subexpression_problem"}}}}}