SOME CLASSES OF LANGUAGES IN NC1

被引：1
作者：
IBARRA, OH
JIANG, T
CHANG, JH
RAVIKUMAR, B
机构：
[1] MCMASTER UNIV,DEPT COMP SCI & SYST,HAMILTON L8S 4K1,ONTARIO,CANADA
[2] SOGANG UNIV,DEPT COMP SCI,SEOUL,SOUTH KOREA
[3] UNIV RHODE ISL,DEPT COMP SCI & STAT,KINGSTON,RI 02881
来源：
INFORMATION AND COMPUTATION | 1991年 / 90卷 / 01期
基金：
美国国家科学基金会;
关键词：
D O I：
10.1016/0890-5401(91)90061-6
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
We show the containment of several classes of languages in NC1. These include the binary encodings of semilinear sets and some subclasses of context-free languages. We also investigate the closure properties of NC1. © 1991.
引用
收藏
页码：86 / 106
页数：21
相关论文
共 50 条
  • [1] Classes of Szilard Languages in NC1
    Cojocaru, Liliana
    Makinen, Erkki
    Tiplea, Ferucio Laurentiu
    11TH INTERNATIONAL SYMPOSIUM ON SYMBOLIC AND NUMERIC ALGORITHMS FOR SCIENTIFIC COMPUTING (SYNASC 2009), 2009, : 299 - 306
  • [2] ON THE RELATIVE COMPLEXITY OF SOME LANGUAGES IN NC1
    BARRINGTON, DAM
    CORBETT, J
    INFORMATION PROCESSING LETTERS, 1989, 32 (05) : 251 - 256
  • [3] On the relative complexity of some languages in NC1
    Barrington, David A.Mix
    Corbett, James
    Information Processing Letters, 1989, 32 (05): : 251 - 256
  • [4] SOME SUBCLASSES OF CONTEXT-FREE LANGUAGES IN NC1
    IBARRA, OH
    JIANG, T
    RAVIKUMAR, B
    INFORMATION PROCESSING LETTERS, 1988, 29 (03) : 111 - 117
  • [5] Arithmetizing classes around NC1 and L
    Limaye, Nutan
    Mahajan, Meena
    Rao, B. V. Raghavendra
    STACS 2007, PROCEEDINGS, 2007, 4393 : 477 - +
  • [6] Visibly Counter Languages and the Structure of NC1
    Hahn, Michael
    Krebs, Andreas
    Lange, Klaus-Joern
    Ludwig, Michael
    MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 2015, PT II, 2015, 9235 : 384 - 394
  • [7] Arithmetizing Classes Around NC1 and L
    Limaye, Nutan
    Mahajan, Meena
    Rao, B. V. Raghavendra
    THEORY OF COMPUTING SYSTEMS, 2010, 46 (03) : 499 - 522
  • [8] Counting classes and the fine structure between NC1 and L
    Datta, Samir
    Mahajan, Meena
    Rao, B. V. Raghavendra
    Thomas, Michael
    Vollmer, Heribert
    THEORETICAL COMPUTER SCIENCE, 2012, 417 : 36 - 49
  • [9] Counting Classes and the Fine Structure between NC1 and L
    Datta, Samir
    Mahajan, Meena
    Rao, B. V. Raghavendra
    Thomas, Michael
    Vollmer, Heribert
    MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 2010, 2010, 6281 : 306 - +
  • [10] AN ALGEBRA AND A LOGIC FOR NC1
    COMPTON, KJ
    LAFLAMME, C
    INFORMATION AND COMPUTATION, 1990, 87 (1-2) : 241 - 263
12345