Concepedia

Linear Context-free Grammar

A Linear Context-Free Grammar is a context-free grammar in which each production rule has at most one nonterminal symbol on its right-hand side, thereby restricting derivations to linear structures.

43

Publications

2.2K

Citations

58

Authors

40

Institutions

Publications per year

2017–2026

1

Parents

Publications

43

On Context-Free Languages

Rohit Parikh · Journal of the ACM · 1966 · 782 citations · Full text

, , +17

Characterizing structural descriptions produced by various grammatical formalisms

K. Vijay‐Shanker, David Weir, Aravind K. Joshi · 1987 · 262 citations · Full text

, , +16

Derivation-bounded languages

Seymour Ginsburg, Edwin H. Spanier · Journal of Computer and System Sciences · 1968 · 81 citations

, , +10

A Note on Tape-Bounded Complexity Classes and Linear Context-Free languages

I. Hal Sudborough · Journal of the ACM · 1975 · 76 citations · Full text

, , +14

On the equivalence of linear conjunctive grammars and trellis automata

Alexander Okhotin · RAIRO - Theoretical Informatics and Applications · 2004 · 60 citations

, , +16

1–5 of 43

Authors

58

  1. GS
    Giorgio Satta

    University of Padua, Italy

    5 publications · 200 citations

    5

    h-index

  2. DW
    David Weir

    University of Sussex, United Kingdom

    4 publications · 355 citations

    4

    h-index

  3. MK
    Marco Kuhlmann

    Linköping University, Sweden

    3 publications · 109 citations

    3

    h-index

  4. ML
    Markus Lohrey

    Leipzig University, Germany

    2 publications · 37 citations

    2

    h-index

  5. AJ
    Artur Jeż

    University of Wrocław, Poland

    2 publications · 37 citations

    2

    h-index

1–5 of 58

Institutions

40

  1. University of Padua

    Padua, Italy

    4 h-index

    4 publications

    166 citations

  2. University of Pennsylvania

    Philadelphia, United States

    3 h-index

    6 publications

    908 citations

  3. Uppsala University

    Uppsala, Sweden

    3 h-index

    3 publications

    109 citations

  4. University of Tübingen

    Tübingen, Germany

    2 h-index

    3 publications

    69 citations

  5. Heinrich Heine University Düsseldorf

    Düsseldorf, Germany

    2 h-index

    4 publications

    43 citations

  6. Queen's University

    Kingston, Canada

    2 h-index

    2 publications

    75 citations

  7. University of Amsterdam

    Amsterdam, The Netherlands

    2 h-index

    5 publications

    140 citations

  8. University of Rochester

    Rochester, United States

    2 h-index

    2 publications

    41 citations

1–8 of 40

Venues

  1. Information and Control

    3 publications · 94 citations

    3

    h-index

  2. Theoretical Computer Science

    3 publications · 51 citations

    3

    h-index

  3. Information and Computation

    2 publications · 61 citations

    2

    h-index

  4. Journal of the ACM

    JACM · 2 publications · 858 citations

    2

    h-index

  5. International Journal of Computer Mathematics

    2 publications · 56 citations

    2

    h-index

1–5