{"entities":{"Q444643":{"pageid":446410,"ns":120,"title":"Item:Q444643","lastrevid":61912128,"modified":"2026-04-11T02:29:33Z","type":"item","id":"Q444643","labels":{"en":{"language":"en","value":"On the word problem for syntactic monoids of piecewise testable languages."}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6066635"}},"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":"Q444643$A843C820-B7BA-4DCB-8BFB-0F937AF5B703","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"2befbfa2b84ab63683b3ec655a42619b4a57c649","datavalue":{"value":{"text":"On the word problem for syntactic monoids of piecewise testable languages.","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q444643$982FAA72-3E67-4FCE-88D5-A9FBAC6A9CAE","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"6d744c1a8702ecd1263f07849fae0f40eeacdd71","datavalue":{"value":"1261.20075","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q444643$5F6EA3C7-F1CB-439A-96F3-4CAE8873AA12","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"432a1b97ef03ed783932c8fa3c9e16130b7ea8f4","datavalue":{"value":{"entity-type":"item","numeric-id":444638,"id":"Q444638"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q444643$89FB67A9-33DC-4A05-9750-69F3CBEAF5D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d4dda9a3ca6b99f8dfb9dde6e55dad6b15947a38","datavalue":{"value":{"entity-type":"item","numeric-id":444639,"id":"Q444639"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q444643$77B06252-1BDB-4F39-A804-89781494288B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c8fa9669720cc37f2a7575495644eb3cf4312401","datavalue":{"value":{"entity-type":"item","numeric-id":444640,"id":"Q444640"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q444643$35AD8987-B60D-4207-ABC8-CCADB832A4F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f386c6f24c4295f5645ba7805bfa54741e34340a","datavalue":{"value":{"entity-type":"item","numeric-id":444641,"id":"Q444641"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q444643$398D59BD-83D1-4EAC-9829-5E02CC28635A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"8ff57f9a663a87e6be7e61b60860e3702b0bbf88","datavalue":{"value":{"entity-type":"item","numeric-id":444642,"id":"Q444642"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q444643$24E4F230-68B9-43C7-91FA-C2C3CF0FCCB3","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"28dbf90a09492d81530507fd711b9336815e58a3","datavalue":{"value":{"entity-type":"item","numeric-id":172569,"id":"Q172569"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q444643$D72708C6-57DB-48AE-A33A-AF2A3EA00E9A","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"0d101fdedee8fe26942f59fda6716c1df8d9aaf9","datavalue":{"value":{"time":"+2012-08-16T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q444643$11F11EB4-7610-4322-BFE4-16E59DE6F61E","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"de6ed6d4e2c8df1065f966cd58b14415a0d0194c","datavalue":{"value":"The word \\(w\\) is a \\textit{subword} of \\(u\\) if \\(w\\) is a subsequence of not necessary consecutive variables taken from \\(u\\). Given a natural number \\(k\\) let \\(u\\sim_kv\\) if and only if the words \\(u,v\\) over the alphabet \\(X\\) have the same set of subwords of length at most \\(k\\). A language \\(L\\) over the alphabet \\(X\\) is \\textit{\\(k\\)-piecewise testable} if and only if \\(L\\) is the union of classes of the equivalence relation \\(\\sim_k\\).   \\textit{I. Simon} [Lect. Notes Comput. Sci. 33, 214-222 (1975; Zbl 0316.68034)] found a basis of identities for the variety of finite monoids corresponding to a class of \\(k\\)-piecewise testable languages if \\(k=1,2\\). \\textit{F. Blanchet-Sadri} gave a basis of identities for \\(k=3\\), and proved that there is no finite basis of identities for \\(k>3\\) [see Theor. Comput. Sci. 123, No. 2, 239-258 (1994; Zbl 0801.68105)].   In this paper a normal form is presented for the varieties of finite monoids corresponding to a class of \\(k\\)-piecewise testable languages for \\(k=2,3\\) and a log-asypmtotic estimate is given for the number of words over these monoids.","type":"string"},"datatype":"string"},"type":"statement","id":"Q444643$5C5C7DAF-0160-4AD1-9498-8922C1058EF9","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"1f2d51749736d7a35abf742f9ac7394f1aeed58c","datavalue":{"value":"20M35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q444643$15909D0F-53EA-4E46-B5B6-EE6F16705B9A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e5fb4697c93e6483e0ffbb93428a373e0646b68d","datavalue":{"value":"20M07","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q444643$EF6BC3FD-C94C-47B6-BDD6-269F0B4E3AE0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"03468f1d5abafefed311cc9ccae9ddd73ff4dbd8","datavalue":{"value":"20M05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q444643$E17480C7-6513-42F9-AF27-9760E735FB76","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q444643$7F2ADEB1-D868-495E-9A48-4221A58B6A77","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"deb5f9f43f355c6575c467b17adc4a680e013b41","datavalue":{"value":"68Q70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q444643$FE0620E8-DBEA-427A-8577-7AF03AF3BF3E","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"5bdb5844861b60456ed95de28f0e94acee621895","datavalue":{"value":"6066635","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q444643$E103659D-5919-491E-8CE9-4BFB8C606DA1","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fcf2ec45b56911a8bbac4fb9d1dc61ba4b57469c","datavalue":{"value":"semigroups","type":"string"},"datatype":"string"},"type":"statement","id":"Q444643$A7133E7C-42F2-42AA-B153-10B61668A666","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a548329a944d0a891707e22cf642a25cd3a9093c","datavalue":{"value":"piecewise testable languages","type":"string"},"datatype":"string"},"type":"statement","id":"Q444643$46830717-A269-40E4-9E2F-E49B5E75A983","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"177926f7abe98d798fd5e83e609da7054498b68d","datavalue":{"value":"pseudovarieties of finite monoids","type":"string"},"datatype":"string"},"type":"statement","id":"Q444643$B5073E36-45C1-4705-9EF7-6563F199C890","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"94296e8a277f388b57874edd8d9cbd522a40de97","datavalue":{"value":"free syntactic monoids","type":"string"},"datatype":"string"},"type":"statement","id":"Q444643$51C1062E-D9DE-473B-B223-7F4DCC2FD628","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"541e14ca1a9bb27a1cfe827610ca5ddb594a16de","datavalue":{"value":"word problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q444643$8B4E798F-C898-480C-89ED-05FFC223BF89","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1c2c50d98e1e7edb4fe5350bf31e93b8679eee73","datavalue":{"value":"bases of identities","type":"string"},"datatype":"string"},"type":"statement","id":"Q444643$016ABADE-126D-44D9-8AE1-F558613C3BCB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"96fd7be9631edb45ac33ee482d312a36831c0760","datavalue":{"value":"normal form theorems","type":"string"},"datatype":"string"},"type":"statement","id":"Q444643$D767BC7A-E560-4504-AF69-31977A0A49E5","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":"Q444643$925E199A-4807-4C74-BD5A-565E468F65A4","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"5ef94e4503a9d06a3da3d553631a7a037e90ca38","datavalue":{"value":"https://doi.org/10.1007/s00233-011-9357-z","type":"string"},"datatype":"url"},"type":"statement","id":"Q444643$CDBE0735-FF2D-44B6-9456-13BBF10CC998","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"1a79f5d2aed5a962c9ece55855eb1a15350e5966","datavalue":{"value":"W2054241966","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q444643$416100FF-E7B9-42EB-9916-CEEE847D6D90","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"cb6e5904a0ed5b77aea7e01a476dc85dcdea6d80","datavalue":{"value":{"entity-type":"item","numeric-id":1823928,"id":"Q1823928"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q444643$F01B3E17-867B-4ECF-9395-B19BB75A7620","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b8a866f7b67aad930bc14601626db5bb06f4bbd0","datavalue":{"value":{"entity-type":"item","numeric-id":1314381,"id":"Q1314381"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q444643$5A4780FA-36C3-41B9-A279-8AFCE5A38816","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a08061e7c14b25092ca29749b87c860719ff533c","datavalue":{"value":{"entity-type":"item","numeric-id":3123631,"id":"Q3123631"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q444643$770334BE-E00F-4689-BAA0-0A621703AA0A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ed68160731cf55d219ba94647825683328472c30","datavalue":{"value":{"entity-type":"item","numeric-id":3769981,"id":"Q3769981"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q444643$7E1AFA0E-813F-4307-9F45-660EA8341880","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"858af5de7e93ef8dc1b75b5073ab869dd54013e3","datavalue":{"value":{"entity-type":"item","numeric-id":3740247,"id":"Q3740247"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q444643$B44FA4BF-17C3-4590-8430-682C3AC23A58","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"99c71bf5594d80706e33dcbc13841c2d147bc380","datavalue":{"value":{"entity-type":"item","numeric-id":4077455,"id":"Q4077455"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q444643$E5E5FC6B-1C0B-4436-B027-B2FBF4325E89","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c99b0d8a654acb39458337cd02e8ba470822b6ee","datavalue":{"value":"10.1007/S00233-011-9357-Z","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q444643$72FDA1CD-66A1-4E73-B9C3-51F080DF3E82","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"21ebbc4be2b72e74fe0f4827feea74cc4a286d8a","datavalue":{"value":{"entity-type":"item","numeric-id":667852,"id":"Q667852"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3d8fa1c5edfc0c70bfc6635c309414c0f1fc49ba","datavalue":{"value":{"amount":"+0.8654717206954956","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":"Q444643$A2398491-D690-4D5D-BB83-60EE445CCBF6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a0433e0638f840e913d859a13f3f005377ae276a","datavalue":{"value":{"entity-type":"item","numeric-id":4658714,"id":"Q4658714"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f61b28580835f5d35fb8b0fd9f5887204fcdd5fa","datavalue":{"value":{"amount":"+0.8282294273376465","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":"Q444643$1102F3BF-86C4-40B9-ADF5-8DF961AEE3BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"71dce300767b6e31b22d67cbeddea27640b0ee5d","datavalue":{"value":{"entity-type":"item","numeric-id":5005165,"id":"Q5005165"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9279b8ff82f476a4f9219926eefa34b4f8f4bcc6","datavalue":{"value":{"amount":"+0.8179091811180115","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":"Q444643$1CDCDFC9-5EFB-47D7-883B-07B287F0C022","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a5f441ac42c7b19367b3b7e78af32c62e6b3c39f","datavalue":{"value":{"entity-type":"item","numeric-id":3586402,"id":"Q3586402"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4c5d0b040932b0f819a58cd14e884dc70a3087d5","datavalue":{"value":{"amount":"+0.8073296546936035","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":"Q444643$B8C356A1-1B07-42F9-8CBD-1F63D44A8DE5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d8fe7ba289429eb7f48fbf17941c392005e7153a","datavalue":{"value":{"entity-type":"item","numeric-id":3533034,"id":"Q3533034"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1a0a3ef4b4d8672363f27da9f6e344bbaf9ed492","datavalue":{"value":{"amount":"+0.8052916526794434","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":"Q444643$D6B7A176-B99B-44F4-A730-B0666DF39096","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the word problem for syntactic monoids of piecewise testable languages.","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_the_word_problem_for_syntactic_monoids_of_piecewise_testable_languages."}}}}}