{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,29]],"date-time":"2022-03-29T17:52:36Z","timestamp":1648576356723},"reference-count":9,"publisher":"World Scientific Pub Co Pte Lt","issue":"08","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2014,12]]},"abstract":"<jats:p> We study FAD-languages, which are regular languages defined by finite sets of forbidden factors, together with their \u201ccanonical\u201d recognizing automata. We are mainly interested in the possible asymptotic orders of growth for such languages. We analyze certain simplifications of sets of forbidden factors and show that they \u201calmost\u201d preserve the canonical automata. Using this result and structural properties of canonical automata, we describe an algorithm that effectively lists all canonical automata having a sink strong component isomorphic to a given digraph, or reports that no such automata exist. This algorithm can be used, in particular, to prove the existence of a FAD-language over a given alphabet with a given exponential growth rate. On the other hand, we give an example showing that the algorithm cannot prove non-existence of a FAD-language having a given growth rate. Finally, we provide some examples of canonical automata with a nontrivial condensation graph and of FAD-languages with a \u201ccomplex\u201d order of growth. <\/jats:p>","DOI":"10.1142\/s0129054114400164","type":"journal-article","created":{"date-parts":[[2015,2,25]],"date-time":"2015-02-25T06:32:14Z","timestamp":1424845934000},"page":"937-953","source":"Crossref","is-referenced-by-count":0,"title":["LANGUAGES WITH A FINITE ANTIDICTIONARY: SOME GROWTH QUESTIONS"],"prefix":"10.1142","volume":"25","author":[{"given":"ARSENY M.","family":"SHUR","sequence":"first","affiliation":[{"name":"Department of Algebra and Discrete Mathematics, Ural Federal University, pr. Lenina 51, Ekaterinburg 620083, Russia"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2015,2,24]]},"reference":[{"key":"p_1","first-page":"463","volume":"199","author":"B\u00e9al M.-P.","journal-title":"Springer-Verlag"},{"key":"p_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(98)00104-5"},{"key":"p_4","doi-asserted-by":"publisher","DOI":"10.1007\/BF01095017"},{"key":"p_6","doi-asserted-by":"crossref","first-page":"447","DOI":"10.4310\/jdg\/1214428659","volume":"2","author":"Milnor J.","year":"1968","journal-title":"J. Diff. Geom."},{"key":"p_7","doi-asserted-by":"publisher","DOI":"10.2307\/2371264"},{"key":"p_9","first-page":"190","volume":"8","author":"Sch\u00fctzenberger M. P.","year":"1965","journal-title":"Computation"},{"key":"p_11","first-page":"269","volume":"43","author":"Shur A. M.","year":"2009","journal-title":"App."},{"key":"p_12","first-page":"220","volume":"74","author":"Shur A. M.","year":"2010","journal-title":"Proc. Ural State Univ."},{"key":"p_13","doi-asserted-by":"publisher","DOI":"10.1016\/j.cosrev.2012.09.001"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054114400164","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T15:13:35Z","timestamp":1565190815000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054114400164"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,12]]},"references-count":9,"journal-issue":{"issue":"08","published-online":{"date-parts":[[2015,2,24]]},"published-print":{"date-parts":[[2014,12]]}},"alternative-id":["10.1142\/S0129054114400164"],"URL":"https:\/\/doi.org\/10.1142\/s0129054114400164","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,12]]}}}