Concepedia

Computational Complexity Of Languages

Computational Complexity of Languages is a theoretical framework within formal language theory that classifies languages based on the asymptotic resource requirements, such as time and space, of the most efficient Turing machine deciding membership in the language.

896

Publications

45.4K

Citations

1.2K

Authors

487

Institutions

Publications per year

2017–2026

70

Parents

Publications

896

Extensions of recurrent neural network language model

Tomáš Mikolov, Stefan Kombrink, Lukáš Burget et al. · 2011 · 1.6K citations

, , +12

Fiftieth volume of theoretical computer science

Maurice Nivat · Theoretical Computer Science · 1988 · 1.3K citations

, , +7

Word problems requiring exponential time(Preliminary Report)

Larry J. Stockmeyer, Albert R. Meyer · 1973 · 874 citations

, , +13

Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question

T. P. Baker, John Gill, Robert M Solovay · SIAM Journal on Computing · 1975 · 738 citations

, , +10

The mathematical theory of context-free languages

H. P. Edmundson · Information Storage and Retrieval · 1967 · 738 citations

, , +11

1–5 of 896

Authors

1.2K

  1. KS
    Kai Salomaa

    Queen's University, Canada

    17 publications · 477 citations

    14

    h-index

  2. GJ
    Galina Jirásková

    Slovak Academy of Sciences, Slovakia

    15 publications · 558 citations

    13

    h-index

  3. JB
    Janusz Brzozowski

    University of Waterloo, Canada

    11 publications · 491 citations

    11

    h-index

  4. SY
    Sheng Yü

    Western University, Canada

    10 publications · 576 citations

    10

    h-index

  5. JH
    Jack H. Lutz

    Iowa State University, United States

    10 publications · 423 citations

    10

    h-index

1–5 of 1.2K

Institutions

487

  1. University of Waterloo

    Waterloo, Canada

    17 h-index

    46 publications

    1.4K citations

  2. Queen's University

    Kingston, Canada

    14 h-index

    22 publications

    704 citations

  3. Centre National de la Recherche Scientifique

    Paris, France

    14 h-index

    24 publications

    936 citations

  4. University of Turku

    Turku, Finland

    13 h-index

    21 publications

    799 citations

  5. Cornell University

    Ithaca, United States

    13 h-index

    20 publications

    1.6K citations

  6. Mathematical Institute of the Slovak Academy of Sciences

    Bratislava, Slovakia

    12 h-index

    12 publications

    529 citations

  7. Slovak Academy of Sciences

    Bratislava, Slovakia

    12 h-index

    12 publications

    513 citations

  8. Massachusetts Institute of Technology

    Cambridge, United States

    11 h-index

    13 publications

    1.8K citations

1–8 of 487

Venues

  1. Theoretical Computer Science

    77 publications · 3.8K citations

    28

    h-index

  2. SIAM Journal on Computing

    54 publications · 5.1K citations

    28

    h-index

  3. International Journal of Foundations of Computer Science

    IJFCS · 30 publications · 1.1K citations

    18

    h-index

  4. Information and Control

    22 publications · 879 citations

    17

    h-index

  5. Journal of Computer and System Sciences

    27 publications · 1.6K citations

    17

    h-index

1–5