{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T03:09:17Z","timestamp":1767236957833},"reference-count":18,"publisher":"World Scientific Pub Co Pte Lt","issue":"05","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2018,8]]},"abstract":"<jats:p> A nondeterministic finite automaton is unambiguous if it has at most one accepting computation on every input string. We investigate the state complexity of basic regular operations on languages represented by unambiguous finite automata. We get tight upper bounds for reversal ([Formula: see text]), intersection ([Formula: see text]), left and right quotients ([Formula: see text]), positive closure ([Formula: see text]), star ([Formula: see text]), shuffle ([Formula: see text]), and concatenation ([Formula: see text]). To prove tightness, we use a binary alphabet for intersection and left and right quotients, a ternary alphabet for star and positive closure, a five-letter alphabet for shuffle, and a seven-letter alphabet for concatenation. For complementation, we reduce the trivial upper bound [Formula: see text] to [Formula: see text]. We also get some partial results for union and square. <\/jats:p>","DOI":"10.1142\/s012905411842008x","type":"journal-article","created":{"date-parts":[[2018,8,21]],"date-time":"2018-08-21T10:47:08Z","timestamp":1534848428000},"page":"861-876","source":"Crossref","is-referenced-by-count":12,"title":["Operations on Unambiguous Finite Automata"],"prefix":"10.1142","volume":"29","author":[{"suffix":"Jr.","given":"Jozef","family":"Jir\u00e1sek","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Saskatchewan, Saskatoon, SK S7N 5A9, Canada"}]},{"given":"Galina","family":"Jir\u00e1skov\u00e1","sequence":"additional","affiliation":[{"name":"Mathematical Institute, Slovak Academy of Sciences, Gre\u0161\u00e1kova 6, 040 01 Ko\u0161ice, Slovakia"}]},{"given":"Juraj","family":"\u0160ebej","sequence":"additional","affiliation":[{"name":"Institute of Computer Science, Faculty of Science, P. J. \u0160af\u00e1rik University, Jesenn\u00e1 5, 040 01 Ko\u0161ice, Slovakia"}]}],"member":"219","published-online":{"date-parts":[[2018,8,21]]},"reference":[{"key":"S012905411842008XBIB001","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(92)90198-5"},{"key":"S012905411842008XBIB002","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(93)90160-U"},{"issue":"3","key":"S012905411842008XBIB003","first-page":"303","volume":"7","author":"C\u00e2mpeanu C.","year":"2002","journal-title":"J. Autom. Lang. Comb."},{"key":"S012905411842008XBIB005","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(88)90012-6"},{"key":"S012905411842008XBIB008","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(96)00095-6"},{"key":"S012905411842008XBIB009","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054103002199"},{"key":"S012905411842008XBIB011","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-010-9277-4"},{"key":"S012905411842008XBIB012","doi-asserted-by":"publisher","DOI":"10.1006\/inco.2001.3069"},{"key":"S012905411842008XBIB014","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.04.011"},{"key":"S012905411842008XBIB015","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(81)80005-9"},{"key":"S012905411842008XBIB016","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793252092"},{"key":"S012905411842008XBIB017","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054105003418"},{"key":"S012905411842008XBIB019","first-page":"1373","volume":"11","author":"Maslov A. N.","year":"1970","journal-title":"Soviet Math. Doklady"},{"key":"S012905411842008XBIB020","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2012.01.003"},{"key":"S012905411842008XBIB021","doi-asserted-by":"publisher","DOI":"10.1137\/0218083"},{"key":"S012905411842008XBIB023","doi-asserted-by":"publisher","DOI":"10.1137\/0214044"},{"key":"S012905411842008XBIB024","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(91)90381-B"},{"key":"S012905411842008XBIB025","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(92)00011-F"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S012905411842008X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T12:58:24Z","timestamp":1565182704000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S012905411842008X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,8]]},"references-count":18,"journal-issue":{"issue":"05","published-online":{"date-parts":[[2018,8,21]]},"published-print":{"date-parts":[[2018,8]]}},"alternative-id":["10.1142\/S012905411842008X"],"URL":"https:\/\/doi.org\/10.1142\/s012905411842008x","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,8]]}}}