diff 9506729..b1f9bc4 two_way_nondeterministic_complement_v2.txt
diff --git a/two_way_nondeterministic_complement_v2.txt b/two_way_nondeterministic_complement_v2.txt index 48c7f02..9d9be21 100644 --- a/two_way_nondeterministic_complement_v2.txt +++ b/two_way_nondeterministic_complement_v2.txt @@ -1179,48 +1179,4 @@ forever is accepted by neither the machine nor its swapped version. The cited construction is the standard fix. -------------------------------------------------------------------------------- -14. WHERE THE PIECES COME FROM, AND A READING LIST --------------------------------------------------------------------------------- - -Only two things above are imported from outside this file: - - - The family L_H, for nonempty words, is Sakoda and Sipser's B_h. Naming it - is a convenience; all its properties used here are proved. - - The linear-overhead complementation of 2DFAs (Geffert, Mereghetti, - Pighizzini 2007) is used only in Corollary 13.1. - -Everything else -- the diagram monoid, recurrent classes, missing sets, -transport, the chain bound, amplification, the representation lemma, the -reduction, and the arithmetic -- is proved from scratch here. - -Reading list, with why each is relevant: - - W. J. Sakoda, M. Sipser (1978), Nondeterminism and the Size of Two Way Finite - Automata, STOC '78. The liveness family B_h and the state-succinctness - question that motivates the whole problem. - - M. Y. Vardi (1989), A note on the reduction of two-way automata to one-way - automata, Information Processing Letters 30. An exponential-size one-way - nondeterministic way to COMPLEMENT a 2NFA; complementation in the same - two-way model is what we bound. - - C. Kapoutsis (2006), Small Sweeping 2NFAs Are Not Closed under Complement, - ICALP 2006. Exponential complementation cost for the restricted class of - sweeping automata. - - V. Geffert, C. Mereghetti, G. Pighizzini (2007), Complementing Two-Way Finite - Automata, Information and Computation 205. Linear-overhead deterministic - complementation, used in Corollary 13.1. - - B. Guillon, L. Prigioniero, J. Taheri (2026), Polynomial Complementation of - Nondeterministic Two-Way Finite Automata by 1-Limited Automata, STACS 2026. - A polynomial bound needs the power to rewrite each cell once on first visit; - the read-only model here has no such power. - - P. Martin, V. Mazorchuk (2013), Partitioned binary relations, Mathematica - Scandinavica 113. The monoid T_m is exactly their monoid of partitioned - binary relations, with the two signs kept as separate copies. -The exponent 127 is far from optimal. It only has to be a positive constant. -A sharper constant would replace floor((n-4)/127) by floor((n-4)/K) for some -smaller fixed K and would not change any qualitative conclusion.