{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,1]],"date-time":"2022-04-01T21:13:41Z","timestamp":1648847621911},"reference-count":10,"publisher":"World Scientific Pub Co Pte Lt","issue":"01","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2012,1]]},"abstract":"<jats:p> It is known that an ordinal is the order type of the lexicographic ordering of a regular language if and only if it is less than \u03c9<jats:sup>\u03c9<\/jats:sup>. We design a polynomial time algorithm that constructs, for each well-ordered regular language L with respect to the lexicographic ordering, given by a deterministic finite automaton, the Cantor Normal Form of its order type. It follows that there is a polynomial time algorithm to decide whether two deterministic finite automata accepting well-ordered regular languages accept isomorphic languages. We also give estimates on the state complexity of the smallest \"ordinal automaton\" representing an ordinal less than \u03c9<jats:sup>\u03c9<\/jats:sup>, together with an algorithm that translates each such ordinal to an automaton. <\/jats:p>","DOI":"10.1142\/s0129054112400060","type":"journal-article","created":{"date-parts":[[2012,2,20]],"date-time":"2012-02-20T05:57:11Z","timestamp":1329717431000},"page":"87-98","source":"Crossref","is-referenced-by-count":0,"title":["ORDINAL AUTOMATA AND CANTOR NORMAL FORM"],"prefix":"10.1142","volume":"23","author":[{"given":"ZOLT\u00c1N","family":"\u00c9SIK","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Szeged, \u00c1rp\u00e1d t\u00e9r 2, Szeged, H-6720, Hungary"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2012,4,6]]},"reference":[{"key":"rf1","doi-asserted-by":"crossref","first-page":"319","DOI":"10.1051\/ita\/1978120403191","volume":"12","author":"Courcelle B.","journal-title":"RAIRO Inform. Th\u00e9or."},{"key":"rf2","doi-asserted-by":"crossref","first-page":"371","DOI":"10.1051\/ita\/1986200403711","volume":"20","author":"Thomas W.","journal-title":"RAIRO Inform. Th\u00e9or. Appl."},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2005.01.004"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2010.10.018"},{"key":"rf6","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1051\/ita\/1980140201311","volume":"14","author":"Heilbrunner S.","journal-title":"RAIRO Inform. Th\u00e9or."},{"key":"rf7","unstructured":"J. G.\u00a0Rosenstein, Linear Orderings, Pure and Applied Mathematics (Academic Press, 1982)\u00a0p. 98."},{"key":"rf10","first-page":"1","volume":"55","author":"Bloom S. L.","journal-title":"Fund. Inform."},{"key":"rf12","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-26677-0"},{"key":"rf14","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(75)90008-0"},{"key":"rf15","first-page":"121","volume":"3","author":"Downey P.","journal-title":"SIAM J. Comput."}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054112400060","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T09:30:18Z","timestamp":1565170218000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054112400060"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,1]]},"references-count":10,"journal-issue":{"issue":"01","published-online":{"date-parts":[[2012,4,6]]},"published-print":{"date-parts":[[2012,1]]}},"alternative-id":["10.1142\/S0129054112400060"],"URL":"https:\/\/doi.org\/10.1142\/s0129054112400060","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,1]]}}}