Concepedia

Complexity Of Context-free Language Problems

Complexity of Context-Free Language Problems is a theoretical framework in formal language theory that classifies decision problems associated with context-free languages according to their inherent computational difficulty, typically measured in terms of time and space complexity within the hierarchy of computational models.

134

Publications

7.7K

Citations

181

Authors

119

Institutions

Publications per year

2017–2026

3

Parents

Publications

134

Word problems requiring exponential time(Preliminary Report)

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

, , +13

The mathematical theory of context-free languages

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

, , +11

An Efficient Recognition and Syntax-Analysis Algorithm for Context-Free Languages

Tadao Kasami · IDEALS (University of Illinois Urbana-Champaign) · 1965 · 527 citations · Full text

, , +16

Groups, the Theory of ends, and context-free languages

David E. Muller, Paul E. Schupp · Journal of Computer and System Sciences · 1983 · 257 citations

, , +7

On the Tape Complexity of Deterministic Context-Free Languages

I. Hal Sudborough · Journal of the ACM · 1978 · 227 citations · Full text

, , +10

1–5 of 134

Authors

181

  1. JG
    Jozef Gruska

    Masaryk University, Czechia

    7 publications · 262 citations

    7

    h-index

  2. HB
    Harry B. Hunt

    University at Albany, State University of New York, United States

    4 publications · 96 citations

    4

    h-index

  3. WR
    Wojciech Rytter

    University of Warsaw, Poland

    4 publications · 63 citations

    4

    h-index

  4. JH
    Juris Hartmanis

    Cornell University, United States

    4 publications · 407 citations

    4

    h-index

  5. OF
    Olivier Finkel

    Centre National de la Recherche Scientifique, France

    4 publications · 150 citations

    4

    h-index

1–5 of 181

Institutions

119

  1. University of Waterloo

    Waterloo, Canada

    6 h-index

    10 publications

    289 citations

  2. University of Turku

    Turku, Finland

    5 h-index

    5 publications

    125 citations

  3. Princeton University

    Princeton, United States

    5 h-index

    10 publications

    354 citations

  4. University of Minnesota

    Minneapolis, United States

    5 h-index

    7 publications

    227 citations

  5. Centre National de la Recherche Scientifique

    Paris, France

    5 h-index

    5 publications

    195 citations

  6. University of Toronto

    Toronto, Canada

    4 h-index

    4 publications

    343 citations

  7. University of Warsaw

    Warsaw, Poland

    4 h-index

    5 publications

    73 citations

  8. Université Paris Cité

    Paris, France

    4 h-index

    4 publications

    150 citations

1–8 of 119

Venues

  1. Theoretical Computer Science

    26 publications · 963 citations

    16

    h-index

  2. Information and Control

    14 publications · 587 citations

    12

    h-index

  3. SIAM Journal on Computing

    9 publications · 608 citations

    9

    h-index

  4. Journal of Computer and System Sciences

    8 publications · 678 citations

    8

    h-index

  5. Information Processing Letters

    5 publications · 150 citations

    5

    h-index

1–5