• DocumentCode
    2834089
  • Title

    Symmetry Coincides with Nondeterminism for Time-Bounded Auxiliary Pushdown Automata

  • Author

    Allender, Eric ; Lange, Klaus-Jörn

  • Author_Institution
    Dept. of Comput. Sci., Rutgers Univ., New Brunswick, NJ, USA
  • fYear
    2010
  • fDate
    9-12 June 2010
  • Firstpage
    172
  • Lastpage
    180
  • Abstract
    We show that every language accepted by a nondeterministic auxiliary pushdown automaton in polynomial time (that is, every language in SAC1 = Log(CFL)) can be accepted by a symmetric auxiliary pushdown automaton in polynomial time.
  • Keywords
    automata theory; computational complexity; polynomials; automata nondeterminism; nondeterministic auxiliary pushdown automaton; polynomial time; symmetric auxiliary pushdown automaton; time bounded auxiliary pushdown automata; Automata; Circuits; Complexity theory; Computational complexity; Computer science; Fasteners; Legged locomotion; Polynomials; Tree graphs; USA Councils; Auxiliary Pushdown Automata; LogCFL; Reversible Computation; Symmetric Computation;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Computational Complexity (CCC), 2010 IEEE 25th Annual Conference on
  • Conference_Location
    Cambridge, MA
  • ISSN
    1093-0159
  • Print_ISBN
    978-1-4244-7214-7
  • Electronic_ISBN
    1093-0159
  • Type

    conf

  • DOI
    10.1109/CCC.2010.24
  • Filename
    5497887
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=2834089