{"entities":{"Q650888":{"pageid":652737,"ns":120,"title":"Item:Q650888","lastrevid":63319956,"modified":"2026-04-11T12:04:45Z","type":"item","id":"Q650888","labels":{"en":{"language":"en","value":"The word problem for \\(\\omega \\)-terms over DA"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5986988"}},"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":"Q650888$26A97E9A-4E8B-4A79-9E9D-7F2F42171DBC","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"eee6e57bad9617d0e3a874e61fe26abf0b12413f","datavalue":{"value":{"text":"The word problem for \\(\\omega \\)-terms over DA","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q650888$95FDB65C-91BA-4013-B293-D93D153827E0","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"d091ec4ed7c7cc2fc59d31e35d7498df49472799","datavalue":{"value":"1237.68117","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q650888$1D4EADE5-513B-4F96-AA22-29C3A8FF16FC","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"37ef6a0209e2fcb06be35f011033f1ff1a893440","datavalue":{"value":{"entity-type":"item","numeric-id":650887,"id":"Q650887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q650888$7498354C-A8AE-4585-AC21-CF30C93FE317","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":"Q650888$1F49268F-3351-45C8-BE96-1DD56B0DFC4B","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"e38c6f1e03c0365fe5e243370e140f97607764e2","datavalue":{"value":{"time":"+2011-12-07T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q650888$8B38323C-7ADA-453A-A8A9-7E373FD0645A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"97866a3bf03107c9b5a7cc0cb31ea09b3caaf056","datavalue":{"value":"The pseudovariety DA is the class of finite monoids whose regular \\(\\mathcal{D}\\)-classes are aperiodic semigroups. The present paper solves \\(\\omega\\)-terms over DA; this problem asks for an algorithm which decides if two given \\(\\omega\\)-terms are equal over all elements of this pseudovariety. In an earlier paper of the author [Int. J. Algebra Comput. 21, No. 5, 675--701 (2011; Zbl 1243.20070)] some representations of implicit operations over DA were given; here the representation by quasi-ternary labeled trees has been improved, which contains the infinite case consisting of wrapping the DA-trees of an implicit operation. Another representation is given by means of DA-automata, and it is proved that an \\(\\omega\\)-term has a finite representation by the minimal DA-automaton. These minimal DA-automata associated to an \\(\\omega\\)-term are computed in polynomial time.","type":"string"},"datatype":"string"},"type":"statement","id":"Q650888$1283055B-8BBF-44B4-B4BE-B427F418D444","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"4bc285a01ee2fee3db93f6df1148b69669dc8b6e","datavalue":{"value":{"entity-type":"item","numeric-id":590045,"id":"Q590045"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q650888$35755DF9-8CBD-4F8E-9A56-02717ECD741A","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q650888$CEC1BBCF-822C-4C28-BF96-91BF23E5583F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"deb5f9f43f355c6575c467b17adc4a680e013b41","datavalue":{"value":"68Q70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q650888$D39CB779-D9CB-4850-B46A-16B423ADEB87","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"03468f1d5abafefed311cc9ccae9ddd73ff4dbd8","datavalue":{"value":"20M05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q650888$28646F53-3AE6-492E-9F18-D63A945C83EF","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d2caf4a86e0573d659bb2f391e62954fbbfed604","datavalue":{"value":"5986988","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q650888$3B0AE73D-91C3-440E-A53F-8B8540FE0E20","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"013ea0ae18b29892b5726356388c7d5d42063956","datavalue":{"value":"finite monoid","type":"string"},"datatype":"string"},"type":"statement","id":"Q650888$DCB6B3E8-7E0D-4A9F-8583-EA548ABACA51","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6ae52c8f67f146f93874234c0534949dab63cc34","datavalue":{"value":"pseudovariety","type":"string"},"datatype":"string"},"type":"statement","id":"Q650888$2EF8D2C1-1184-4A2A-859F-979CE505AAD7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"541e14ca1a9bb27a1cfe827610ca5ddb594a16de","datavalue":{"value":"word problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q650888$2AEE4B92-55F6-415C-B917-C861125E860F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"97eacacca1b3d775d1bc945b0db0f3431fe81c66","datavalue":{"value":"pseudoword","type":"string"},"datatype":"string"},"type":"statement","id":"Q650888$66627C77-5A61-41CC-B571-2803C2CFD044","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bf020764596478b4a3e79bf192f9da61e332cd44","datavalue":{"value":"omega-term","type":"string"},"datatype":"string"},"type":"statement","id":"Q650888$FC708DBE-6146-46F8-94D6-5D2610824377","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"38db77d753154cd8d5f07a21f379107399a92b6b","datavalue":{"value":"aperiodic","type":"string"},"datatype":"string"},"type":"statement","id":"Q650888$AFE842D5-EBCD-4FEB-B891-6CD34BDE8498","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"af352e0cafb7ee7e73b6b4431ecaad2d0aab57d0","datavalue":{"value":"regular \\(\\mathcal{D}\\)-class","type":"string"},"datatype":"string"},"type":"statement","id":"Q650888$29C3EA70-017E-4FC7-870C-EFE3C6A12C7B","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":"Q650888$8FC15743-D9EF-406A-813D-399DD7190478","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"c528eb8f5da2217fdf0b980357757098bb120480","datavalue":{"value":"https://doi.org/10.1016/j.tcs.2011.08.003","type":"string"},"datatype":"url"},"type":"statement","id":"Q650888$B5450780-E154-411C-9D70-2436B8220B2A","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"69ebf2fefd974f0714a7dffd55f50dd9e8ea03a6","datavalue":{"value":"W1983052745","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q650888$34E3622B-1650-4C59-9905-6A356D67D07C","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"9c5b75e5917c889134d8a78729f028c28b56c294","datavalue":{"value":{"entity-type":"item","numeric-id":4848740,"id":"Q4848740"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q650888$23F2261F-2B02-4992-B687-EAE92CF35CA3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5ed496352c040c4152891195e3251999037c6cbb","datavalue":{"value":{"entity-type":"item","numeric-id":4892455,"id":"Q4892455"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q650888$A7EB0E55-7251-495D-B5B4-AE6CCE445B71","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cf981e9961fe9bb3dcffe11fabdbe5b3b271e6cf","datavalue":{"value":{"entity-type":"item","numeric-id":4407421,"id":"Q4407421"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q650888$87C2775A-154D-4F09-BF5A-A254F77E46D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"db62f718e1a12639327dc0d184957cc9a27ed9f6","datavalue":{"value":{"entity-type":"item","numeric-id":3552216,"id":"Q3552216"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q650888$28BBBB10-7878-4AC0-9658-F81940FCD732","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"990c49199a1373744910c92f84c277fb81490547","datavalue":{"value":{"entity-type":"item","numeric-id":868948,"id":"Q868948"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q650888$022C3356-7308-49D8-B256-FA35A3022580","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"906b48dd9034065477ae47c561d757f5c5062da7","datavalue":{"value":{"entity-type":"item","numeric-id":963396,"id":"Q963396"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q650888$1DFE5D15-0A0A-4074-952B-423CC1865E12","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fe955fb7f9026c48a3b74bf365e86ce77d5a2f05","datavalue":{"value":{"entity-type":"item","numeric-id":5725992,"id":"Q5725992"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q650888$89862803-82BE-4EC8-8D6F-4EA1EB59B151","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2be2ce44bdf80df52f5a97dfe72ac01ea51570a9","datavalue":{"value":{"entity-type":"item","numeric-id":4045961,"id":"Q4045961"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q650888$29228574-BFE8-40B4-8888-E35CEB3BBC19","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e606782c4d7147bd72473950f86a7ffa11efb362","datavalue":{"value":{"entity-type":"item","numeric-id":4786300,"id":"Q4786300"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q650888$E27B5D9C-5B3B-4460-A0E1-C9B78EA5AAE8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3cd18ad04423d117a41112714094587500a83fd1","datavalue":{"value":{"entity-type":"item","numeric-id":3094332,"id":"Q3094332"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q650888$9573F444-6438-4D93-B8FA-F268FB4022B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4773c285e5bc508231c7e79b59e726e8ae5dbc2d","datavalue":{"value":{"entity-type":"item","numeric-id":5569435,"id":"Q5569435"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q650888$CC12D99C-E017-471E-BC7F-367546465A56","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"337efcaa3ae20f38fff20af4d53f2602d2e9e5c4","datavalue":{"value":{"entity-type":"item","numeric-id":4407441,"id":"Q4407441"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q650888$4F4AB906-C47A-4DC5-B151-DABDE3CBDB48","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"ea362cd8d391964de8e5c4ff8eb5e799251ea84a","datavalue":{"value":"10.1016/J.TCS.2011.08.003","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q650888$494BFB7C-3737-4AD7-AD7E-28D94991FBDC","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1b180a42de41595b6b763040e9e2c09a36ecd3de","datavalue":{"value":{"entity-type":"item","numeric-id":868948,"id":"Q868948"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4694011317b3db79d5e0ab8fc927646282b83eef","datavalue":{"value":{"amount":"+0.8320679664611816","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":"Q650888$0DA3E8D7-5B07-48B0-8822-026E0177ADAC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"871bf9e6f7015f211f0dffedcac295a39c5ebd5d","datavalue":{"value":{"entity-type":"item","numeric-id":1635816,"id":"Q1635816"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9c3202f7166535b47612d9293671b8d01580dc99","datavalue":{"value":{"amount":"+0.7781018614768982","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":"Q650888$FB9ABF2B-0F06-4232-990B-8CD2F5B0515F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"adfc38bf02fdd5fa025b2b5b22ce91d678705026","datavalue":{"value":{"entity-type":"item","numeric-id":2940603,"id":"Q2940603"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"48b7d800ecf97eb316c04e57909bd1f9b9433682","datavalue":{"value":{"amount":"+0.7582491040229797","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":"Q650888$1FEDC501-6D73-4C13-A60B-CF73580801A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"16b8b7398402156ca38eb4c275b037c1d2f287f8","datavalue":{"value":{"entity-type":"item","numeric-id":5018535,"id":"Q5018535"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a27f7b39bb74966883971aa32f49bffa4c628cb6","datavalue":{"value":{"amount":"+0.7554287910461426","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":"Q650888$6985C3E8-5F42-4DD5-A0F5-EAC42F119A81","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"341b0326baff20e036722d0f78cc3e70535a50d6","datavalue":{"value":{"entity-type":"item","numeric-id":5740189,"id":"Q5740189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1d1d4ed91f3a2bce6aa19d6f47aa5dc79b4c1f33","datavalue":{"value":{"amount":"+0.738394021987915","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":"Q650888$D1E917CA-C679-49ED-B089-FEBF599E95A3","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The word problem for \\(\\omega \\)-terms over DA","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/The_word_problem_for_%5C(%5Comega_%5C)-terms_over_DA"}}}}}