{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:11:32Z","timestamp":1760202692888},"reference-count":11,"publisher":"World Scientific Pub Co Pte Lt","issue":"07","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2014,11]]},"abstract":"<jats:p> We investigate the descriptional complexity of nondeterministic biautomata, which are a generalization of biautomata [O. KL\u00cdMA, L. POL\u00c1K: On biautomata. RAIRO \u2014 Theor. Inf. Appl., 46(4), 2012]. Simply speaking, biautomata are finite automata reading the input from both sides; although the head movement is nondeterministic, additional requirements enforce biautomata to work deterministically. First we study the size blow-up when determinizing nondeterministic biautomata. Further, we give tight bounds on the number of states for nondeterministic biautomata accepting regular languages relative to the size of ordinary finite automata, regular expressions, and syntactic monoids. It turns out that as in the case of ordinary finite automata nondeterministic biautomata are superior to biautomata with respect to their relative succinctness in representing regular languages. <\/jats:p>","DOI":"10.1142\/s0129054114400115","type":"journal-article","created":{"date-parts":[[2015,1,14]],"date-time":"2015-01-14T08:48:03Z","timestamp":1421225283000},"page":"837-855","source":"Crossref","is-referenced-by-count":1,"title":["NONDETERMINISTIC BIAUTOMATA AND THEIR DESCRIPTIONAL COMPLEXITY"],"prefix":"10.1142","volume":"25","author":[{"given":"MARKUS","family":"HOLZER","sequence":"first","affiliation":[{"name":"Institut f\u00fcr Informatik, Universit\u00e4t Giessen Arndtstr. 2, 35392 Giessen, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"SEBASTIAN","family":"JAKOBI","sequence":"additional","affiliation":[{"name":"Institut f\u00fcr Informatik, Universit\u00e4t Giessen Arndtstr. 2, 35392 Giessen, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2015,1,14]]},"reference":[{"key":"p_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(86)90088-5"},{"key":"p_2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(92)90198-5"},{"key":"p_3","first-page":"202","author":"Champarnaud J.-M.","year":"2013","journal-title":"Spain"},{"key":"p_4","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(96)00095-6"},{"key":"p_5","doi-asserted-by":"publisher","DOI":"10.1070\/RM1961v016n05ABEH004112"},{"key":"p_6","doi-asserted-by":"publisher","DOI":"10.1137\/0209010"},{"key":"p_10","first-page":"196","author":"Jir\u00e1skov\u00e1 G.","year":"2012","journal-title":"Portugal"},{"key":"p_12","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793252092"},{"key":"p_13","first-page":"351","author":"Loukanova R.","year":"2007","journal-title":"China"},{"key":"p_14","doi-asserted-by":"publisher","DOI":"10.1109\/TEC.1960.5221603"},{"key":"p_16","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(67)80006-8"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054114400115","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T22:36:34Z","timestamp":1565130994000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054114400115"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,11]]},"references-count":11,"journal-issue":{"issue":"07","published-online":{"date-parts":[[2015,1,14]]},"published-print":{"date-parts":[[2014,11]]}},"alternative-id":["10.1142\/S0129054114400115"],"URL":"https:\/\/doi.org\/10.1142\/s0129054114400115","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,11]]}}}