{"entities":{"Q1575438":{"pageid":1586178,"ns":120,"title":"Item:Q1575438","lastrevid":73072884,"modified":"2026-04-14T14:23:11Z","type":"item","id":"Q1575438","labels":{"en":{"language":"en","value":"Repetitiveness of languages generated by morphisms"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1493306"}},"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":"Q1575438$516FABFB-D2DD-420A-93F2-239CC37B07F2","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"d72a5d050d50175ae5ffc77e1b13959d32032cea","datavalue":{"value":{"text":"Repetitiveness of languages generated by morphisms","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1575438$0311DC49-AD50-4286-8AB9-CF8B6E61220C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"f840df9004d4a1d7c9b31539e93e6e5a3b2090c1","datavalue":{"value":"0947.68086","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1575438$80C6A01A-0520-44CD-9722-C7427FC32217","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"d5cfa7c8c8e4c11fd943d6faddf1c5d3361b601a","datavalue":{"value":"10.1016/S0304-3975(99)00238-8","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1575438$2C40F82A-1F14-4774-A900-924A37A21C41","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":"Q1575438$E1738585-E137-4C40-ADF6-5B6F7831F598","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"b3a497233c3b9babc42d370358782cbff338a7a1","datavalue":{"value":{"time":"+2000-08-21T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1575438$837E590B-2CD5-4BB9-B0E0-0F738A464FAA","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"cd1acab77ca9122d148ab6ec688e28c366ca1d2e","datavalue":{"value":"We study the repetition of subwords in languages generated by morphisms. Fundamental to our approach is the notion of quasi-repetitive elements. Using these elements we present a new characterization for repetitive morphisms, from which we derive a simple proof for the fact that a D0L-language is repetitive if and only if it is strongly repetitive [\\textit{A. Ehrenfeucht} and \\textit{G. Rozenberg}, Inf. Control 59, 13-35 (1983; Zbl 0549.68076)]. From this proof we obtain a structurally simple polynomial-time algorithm for deciding whether such a language is repetitive. From further results on quasi-repetitive elements we obtain as a consequence a complete characterization for all those morphisms on a two-letter alphabet that are repetitive, a result which is closely related to a result of \\textit{P. S\u00e9\u00e9bold} [Bull. EATCS 36, 137-151 (1988; Zbl 0678.68072)] on the D0L periodicity problem. Finally, we characterize those morphisms f on a two-letter alphabet, for which the language L(\\(f\\)) generated by \\(f\\) or the language SL(\\(f\\)) of subwords of L(\\(f\\)) are context-free or even regular.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1575438$0781935E-5791-4032-A91E-AE8E2290E0C6","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1575438$113D69B8-7B7F-4BFA-BE4F-8114FDFAD097","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"4516ba1136f0878b1635418acd4ff214b45ca4c3","datavalue":{"value":"1493306","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1575438$AA9D36C5-ABBF-4D1A-A66A-1A04A5D38D50","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"229532fe9c6bb8eed97e3cd7b6c9b8ffd59dab8c","datavalue":{"value":"D0L-language","type":"string"},"datatype":"string"},"type":"statement","id":"Q1575438$ADC6EE4B-1022-4477-89FB-BBD32214E790","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0ff0f048f575b28ab03050f2f111e422b3722df6","datavalue":{"value":"Repetitive morphism","type":"string"},"datatype":"string"},"type":"statement","id":"Q1575438$E954D8AB-AC8D-4301-B0F8-A04E23B9CF5B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5e48a3aead922821e07b2a3c1023bb5a2828d184","datavalue":{"value":"Quasi-repetitive element","type":"string"},"datatype":"string"},"type":"statement","id":"Q1575438$EDC4E835-1F96-41F5-BEF6-FDB25322D119","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"0189ea284dbeb4d1811a67b9a764a86b15f50c48","datavalue":{"value":{"entity-type":"item","numeric-id":441852,"id":"Q441852"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1575438$7AABACE6-8D1B-4C27-870A-0B5CB7B8D698","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f46c7c00558d7121734d489049799fa24953dd04","datavalue":{"value":{"entity-type":"item","numeric-id":287428,"id":"Q287428"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1575438$076A3917-23E1-4A88-8210-1FDD34F05418","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":"Q1575438$C019B0EA-111F-49DB-870C-4EE43D5B7B68","rank":"normal"}],"P223":[{"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":"Q1575438$B2C0FDBA-345F-410F-9575-F0CF908DDE30","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8ae4e9b1f14e220740fd08a99e4c277b28a9993b","datavalue":{"value":{"entity-type":"item","numeric-id":1069710,"id":"Q1069710"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1575438$1313C908-371E-4952-B1AE-D89BB21A47B6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7d6aa4460a2edeca83ff4b0dc6813ffec5cda337","datavalue":{"value":{"entity-type":"item","numeric-id":4168093,"id":"Q4168093"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1575438$40CEA6E1-B95E-4CDE-ABF0-291800C87C0A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8420c760e4cc3ded478e52cd6144ad10165c0dbe","datavalue":{"value":{"entity-type":"item","numeric-id":1162365,"id":"Q1162365"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1575438$70E1F3D3-93D4-44E5-A97A-823B2DC504E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eb2ec57d79fbaf7df38a05ad2c5a798de7d9d8e9","datavalue":{"value":{"entity-type":"item","numeric-id":3341931,"id":"Q3341931"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1575438$9517E18C-DF44-4BCA-BE59-DADEA6421397","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"069182a9982a3ed1e6f7485b5aca74b813651aab","datavalue":{"value":{"entity-type":"item","numeric-id":799819,"id":"Q799819"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1575438$D825E419-8F93-4C23-92D3-3F59AFDE3D67","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7c96e3cfde834de2fd486837c0444243bee8e58b","datavalue":{"value":{"entity-type":"item","numeric-id":1093376,"id":"Q1093376"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1575438$8DA83FE8-5762-481B-966D-B4E7E8AB4C40","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2043397a54eaa38033021fac24881dafefacec7d","datavalue":{"value":{"entity-type":"item","numeric-id":5592246,"id":"Q5592246"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1575438$5C3935E3-6B4F-499A-84D0-926B53D4FB68","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8ab968868a27793512725f9615e172750ff9d631","datavalue":{"value":{"entity-type":"item","numeric-id":4529547,"id":"Q4529547"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1575438$C0939917-D72E-4550-95E0-12EB2793DBA4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"10cb97762def2449118704483facf4b11c9d1ca4","datavalue":{"value":{"entity-type":"item","numeric-id":4630287,"id":"Q4630287"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1575438$70BDB21D-7E2C-44E1-AA5F-DE5129EB96EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"53dd34140d96420e45c69fab96303f7b246099c0","datavalue":{"value":{"entity-type":"item","numeric-id":1184978,"id":"Q1184978"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1575438$7B8C8265-0DC1-4FE2-B36A-B4F2BDA0D801","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a9500e19069722efa256e9656f8110bdcd87d826","datavalue":{"value":{"entity-type":"item","numeric-id":4140407,"id":"Q4140407"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1575438$4FDED564-89DF-409C-929B-414680721468","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"67a6f56645ad4e91d48e12384a9f9d0bcdff231a","datavalue":{"value":{"entity-type":"item","numeric-id":4023070,"id":"Q4023070"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1575438$7984B27C-E2D0-40FD-9E37-EBBA317BEC1D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bde607297d9d3d790eeafc74d07082a473d53c98","datavalue":{"value":{"entity-type":"item","numeric-id":3835038,"id":"Q3835038"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1575438$FD593384-F24C-4BFC-A3DE-5AE637A8BCB5","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"fa6ceff23aa5fc96e1e9d7feb5fce865e3c30455","datavalue":{"value":"https://doi.org/10.1016/s0304-3975(99)00238-8","type":"string"},"datatype":"url"},"type":"statement","id":"Q1575438$97BCDE9A-0B56-472A-9D62-7CE7E9B1DAF5","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"18b8df47bc7c4b7a6732f4cb26c2ee1d447309fd","datavalue":{"value":"W2083357883","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1575438$5DACF04F-59C7-4236-8E45-4AFF40A6EA69","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0c774d85c605e8ff769e948887c7247b1d2c2b41","datavalue":{"value":{"entity-type":"item","numeric-id":4699310,"id":"Q4699310"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2c23c857b65ac060fe033dc867f51412d83ab762","datavalue":{"value":{"amount":"+0.9160426259040833","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":"Q1575438$23953C24-F452-46ED-9868-C493594B2DBA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3ff137914e4ac2e8c2d8c861cdc15496362d8c7e","datavalue":{"value":{"entity-type":"item","numeric-id":4364596,"id":"Q4364596"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"918bc8854a08deec1cbe5f6e5b8d8aba710c29c9","datavalue":{"value":{"amount":"+0.8717317581176758","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":"Q1575438$3E70DB9C-800C-4BE2-BB63-1E97CD475990","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"65b08facc72a96bca3f902aaf143046b19171171","datavalue":{"value":{"entity-type":"item","numeric-id":3341931,"id":"Q3341931"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0dbe19ca79a91a80807c6f28f0834e61b0e72dca","datavalue":{"value":{"amount":"+0.8500937819480896","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":"Q1575438$82A58616-6752-4535-B76C-C0ADAA0625D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1471f52f59c8518349ee70e922c88b77f97dbba2","datavalue":{"value":{"entity-type":"item","numeric-id":799123,"id":"Q799123"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"07ed646b28e399a9e457f88633568544355bcc0b","datavalue":{"value":{"amount":"+0.8121519088745117","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":"Q1575438$0B04EF56-B5E6-408B-8593-3160A0F51474","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Repetitiveness of languages generated by morphisms","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Repetitiveness_of_languages_generated_by_morphisms"}}}}}