• DocumentCode
    3635375
  • Title

    Classes of Szilard Languages in NC^1

  • Author

    Liliana Cojocaru;Erkki Makinen;Ferucio Laurentiu Tiplea

  • Author_Institution
    Dept. of Comput. Sci., Univ. of Tampere, Tampere, Finland
  • fYear
    2009
  • Firstpage
    299
  • Lastpage
    306
  • Abstract
    We prove that Szilard languages of context-free grammars can be accepted by an indexing alternating Turing machine (indexing ATM) in logarithmic time and space. The same result holds for leftmost Szilard languages of unrestricted (phrase-structure or type 0) grammars. Since the class of languages recognizable by an indexing ATM in logarithmic time equals the U_E-uniform NC1 class, we obtain that the above classes of Szilard languages are in NC1. The inclusions are strict, since there exist languages in NC1 that cannot be Szilard languages of any context-free or unrestricted grammar.
  • Keywords
    "Indexing","Character generation","Turing machines","Production","Digital signal processing","Scientific computing","Computer science","Upper bound","Boolean functions","Concurrent computing"
  • Publisher
    ieee
  • Conference_Titel
    Symbolic and Numeric Algorithms for Scientific Computing (SYNASC), 2009 11th International Symposium on
  • Print_ISBN
    978-1-4244-5910-0
  • Type

    conf

  • DOI
    10.1109/SYNASC.2009.58
  • Filename
    5460835