rdf-syntax-grammar
mods:
  schema location: http://www.loc.gov/mods/v3 http://www.loc.gov/standards/mods/v3/mods-3-2.xsd
  title info:
    title: On input read-modes of alternating Turing machines
  name:
    name part: Cai, Liming.
    role:
      role term: creator
  name:
    name part: Chen, Jianer.
  type of resource: text
  genre: bibliography
  origin info:
    place:
      place term: txu
    date issued: 1993
    issuance: monographic
  language:
    language term: eng
  physical description:
    form: print
    extent: 27 leaves : illustrations ; 28 cm.
  abstract: Abstract: "A number of input read-modes of Turing machines have appeared in the literature. To investigate the differences among these input read-modes, we study log-time alternating Turing machines of constant alternations. For each fixed integer k [> or =] 1 and for each read-mode, a precise circuit characterization is established for log-time alternating Turing machines of k alternations, which is a nontrivial refinement of Ruzzo's circuit characterization of alternating Turing machines. These circuit characterizations indicate clearly the differences among the input read-modes. Complete languages in strong sense for each level of the log- time hierarchy are presented, refining a result by Buss. An application of these results to computational optimization problems is described."
  note: Liming Cai and Jianer Chen.
  note: "September 29, 1993."
  note: Includes bibliographical references.
  note: Supported in part by an Engineering Excellence Award from Texas A&M University
  note: Supported in part by the National Science Foundation. CCR- 9110824
  subject:
    topic: Turing machines
  related item:
    title info:
      title: Technical report (Texas A & M University. Computer Science Department) ; 93-046
  record info:
    record content source: PMC
    record creation date: 941103
    record change date: 20151003083213.0
    record identifier: in00001246798