• DocumentCode
    2203687
  • Title

    Two way deterministic pushdown automaton languages and some open problems in the theory of computation

  • Author

    Galil, Zvi

  • fYear
    1974
  • fDate
    14-16 Oct. 1974
  • Firstpage
    170
  • Lastpage
    177
  • Abstract
    We consider some of the important unsolved problems in the theory of computation concerning the relationship between deterministic and nondeterministic computations, and between tape and time bounded computations. For each such problem we find an equivalent problem concerning two way deterministic pushdown automaton languages. This is the first time many of the open problems have been reduced to questions about one class of automata.
  • Keywords
    Automata; Computer science; Counting circuits; Technological innovation;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Switching and Automata Theory, 1974., IEEE Conference Record of 15th Annual Symposium on
  • Conference_Location
    USA
  • ISSN
    0272-4847
  • Type

    conf

  • DOI
    10.1109/SWAT.1974.29
  • Filename
    4569773
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=2203687