{"entities":{"Q1338899":{"pageid":1349638,"ns":120,"title":"Item:Q1338899","lastrevid":68500626,"modified":"2026-04-13T00:07:45Z","type":"item","id":"Q1338899","labels":{"en":{"language":"en","value":"Well quasi-orders and regular languages"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 695007"}},"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":"Q1338899$04B4F80C-DD48-449D-9B4B-202A185C2525","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b71fc14f1aba1e792e1324b189425d5c668ae9c3","datavalue":{"value":{"text":"Well quasi-orders and regular languages","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1338899$EE4575DF-DC17-4828-8928-52C1489D990C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"05221a9f0bec16fe11140f389d77a948ea70fd98","datavalue":{"value":"0818.68115","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1338899$2CD66724-F538-40E9-BA70-0CBD62765CB3","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"84b9a687ed55e28eded5c34a42ff46333dc3a966","datavalue":{"value":"10.1007/BF01213206","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1338899$B9C3300C-5F93-47F8-A631-703C1530C376","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"7d0f02e85530cd06ceb2c58a40dc9c2e0258e194","datavalue":{"value":{"entity-type":"item","numeric-id":161641,"id":"Q161641"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1338899$A80BBFD1-0F79-448C-BBEF-765A678F25E5","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"34092c5340d66715bee48b670526075c7ea5e1d3","datavalue":{"value":{"time":"+1994-12-18T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1338899$53C9FDB5-5FFE-4F5E-BC15-3413F58C0B50","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"87e38d8961e86ae7c0ca60b0249286e86deedd2b","datavalue":{"value":"An extension of Myhill's theorem of automata theory, due to \\textit{A. Ehrenfeucht}, \\textit{D. Haussler} and \\textit{G. Rozenberg} [Theoret. Comput. Sci., 27, 311-332 (1983; Zbl 0553.68044)] shows that a subset \\(X\\) of a semigroup \\(S\\) is recognizable if and only if \\(X\\) is closed with respect to a monotone well quasi-order on \\(S\\). In this paper we prove that a similar extension of Nerode's theorem is not possible by showing that there exist nonregular languages on a binary alphabet which are closed with respect to a right-monotone well quasi-order. We give then some additional conditions under which a set \\(X \\subseteq S\\) closed with respect to a right-monotone well quasi-order becomes recognizable. We prove the following main proposition: A subset \\(X\\) of \\(S\\) is recognizable if and only if \\(X\\) is closed with respect to two well quasi-orders \\(\\leq_ 1\\) and \\(\\leq_ 2\\) which are right-monotone and left-monotone, respectively. Some corollaries and applications are given. Moreover, we consider the family \\({\\mathcal F}\\) of all languages which are closed with respect to a right-monotone well quasi-order on a finitely generated free monoid. We prove that \\({\\mathcal F}\\) is closed under rational operations, intersection, inverse morphisms and direct non-erasing morphisms. This implies that \\({\\mathcal F}\\) is closed under faithful rational transductions. Finally we prove that the languges in \\({\\mathcal F}\\) satisfy a suitable `pumping' lemma and that \\({\\mathcal F}\\) contains languages which are not recursively enumerable.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1338899$C7BC882A-D405-40FC-B381-D2B1D61DCE87","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1338899$166E5038-BB34-45D4-BD9F-D0B39991F8FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"deb5f9f43f355c6575c467b17adc4a680e013b41","datavalue":{"value":"68Q70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1338899$5E42BCD7-CA30-408E-B0CB-FC1F0C75EA62","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"785e16bb8feed826a55f9a7c28b1df10089eab67","datavalue":{"value":"695007","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1338899$47538C73-E787-4013-B4B6-93416542955C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b1779e11f274146273217ae1a0a3dcafe93273d7","datavalue":{"value":"Myhill's theorem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1338899$F56242E8-9861-4921-97FA-EBA59DB6661D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"68c261570392928413cb911f93665f42e10898b6","datavalue":{"value":"automata theory","type":"string"},"datatype":"string"},"type":"statement","id":"Q1338899$0916A805-7B77-4760-A91F-A7DB8393901B","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"9d8417afdf52a28b84ff00c20815e85e1e4e448d","datavalue":{"value":{"entity-type":"item","numeric-id":1165590,"id":"Q1165590"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1338899$1850D2CF-9716-4959-A69E-9ED43C99CB1E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c52f17c2cd460f5ac810f2c03192e70dd7240742","datavalue":{"value":{"entity-type":"item","numeric-id":213204,"id":"Q213204"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1338899$5E5B35A5-0751-4043-B781-53DC4D0F169D","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":"Q1338899$85242654-03D2-4314-B860-930950916F20","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"0d8f09623f88efc759f6e97e0eabc50324bfb760","datavalue":{"value":{"entity-type":"item","numeric-id":3995871,"id":"Q3995871"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1338899$4DE92827-88F7-451F-9EB6-2C6B411289C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3632afaf7c9124694de853efafd5cd84e2a50881","datavalue":{"value":{"entity-type":"item","numeric-id":3859267,"id":"Q3859267"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1338899$36655EFE-5C5C-40DA-A909-78642C567AA3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a5afbf744a209bae591f2001b963f84ed85dc6a7","datavalue":{"value":{"entity-type":"item","numeric-id":3848243,"id":"Q3848243"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1338899$45EF9917-437F-4C38-B56B-F379ADD3C4FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a5426167c36bf53d870bf29cf50b30925d1c9562","datavalue":{"value":{"entity-type":"item","numeric-id":759489,"id":"Q759489"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1338899$FDFC0ACC-D086-4A5C-81AB-8BA2F67FBA25","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"36d84aa78f0d96f7d40459af01bc21793f5962fa","datavalue":{"value":{"entity-type":"item","numeric-id":4079524,"id":"Q4079524"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1338899$8447542E-EA94-46ED-8301-78DA5C04F19B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"58709679cfff7718457ae5dbfaa34a4e9b17219c","datavalue":{"value":{"entity-type":"item","numeric-id":5812263,"id":"Q5812263"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1338899$60658F0D-6D51-4639-B39C-FA32E0479427","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c57448c3511c30ed92e5fbbbe68c6f2b95237a20","datavalue":{"value":{"entity-type":"item","numeric-id":2554710,"id":"Q2554710"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1338899$00ED696D-7054-4ED5-B620-F2854256036C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4c0c4cc2cea479ba434db849cd397e58e31b51f4","datavalue":{"value":{"entity-type":"item","numeric-id":800097,"id":"Q800097"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1338899$4B2ED0E0-1BCE-4700-BE1A-F5CBE9F8D16A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fe2355482dbc37a911cde9b74ab32ffb5b6939f6","datavalue":{"value":{"entity-type":"item","numeric-id":3659988,"id":"Q3659988"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1338899$6623574A-02F7-494E-90C4-2CC21844103E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f0e41930ba9b1fd9ddcc0c32232df557efc5af58","datavalue":{"value":{"entity-type":"item","numeric-id":1177143,"id":"Q1177143"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1338899$CDBEDECE-0787-4DB7-BB10-C559C09DC0A7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7104e1508241a027c3f023b8ca095860bc9c60a5","datavalue":{"value":{"entity-type":"item","numeric-id":3686059,"id":"Q3686059"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1338899$6F9CBCF4-3545-4891-98A5-E3B8223E2981","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":"Q1338899$43E47622-1981-447A-BFA0-04301117D917","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6d53a4ae8851a3e3c503057692654d128f306d89","datavalue":{"value":{"entity-type":"item","numeric-id":1882913,"id":"Q1882913"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e040f08e1e1ae7ddea00609ab3868c92178089ef","datavalue":{"value":{"amount":"+0.8647967576980591","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":"Q1338899$ACAE5453-7F65-4B22-B647-E11A4C645561","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"05eb7d4b8dc772b637617d6058aa36ab0e8153a3","datavalue":{"value":{"entity-type":"item","numeric-id":2179340,"id":"Q2179340"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6e717c94abd169ea8aeda2dcf3b6b51e4ddd4512","datavalue":{"value":{"amount":"+0.8266958594322205","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":"Q1338899$8878388D-61D3-4F73-9438-72C14C472A21","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8818d0501105205e717bee1eb116ae4a7c76c329","datavalue":{"value":{"entity-type":"item","numeric-id":5422507,"id":"Q5422507"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"39867f15624bd3088dd7ec166b21d76a7407322d","datavalue":{"value":{"amount":"+0.8183668851852417","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":"Q1338899$6876FB24-D443-4E9D-AF1E-080258C80813","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3edd98026e0a5256be213e20d0209c0b3fe37c66","datavalue":{"value":{"entity-type":"item","numeric-id":1275465,"id":"Q1275465"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ab3f67dd0a6a06729b27679e9c94654fb3026dff","datavalue":{"value":{"amount":"+0.8148287534713745","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":"Q1338899$F058AE71-7FAA-404B-8173-3A9C4BC6C372","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"420f2d90a84e42e09ee8510bb2e2e5291c22b099","datavalue":{"value":{"entity-type":"item","numeric-id":3533001,"id":"Q3533001"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"75a3174e3b94ee859eb91a4714b1464e3e18daf0","datavalue":{"value":{"amount":"+0.8010767698287964","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":"Q1338899$23211594-6BF0-4F7B-8DEA-DC630FCB5F19","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Well quasi-orders and regular languages","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Well_quasi-orders_and_regular_languages"}}}}}