Concepedia

Nondeterministic Pushdown Automata

A Nondeterministic Pushdown Automaton is a computational model that extends a finite automaton with a stack-based memory, allowing multiple possible transitions from a given state for the same input and stack symbol, thereby enabling nondeterministic behavior in recognizing context-free languages.

44

Publications

2.1K

Citations

68

Authors

48

Institutions

Publications per year

2017–2026

1

Variants

Npdas

Parents

Publications

44

Characterizations of Pushdown Machines in Terms of Time-Bounded Computers

Stephen Cook · Journal of the ACM · 1971 · 362 citations · Full text

, , +6

On context-free languages and push-down automata

M. P. Schützenberger · Information and Control · 1963 · 182 citations

, , +12

Two Applications of Inductive Counting for Complementation Problems

Allan Borodin, Stephen Cook, Patrick Dymond et al. · SIAM Journal on Computing · 1989 · 135 citations

, , +13

Properties that characterize LOGCFL

H. Venkateswaran · Journal of Computer and System Sciences · 1991 · 120 citations

, , +15

Counting auxiliary pushdown automata and semi-unbounded arithmetic circuits

Vishwa Vinay · 2002 · 113 citations

, , +16

1–5 of 44

Authors

68

  1. SC
    Stephen Cook

    University of Toronto, Canada

    3 publications · 520 citations

    3

    h-index

  2. BP
    Beatrice Palano

    University of Milan, Italy

    2 publications · 32 citations

    2

    h-index

  3. KS
    Kai Salomaa

    Queen's University, Canada

    2 publications · 83 citations

    2

    h-index

  4. PD
    Patrick Dymond

    York University, Canada

    2 publications · 158 citations

    2

    h-index

  5. SH
    Susan H. Rodger

    Duke University, United States

    2 publications · 88 citations

    2

    h-index

1–5 of 68

Institutions

48

  1. University of Milan

    Milan, Italy

    4 h-index

    6 publications

    128 citations

  2. University of Toronto

    Toronto, Canada

    3 h-index

    5 publications

    678 citations

  3. Goethe University Frankfurt

    Frankfurt am Main, Germany

    3 h-index

    3 publications

    63 citations

  4. IBM (United States)

    Armonk, United States

    3 h-index

    3 publications

    340 citations

  5. University of Pavol Jozef Šafárik

    Košice, Slovakia

    2 h-index

    4 publications

    64 citations

  6. Duke University

    Durham, United States

    2 h-index

    4 publications

    176 citations

  7. Columbia University

    New York, United States

    2 h-index

    2 publications

    57 citations

  8. Georgia Institute of Technology

    Atlanta, United States

    2 h-index

    2 publications

    150 citations

1–8 of 48

Venues

  1. Journal of Computer and System Sciences

    7 publications · 306 citations

    7

    h-index

  2. Theoretical Computer Science

    6 publications · 150 citations

    6

    h-index

  3. Information and Control

    5 publications · 473 citations

    5

    h-index

  4. SIAM Journal on Computing

    3 publications · 160 citations

    3

    h-index

  5. Journal of the ACM

    JACM · 3 publications · 392 citations

    3

    h-index

1–5