{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,1,17]],"date-time":"2023-01-17T16:31:49Z","timestamp":1673973109457},"reference-count":5,"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":[[2017,8]]},"abstract":"<jats:p> Let 2N be the class of families of problems solvable by families of two-way nondeterministic finite automata of polynomial size. We characterize 2N in terms of families of formulas of transitive-closure logic. These formulas apply the transitive-closure operator on a quantifier-free disjunctive normal form of first-order logic with successor and constants, where (i) apart from two special variables, all others are equated to constants in every clause, and (ii) no clause simultaneously relates these two special variables and refers to fixed input cells. We prove that automata with polynomially many states are as powerful as formulas with polynomially many clauses and polynomially large constants. This can be seen as a refinement of Immerman\u2019s theorem that nondeterministic logarithmic space matches positive transitive-closure logic ([Formula: see text]). <\/jats:p>","DOI":"10.1142\/s0129054117400019","type":"journal-article","created":{"date-parts":[[2017,12,15]],"date-time":"2017-12-15T03:31:43Z","timestamp":1513308703000},"page":"445-464","source":"Crossref","is-referenced-by-count":1,"title":["A Logical Characterization of Small 2NFAs"],"prefix":"10.1142","volume":"28","author":[{"given":"Christos A.","family":"Kapoutsis","sequence":"first","affiliation":[{"name":"Carnegie Mellon University in Qatar, Education City, P.O. Box 24866, Doha, Qatar"}]},{"given":"Lamana","family":"Mulaffer","sequence":"additional","affiliation":[{"name":"Texas A&amp;M University at Qatar, Education City, P.O. Box 23874, Doha, Qatar"}]}],"member":"219","published-online":{"date-parts":[[2017,12,15]]},"reference":[{"key":"S0129054117400019BIB001","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19600060105"},{"key":"S0129054117400019BIB002","series-title":"AMS-SIAM Symposia in Applied Mathematics","first-page":"43","volume-title":"Complexity of Computation","author":"Fagin R.","year":"1974"},{"key":"S0129054117400019BIB003","doi-asserted-by":"publisher","DOI":"10.1137\/0217058"},{"key":"S0129054117400019BIB004","volume-title":"Descriptive Complexity","author":"Immerman N.","year":"1998"},{"issue":"2","key":"S0129054117400019BIB005","first-page":"205","volume":"17","author":"Kapoutsis C.","year":"2012","journal-title":"Journal of Automata, Languages and Combinatorics"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054117400019","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T12:20:18Z","timestamp":1565180418000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054117400019"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,8]]},"references-count":5,"journal-issue":{"issue":"05","published-online":{"date-parts":[[2017,12,15]]},"published-print":{"date-parts":[[2017,8]]}},"alternative-id":["10.1142\/S0129054117400019"],"URL":"https:\/\/doi.org\/10.1142\/s0129054117400019","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,8]]}}}