Symmetry Coincides with Nondeterminism for Time-Bounded Auxiliary Pushdown Automata

by Eric Allender and Klaus-Jörn Lange

Theory of Computing, Volume 10(8), pp. 199-215, 2014

Bibliography with links to cited articles

[1]   Manindra Agrawal, Eric Allender, Samir Datta, Heribert Vollmer, and Klaus W. Wagner: Characterizing small depth and small space classes by operators of higher type. Chicago J. Theor. Comput. Sci., 2000(2), 2000. See also at ECCC. [doi:10.4086/cjtcs.2000.002]

[2]   Eric Allender and Klaus-Jörn Lange: RUSPACE(log n) DSPACE(log 2n∕log log n). Theory of Comput. Syst., 31(5):539–550, 1998. Preliminary version in ISAAC’96. See also at ECCC. [doi:10.1007/s002240000102]

[3]   Eric Allender and Klaus-Jörn Lange: Symmetry coincides with nondeterminism for time-bounded auxiliary pushdown automata. In Proc. 25th IEEE Conf. on Computational Complexity (CCC’10), pp. 172–180. IEEE Comp. Soc. Press, 2010. [doi:10.1109/CCC.2010.24]

[4]   Eric Allender, Klaus Reinhardt, and Shiyu Zhou: Isolation, matching, and counting: Uniform and nonuniform upper bounds. J. Comput. System Sci., 59(2):164–181, 1999. Preliminary versions in CCC’98 (also available at ECCC) and an MFCS’98 workshop (available at ECCC). [doi:10.1006/jcss.1999.1646]

[5]   Charles H. Bennett: Logical reversibility of computation. IBM J. Res. Develop., 17(6):525–532, 1973. [doi:10.1147/rd.176.0525]

[6]   Allan Borodin, Stephen A. Cook, Patrick W. Dymond, Walter L. Ruzzo, and Martin Tompa: Two applications of inductive counting for complementation problems. SIAM J. Comput., 18(3):559–578, 1989. Preliminary version in SCT’88. See erratum. [doi:10.1137/0218038]

[7]   Gerhard Buntrock, Birgit Jenner, Klaus-Jörn Lange, and Peter Rossmanith: Unambiguity and fewness for logarithmic space. In Proc. 8th Internat. Conf. Fundamentals of Computation Theory (FCT’91), volume 529, pp. 168–179. Springer, 1991. [doi:10.1007/3-540-54458-5_61]

[8]   Tanmoy Chakraborty and Samir Datta: One-input-face MPCVP is hard for L, but in LogDCFL. In Proc. Foundations of Software Technology and Theoretical Computer Science (FSTTCS’06), volume 4337 of LNCS, pp. 57–68. Springer, 2006. See also at ECCC. [doi:10.1007/11944836_8]

[9]   Stephen A. Cook: Characterizations of pushdown machines in terms of time-bounded computers. J. ACM, 18(1):4–18, 1971. Preliminary version in STOC’69. [doi:10.1145/321623.321625]

[10]   Stephen A. Cook: Deterministic CFL’s are accepted simultaneously in polynomial time and log squared space. In Proc. 11th STOC, pp. 338–345. ACM Press, 1979. [doi:10.1145/800135.804426]

[11]   Stephen A. Cook and Patrick W. Dymond: Parallel pointer machines. Comput. Complexity, 3(1):19–30, 1993. [doi:10.1007/BF01200405]

[12]   Matei David and Periklis A. Papakonstantinou: Tradeoff lower lounds for stack machines. Comput. Complexity, 23(1):99–146, 2014. Preliminary version in CCC’10. [doi:10.1007/s00037-012-0057-1]

[13]   Larry Denenberg: A note on Savitch’s theorem. Technical Report 25-81, Harvard University, 1981.

[14]   Patrick W. Dymond and Walter L. Ruzzo: Parallel RAMs with owned global memory and deterministic context-free language recognition. J. ACM, 47(1):16–45, 2000. Preliminary version in ICALP’86. [doi:10.1145/331605.331607]

[15]   Michael P. Frank and M. Josephine Ammer: Relativized separation of reversible and irreversible space-time complexity classes. Available at CiteSeerX.

[16]   Brady Garvin, Derrick Stolee, Raghunath Tewari, and N. Variyam Vinodchandran: ReachFewL = ReachUL. Comput. Complexity, 23(1):85–98, 2014. Preliminary version in COCOON’11. See also at ECCC. [doi:10.1007/s00037-012-0050-8]

