{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,3]],"date-time":"2022-04-03T13:36:11Z","timestamp":1648992971741},"reference-count":23,"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":[[2020,12]]},"abstract":"<jats:p> We define a new strict and computable hierarchy for the family of automaton semigroups, which reflects the various asymptotic behaviors of the state-activity growth. This hierarchy extends that given by Sidki for automaton groups, and also gives new insights into the latter. Its exponential part coincides with a notion of entropy for some associated automata. <\/jats:p><jats:p> We prove that the Order Problem is decidable whenever the state-activity is bounded. The Order Problem remains open for the next level of this hierarchy, that is, when the state-activity is linear. Gillibert showed that it is undecidable in the whole family. <\/jats:p><jats:p> We extend the aforementioned hierarchy via a semi-norm making it more coarse but somehow more robust and we prove that the Order Problem is still decidable for the first two levels of this alternative hierarchy. <\/jats:p>","DOI":"10.1142\/s0129054120420046","type":"journal-article","created":{"date-parts":[[2021,1,7]],"date-time":"2021-01-07T14:03:41Z","timestamp":1610028221000},"page":"1069-1089","source":"Crossref","is-referenced-by-count":0,"title":["A New Hierarchy for Automaton Semigroups"],"prefix":"10.1142","volume":"31","author":[{"given":"Laurent","family":"Bartholdi","sequence":"first","affiliation":[{"name":"Institute of Advanced Studies \u2013 Collegium, Lyon and Mathematisches Institut, Georg-August-Universit\u00e4t zu G\u00f6ttingen, France"}]},{"given":"Thibault","family":"Godin","sequence":"additional","affiliation":[{"name":"IECL, UMR 7502 CNRS & Universit\u00e9 de Lorraine, France"},{"name":"IMAG, UMR 5149 CNRS & Universit\u00e9 de Montpellier, France"}]},{"given":"Ines","family":"Klimann","sequence":"additional","affiliation":[{"name":"IRIF, UMR 8243 CNRS & Universit\u00e9 Paris Diderot, France"}]},{"given":"Camille","family":"No\u00fbs","sequence":"additional","affiliation":[{"name":"Laboratoire Cogitamus, France"}]},{"given":"Matthieu","family":"Picantin","sequence":"additional","affiliation":[{"name":"IRIF, UMR 8243 CNRS & Universit\u00e9 Paris Diderot, France"}]}],"member":"219","published-online":{"date-parts":[[2021,1,6]]},"reference":[{"key":"S0129054120420046BIB001","doi-asserted-by":"publisher","DOI":"10.1142\/S021819671250052X"},{"issue":"1","key":"S0129054120420046BIB002","first-page":"3","volume":"29","author":"Antonenko A. S.","year":"2008","journal-title":"Matematychni Studii."},{"key":"S0129054120420046BIB003","series-title":"LNCS","first-page":"29","volume-title":"CSR 2016","volume":"9691","author":"Bartholdi L.","year":"2016"},{"issue":"2","key":"S0129054120420046BIB006","doi-asserted-by":"crossref","first-page":"387","DOI":"10.1016\/j.jalgebra.2004.08.040","volume":"295","author":"Bartholdi L.","year":"2006","journal-title":"J. Algebra"},{"key":"S0129054120420046BIB007","volume-title":"AutoMathA Handbook","author":"Bartholdi L.","year":"2018"},{"issue":"2","key":"S0129054120420046BIB008","doi-asserted-by":"crossref","first-page":"323","DOI":"10.4171\/GGD\/184","volume":"7","author":"Bondarenko I.","year":"2013","journal-title":"Groups Geom. Dyn."},{"issue":"2","key":"S0129054120420046BIB010","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1016\/S0019-9958(58)90082-2","volume":"1","author":"Chomsky N.","year":"1958","journal-title":"Inform. Control"},{"key":"S0129054120420046BIB011","doi-asserted-by":"crossref","first-page":"339","DOI":"10.1007\/978-3-540-85780-8_27","volume-title":"Developments in Language Theory","author":"Gawrychowski P.","year":"2008"},{"issue":"1","key":"S0129054120420046BIB012","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1142\/S0218196714500015","volume":"24","author":"Gillibert P.","year":"2014","journal-title":"Int. J. Alg. Comput."},{"key":"S0129054120420046BIB013","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1016\/j.jalgebra.2017.11.049","volume":"497","author":"Gillibert P.","year":"2018","journal-title":"J. Algebra"},{"key":"S0129054120420046BIB014","doi-asserted-by":"crossref","first-page":"24","DOI":"10.1016\/j.tcs.2017.10.005","volume":"707","author":"Godin Th.","year":"2018","journal-title":"Theor. Comput. Sci."},{"key":"S0129054120420046BIB015","series-title":"LNCS","first-page":"240","volume-title":"CIAA 2012","volume":"7381","author":"Klimann I.","year":"2012"},{"key":"S0129054120420046BIB016","doi-asserted-by":"crossref","first-page":"180","DOI":"10.1007\/978-3-642-54423-1_16","volume-title":"LATIN 2014: Theoretical Informatics \u2014 11th Latin American Symposium, Proceedings","author":"Klimann I.","year":"2014"},{"issue":"2","key":"S0129054120420046BIB017","doi-asserted-by":"crossref","first-page":"283","DOI":"10.1017\/S0143385700002443","volume":"4","author":"Lind D. A.","year":"1984","journal-title":"Ergod. Th. Dyn. Syst."},{"key":"S0129054120420046BIB018","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511626302","volume-title":"An Introduction to Symbolic Dynamics and Coding","author":"Lind D. A.","year":"1995"},{"issue":"2","key":"S0129054120420046BIB020","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1147\/rd.32.0114","volume":"3","author":"Rabin M. O.","year":"1959","journal-title":"IBM J. Res. Development"},{"key":"S0129054120420046BIB021","doi-asserted-by":"crossref","unstructured":"M. Rigo,  Words and Sequences from Scratch,  Chap. 1  (John Wiley & Sons, Ltd, 2014),  pp. 1\u201383.","DOI":"10.1002\/9781119008200.ch1"},{"key":"S0129054120420046BIB022","doi-asserted-by":"crossref","DOI":"10.1002\/9781119008989","volume-title":"Advanced Graph Theory and Combinatorics","author":"Rigo M.","year":"2016"},{"issue":"1","key":"S0129054120420046BIB023","first-page":"86","volume":"9","author":"Russyev A.","year":"2010","journal-title":"Algebra and Discr. Math."},{"key":"S0129054120420046BIB024","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9781139195218","volume-title":"Elements of Automata Theory","author":"Sakarovitch J.","year":"2009"},{"key":"S0129054120420046BIB025","series-title":"LNCS","first-page":"289","volume-title":"CSR\u201908","volume":"5010","author":"Shur A. M.","year":"2008"},{"issue":"3","key":"S0129054120420046BIB026","doi-asserted-by":"crossref","first-page":"647","DOI":"10.1051\/ita:2008021","volume":"42","author":"Shur A. M.","year":"2008","journal-title":"RAIRO-Theor. Inf. Appl."},{"issue":"1","key":"S0129054120420046BIB027","doi-asserted-by":"crossref","first-page":"1925","DOI":"10.1007\/BF02677504","volume":"100","author":"Sidki S.","year":"2000","journal-title":"J. Math. Sci."}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054120420046","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,1,21]],"date-time":"2021-01-21T03:33:58Z","timestamp":1611200038000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054120420046"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,12]]},"references-count":23,"journal-issue":{"issue":"08","published-print":{"date-parts":[[2020,12]]}},"alternative-id":["10.1142\/S0129054120420046"],"URL":"https:\/\/doi.org\/10.1142\/s0129054120420046","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,12]]}}}