, We want to show that the condition of Theorem 2(2) is satisfied. Let G be any input to 3DSTCON n. To this input G, we apply g in order to produce G unary and then run N n on G unary. This new 2afa has n O(1) states and is O(n ? )-narrow, as we expected. Thus, the desired condition holds, ) and a logspace computable function g for which, on each input M of c-branching simple 2nfa M with O(n 4 log k n) states, g outputs its equivalent O(n ? )-narrow 2afa N

E. Allender, S. Chen, T. Lou, P. A. Papakonstantinou, and B. Tang, Widthparameterized SAT: time-space tradeoffs, Theory of Computing, vol.10, pp.297-339, 2014.

G. Barnes, J. F. Buss, W. L. Ruzzo, and B. Schieber, A sublinear space, polynomial time algorithm for directed s-t connectivity, SIAM J. Comput, vol.27, pp.1273-1282, 1998.

P. Berman and A. Lingas, On complexity of regular languages in terms of finite automata, Report, vol.304, 1977.

D. Chakraborty and R. Tewari, Simulteneous time-space upper bounds for redblue path problem in planar DAGs, WALCOM 2015, vol.8973, pp.258-269, 2015.

V. Geffert, C. Mereghetti, and G. Pighizzini, Converting two-way nondeterministic automata into simpler automata, Theoret. Comput. Sci, vol.295, pp.189-203, 2003.

V. Geffert and G. Pighizzini, Two-way unary automata versus logarithmic space, Inform. Comput, vol.209, pp.1016-1025, 2011.

C. A. Kapoutsis, Minicomplexity. J. Automat. Lang. Combin, vol.17, pp.205-224, 2012.

C. A. Kapoutsis, Two-way automata versus logarithmic space, Theory Comput. Syst, vol.55, pp.421-447, 2014.

C. A. Kapoutsis and G. Pighizzini, Two-way automata characterizations of L/poly versus NL, Theory Comput. Syst, vol.56, pp.662-685, 2015.

W. J. Sakoda and M. Sipser, Nondeterminism and the size of two-way finite automata. STOC 1978, pp.275-286, 1978.

T. Yamakami, The 2CNF Boolean formula satsifiability problem and the linear space hypothesis, MFCS 2017, LIPIcs, vol.83, p.14, 2017.

T. Yamakami, Parameterized graph connectivity and polynomial-time sublinear-space short reductions (preliminary report), RP 2017, vol.10506, pp.176-191, 2017.