{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T10:32:14Z","timestamp":1740133934113,"version":"3.37.3"},"reference-count":28,"publisher":"World Scientific Pub Co Pte Ltd","issue":"06n07","funder":[{"DOI":"10.13039\/501100000038","name":"NSERC","doi-asserted-by":"crossref","award":["OGP0147224"],"award-info":[{"award-number":["OGP0147224"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2019,9]]},"abstract":"<jats:p> To get a more comprehensive understanding of the amount of branching in computations of a nondeterministic finite automaton (NFA), we introduce and study the string path width and depth path width measures. For a given NFA, the string path width on a string [Formula: see text] counts the number of all complete computations on [Formula: see text], and the depth path width on an integer [Formula: see text] counts the number of complete computations on all strings of length [Formula: see text]. We give an algorithm to decide the finiteness of the depth path width of an NFA. Deciding finiteness of string path width can be reduced to the corresponding question on ambiguity. <\/jats:p><jats:p> An NFA is nearly acyclic if any computation can pass through at most one cycle. The class of nearly acyclic NFAs consists of exactly all NFAs with finite depth path width. Using this characterization we show that the finite depth path width of an [Formula: see text]-state NFA over a [Formula: see text]-letter alphabet is at most [Formula: see text] and that this bound is tight. The nearly acyclic NFAs recognize exactly the class of constant density regular languages. <\/jats:p>","DOI":"10.1142\/s012905411940032x","type":"journal-article","created":{"date-parts":[[2019,9,19]],"date-time":"2019-09-19T07:06:43Z","timestamp":1568876803000},"page":"1135-1155","source":"Crossref","is-referenced-by-count":0,"title":["Branching Measures and Nearly Acyclic NFAs"],"prefix":"10.1142","volume":"30","author":[{"given":"Casey","family":"Keeler","sequence":"first","affiliation":[{"name":"School of Computing, Queen\u2019s University, Kingston, Ontario K7L 2N8, Canada"}]},{"given":"Kai","family":"Salomaa","sequence":"additional","affiliation":[{"name":"School of Computing, Queen\u2019s University, Kingston, Ontario K7L 2N8, Canada"}]}],"member":"219","published-online":{"date-parts":[[2019,9,19]]},"reference":[{"key":"S012905411940032XBIB001","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2011.03.001"},{"key":"S012905411940032XBIB002","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2013.08.003"},{"key":"S012905411940032XBIB003","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(88)90012-6"},{"key":"S012905411940032XBIB004","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(86)90142-8"},{"key":"S012905411940032XBIB005","volume-title":"Introduction to Algorithms","author":"Cormen T. H.","year":"2009","edition":"3"},{"key":"S012905411940032XBIB006","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(92)90014-7"},{"key":"S012905411940032XBIB007","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(90)90053-K"},{"issue":"2","key":"S012905411940032XBIB008","first-page":"193","volume":"8","author":"Goldstine J.","year":"2002","journal-title":"Journal of Universal Comput. Sci."},{"key":"S012905411940032XBIB009","doi-asserted-by":"publisher","DOI":"10.14232\/actacyb.23.1.2017.9"},{"key":"S012905411940032XBIB010","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2010.11.013"},{"key":"S012905411940032XBIB011","doi-asserted-by":"publisher","DOI":"10.1006\/inco.2001.3069"},{"key":"S012905411940032XBIB012","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-010-9277-4"},{"key":"S012905411940032XBIB014","doi-asserted-by":"publisher","DOI":"10.1007\/BF01189856"},{"key":"S012905411940032XBIB015","doi-asserted-by":"publisher","DOI":"10.1007\/BF00263994"},{"key":"S012905411940032XBIB016","first-page":"70","volume":"111","author":"Kutrib M.","year":"2013","journal-title":"Bulletin of the EATCS"},{"key":"S012905411940032XBIB017","doi-asserted-by":"publisher","DOI":"10.1002\/spe.2309"},{"key":"S012905411940032XBIB018","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793252092"},{"first-page":"48","volume-title":"Proc. Prague Stringology Conference 2016","author":"Msiska M.","key":"S012905411940032XBIB019"},{"issue":"2","key":"S012905411940032XBIB020","first-page":"245","volume":"17","author":"Palioudakis A.","year":"2012","journal-title":"Journal of Automata, Languages and Combinatorics"},{"key":"S012905411940032XBIB021","first-page":"257","volume":"61","author":"P\u01ceun G.","year":"1995","journal-title":"Theoretical Computer Science"},{"key":"S012905411940032XBIB022","doi-asserted-by":"publisher","DOI":"10.1137\/0218083"},{"issue":"3","key":"S012905411940032XBIB023","first-page":"177","volume":"2","author":"Salomaa K.","year":"1997","journal-title":"Journal of Automata, Languages and Combinatorics"},{"key":"S012905411940032XBIB024","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1994.1076"},{"volume-title":"Second Course in Formal Languages and Automata Theory","year":"2009","author":"Shallit J.","key":"S012905411940032XBIB025"},{"key":"S012905411940032XBIB027","doi-asserted-by":"publisher","DOI":"10.1137\/0201010"},{"key":"S012905411940032XBIB028","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511756344"},{"key":"S012905411940032XBIB029","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(91)90381-B"},{"key":"S012905411940032XBIB030","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-59136-5_2"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S012905411940032X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,12,18]],"date-time":"2024-12-18T05:09:53Z","timestamp":1734498593000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/10.1142\/S012905411940032X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,9]]},"references-count":28,"journal-issue":{"issue":"06n07","published-print":{"date-parts":[[2019,9]]}},"alternative-id":["10.1142\/S012905411940032X"],"URL":"https:\/\/doi.org\/10.1142\/s012905411940032x","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"type":"print","value":"0129-0541"},{"type":"electronic","value":"1793-6373"}],"subject":[],"published":{"date-parts":[[2019,9]]}}}