{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,12,20]],"date-time":"2023-12-20T16:26:04Z","timestamp":1703089564993},"reference-count":18,"publisher":"World Scientific Pub Co Pte Lt","issue":"03","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2006,6]]},"abstract":"<jats:p>A word w over a finite alphabet \u03a3 is n-collapsing if for an arbitrary DFA [Formula: see text], the inequality |\u03b4(Q, w)| \u2264 |Q| - n holds provided that |\u03b4(Q, u)| \u2264 |Q| - n for some word u \u2208 \u03a3<jats:sup>+<\/jats:sup>(depending on [Formula: see text]). We overview some recent results related to this notion. One of these results implies that the property of being n-collapsing is algorithmically recognizable for any given positive integer n.<\/jats:p>","DOI":"10.1142\/s0129054106003966","type":"journal-article","created":{"date-parts":[[2006,6,6]],"date-time":"2006-06-06T11:11:37Z","timestamp":1149592297000},"page":"507-518","source":"Crossref","is-referenced-by-count":4,"title":["COLLAPSING WORDS: A PROGRESS REPORT"],"prefix":"10.1142","volume":"17","author":[{"given":"D. S.","family":"ANANICHEV","sequence":"first","affiliation":[{"name":"Department of Mathematics and Mechanics, Ural State University, 620083 Ekaterinburg, Russia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"I. V.","family":"PETROV","sequence":"additional","affiliation":[{"name":"Department of Mathematics and Mechanics, Ural State University, 620083 Ekaterinburg, Russia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"M. V.","family":"VOLKOV","sequence":"additional","affiliation":[{"name":"Department of Mathematics and Mechanics, Ural State University, 620083 Ekaterinburg, Russia"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1142\/S0219498803000519"},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(03)00093-8"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45005-X_23"},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-46011-X_13"},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539798345944"},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1007\/s00012-004-1895-8"},{"key":"rf9","first-page":"208","volume":"14","author":"\u010cern\u00fd J.","journal-title":"Mat.-Fyz. Cas. Slovensk. Akad. Vied."},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1016\/S0195-6698(82)80025-5"},{"key":"rf13","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054104002406"},{"key":"rf14","doi-asserted-by":"crossref","unstructured":"A.\u00a0Mateesku and A.\u00a0Salomaa, Handbook of Formal Languages, Vol. I. Word. Language, Grammar, eds. G.\u00a0Rozenberg and A.\u00a0Salomaa (Springer-Verlag, Berlin-Heidelberg-New York, 1997)\u00a0pp. 175\u2013251.","DOI":"10.1007\/978-3-642-59136-5_4"},{"key":"rf15","doi-asserted-by":"crossref","unstructured":"E.\u00a0Moore, Automata Studies, Ann. Math. Studies\u00a034, eds. C. E.\u00a0Shannon and J.\u00a0McCarthy (Princeton Univ. Press, Princeton, N.J., 1956)\u00a0pp. 129\u2013153.","DOI":"10.1515\/9781400882618-006"},{"key":"rf16","unstructured":"J.E.\u00a0Pin, Actes du ler Colloque AFCET-SMF de Math\u00e9matiques Appliqu\u00e9es (AFCET, 1978)\u00a0pp. 85\u201392."},{"key":"rf17","first-page":"535","volume":"17","author":"Pin J.-E.","journal-title":"Ann. Discrete Math."},{"key":"rf18","doi-asserted-by":"publisher","DOI":"10.1007\/BF01236507"},{"key":"rf20","doi-asserted-by":"publisher","DOI":"10.1007\/s000120050183"},{"key":"rf21","first-page":"171","volume":"31","author":"Sauer N.","journal-title":"Ars Combinatoria"},{"key":"rf22","doi-asserted-by":"publisher","DOI":"10.1142\/S0218196705002293"},{"key":"rf23","doi-asserted-by":"publisher","DOI":"10.1007\/BF01459084"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054106003966","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,15]],"date-time":"2020-04-15T07:34:18Z","timestamp":1586936058000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054106003966"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,6]]},"references-count":18,"journal-issue":{"issue":"03","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2006,6]]}},"alternative-id":["10.1142\/S0129054106003966"],"URL":"https:\/\/doi.org\/10.1142\/s0129054106003966","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,6]]}}}