[17]   Shiva Prasad Kintali: Realizable paths and the NL vs L problem. Electron. Colloq. on Comput. Complexity (ECCC), 17:158, 2010. ECCC. See also preprint at arXiv and doctoral thesis at OATD.

[18]   Tak Wah Lam and Walter L. Ruzzo: The power of parallel pointer manipulation. In Proc. 1st Ann. ACM Symp. on Parallel Algorithms and Architectures (SPAA’89), pp. 92–102. ACM Press, 1989. [doi:10.1145/72935.72946]

[19]   Klaus-Jörn Lange: Are there formal languages complete for SymSPACE(log n)? In Foundations of Computer Science: Potential - Theory - Cognition, to Wilfried Brauer on the occasion of his sixtieth birthday., pp. 125–134. Springer, 1997. [doi:10.1007/BFb0052081]

[20]   Klaus-Jörn Lange: An unambiguous class possessing a complete set. In Proc. 14th Symp. Theoretical Aspects of Comp. Sci. (STACS’97), volume 1200 of LNCS, pp. 339–350. Springer, 1997. [doi:10.1007/BFb0023471]

[21]   Klaus-Jörn Lange, Pierre McKenzie, and Alain Tapp: Reversible space equals deterministic space. J. Comput. System Sci., 60(2):354–367, 2000. Preliminary version in CCC’97. [doi:10.1006/jcss.1999.1672]

[22]   Yves Lecerf: Machines de Turing réversibles. Récursive insolubilité en n N de l’équation u = θnu, où θ est un ‘isomorphism de codes’. Comptes Rendus, 257:2597–2600, 1963. Available at Gallica.

[23]   Harry R. Lewis and Christos H. Papadimitriou: Symmetric space-bounded computation. Theoret. Comput. Sci., 19(2):161–187, 1982. Preliminary version in ICALP’80. [doi:10.1016/0304-3975(82)90058-5]

[24]   Nutan Limaye, Meena Mahajan, and Jayalal M. N. Sarma: Upper bounds for monotone planar circuit value and variants. Comput. Complexity, 18(3):377–412, 2009. Preliminary version in STACS’06. See also at ECCC. [doi:10.1007/s00037-009-0265-5]

[25]   Peter Bro Miltersen: The computational complexity of one-dimensional sandpiles. Theory Comput. Syst., 41(1):119–125, 2007. Preliminary version in CiE’05. [doi:10.1007/s00224-006-1341-8]

[26]   Omer Reingold: Undirected connectivity in log-space. J. ACM, 55(4):17:1–17:24, 2008. Preliminary version in STOC’05 See also at ECCC. [doi:10.1145/1391289.1391291]

[27]   Klaus Reinhardt and Eric Allender: Making nondeterminism unambiguous. SIAM J. Comput., 29(4):1118–1131, 2000. Preliminary version in FOCS’97. See also at ECCC. [doi:10.1137/S0097539798339041]

[28]   Peter Rossmanith: The owner concept for PRAMs. In Proc. 8th Symp. Theoretical Aspects of Comp. Sci. (STACS’91), volume 480 of LNCS, pp. 172–183. Springer, 1991. [doi:10.1007/BFb0020797]

[29]   Walter J. Savitch: Relationships between nondeterministic and deterministic tape complexities. J. Comput. System Sci., 4(2):177–192, 1970. Preliminary version in STOC’69. [doi:10.1016/S0022-0000(70)80006-X]

[30]   Ivan Hal Sudborough: On the tape complexity of deterministic context-free languages. J. ACM, 25(3):405–414, 1978. Preliminary version in STOC’76. [doi:10.1145/322077.322083]

[31]   Till Tantau: Logspace optimization problems and their approximability properties. Theory Comput. Syst., 41(2):327–350, 2007. Preliminary version in FCT’05. See also at ECCC. [doi:10.1007/s00224-007-2011-1]

[32]   H. Venkateswaran: Personal Communication. The author previously announced that an earlier version ([34]) had an incomplete proof.

[33]   H. Venkateswaran: Properties that characterize LOGCFL. J. Comput. System Sci., 43(2):380–404, 1991. Preliminary version in STOC’87. [doi:10.1016/0022-0000(91)90020-6]

[34]   H. Venkateswaran: Derandomization of probabilistic auxiliary pushdown automata classes. In Proc. 21st IEEE Conf. on Computational Complexity (CCC’06), pp. 355–370. IEEE Comp. Soc. Press, 2006. [doi:10.1109/CCC.2006.16]