@article{Kapoutsis:2014aa,
    Abstract = {We strengthen a previously known connection between the size complexity of two-way finite automata () and the space complexity of Turing machines (tms). Specifically, we prove that every s-state has a poly(s)-state that agrees with it on all inputs of length ≤s if and only if NL⊆L/poly, andevery s-state has a poly(s)-state that agrees with it on all inputs of length ≤2sif and only if NLL⊆LL/polylog.Here, and are the deterministic and nondeterministic , NL and L/poly are the standard classes of languages recognizable in logarithmic space by nondeterministic tms and by deterministic tms with access to polynomially long advice, and NLL and LL/polylog are the corresponding complexity classes for space O(loglogn) and advice length poly(logn). Our arguments strengthen and extend an old theorem by Berman and Lingas and can be used to obtain variants of the above statements for other modes of computation or other combinations of bounds for the input length, the space usage, and the length of advice.},
    Author = {Kapoutsis, Christos A.},
    Date = {2014/08/01},
    File = {Two-Way Automata Versus Logarithmic Space - s00224-013-9465-0.pdf},
    ISBN = {1433-0490},
    Journal = {Theory of Computing Systems},
    Number = {2},
    Pages = {421--447},
    Title = {Two-Way Automata Versus Logarithmic Space},
    URL = {https://doi.org/10.1007/s00224-013-9465-0},
    Volume = {55},
    Year = {2014},
    bdsk-url-1 = {https://doi.org/10.1007/s00224-013-9465-0},
    date-added = {2023-01-26 11:24:02 +0100},
    date-modified = {2023-01-26 11:24:02 +0100},
    id = {Kapoutsis2014},
    doi = {10.1007/s00224-013-9465-0}
}

@article{Kapoutsis:2014aa, Abstract = {We strengthen a previously known connection between the size complexity of two-way finite automata () and the space complexity of Turing machines (tms). Specifically, we prove that every s-state has a poly(s)-state that agrees with it on all inputs of length ≤s if and only if NL⊆L/poly, andevery s-state has a poly(s)-state that agrees with it on all inputs of length ≤2sif and only if NLL⊆LL/polylog.Here, and are the deterministic and nondeterministic , NL and L/poly are the standard classes of languages recognizable in logarithmic space by nondeterministic tms and by deterministic tms with access to polynomially long advice, and NLL and LL/polylog are the corresponding complexity classes for space O(loglogn) and advice length poly(logn). Our arguments strengthen and extend an old theorem by Berman and Lingas and can be used to obtain variants of the above statements for other modes of computation or other combinations of bounds for the input length, the space usage, and the length of advice.}, Author = {Kapoutsis, Christos A.}, Date = {2014/08/01}, File = {Two-Way Automata Versus Logarithmic Space - s00224-013-9465-0.pdf}, ISBN = {1433-0490}, Journal = {Theory of Computing Systems}, Number = {2}, Pages = {421--447}, Title = {Two-Way Automata Versus Logarithmic Space}, URL = {https://doi.org/10.1007/s00224-013-9465-0}, Volume = {55}, Year = {2014}, bdsk-url-1 = {https://doi.org/10.1007/s00224-013-9465-0}, date-added = {2023-01-26 11:24:02 +0100}, date-modified = {2023-01-26 11:24:02 +0100}, id = {Kapoutsis2014}, doi = {10.1007/s00224-013-9465-0} }