Concepedia

Pebble Games

Pebble Games is a formal logical game in descriptive complexity theory that serves as a method for comparing the expressive power of logical languages by modeling the interaction between two players who place and move pebbles to represent variables in finite structures, distinguished by its use of a bounded number of pebbles to capture resource-constrained definability.

85

Publications

4.7K

Citations

137

Authors

77

Institutions

Publications per year

2017–2026

15

Parents

Publications

85

I/O complexity

Jiawei Hong, H. T. Kung · 1981 · 450 citations

, , +17

An Algorithm for Two-Dimensional Rigidity Percolation: The Pebble Game

Donald J. Jacobs, Bruce Hendrickson · Journal of Computational Physics · 1997 · 402 citations

, , +8

Coordinating Pebble Motion On Graphs, The Diameter Of Permutation Groups, And Applications

Daniel Kornhauser, Gary L. Miller, Paul G. Spirakis · 1984 · 285 citations · Full text

, , +11

Pebble game algorithms and sparse graphs

Audrey Lee, Ileana Streinu · Discrete Mathematics · 2007 · 223 citations

, , +14

Generic rigidity percolation in two dimensions

Donald J. Jacobs, M. F. Thorpe · Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topics · 1996 · 218 citations

, , +14

1–5 of 85

Authors

137

  1. IS
    Ileana Streinu

    Smith College, United States

    7 publications · 359 citations

    7

    h-index

  2. RE
    Robert E. Tarjan

    Princeton University, United States

    6 publications · 380 citations

    6

    h-index

  3. AL
    Audrey Lee

    University of Massachusetts Amherst, United States

    5 publications · 309 citations

    5

    h-index

  4. DJ
    Donald J. Jacobs

    University of North Carolina at Charlotte, United States

    4 publications · 701 citations

    4

    h-index

  5. PG
    Phokion G. Kolaitis

    University of California, Santa Cruz, United States

    4 publications · 359 citations

    4

    h-index

1–5 of 137

Institutions

77

  1. University of Massachusetts Amherst

    Amherst Center, United States

    7 h-index

    11 publications

    544 citations

  2. Stanford University

    Stanford, United States

    6 h-index

    10 publications

    743 citations

  3. Smith College

    Northampton, United States

    5 h-index

    5 publications

    333 citations

  4. University of California, Santa Cruz

    Santa Cruz, United States

    4 h-index

    4 publications

    359 citations

  5. University of Cambridge

    Cambridge, United Kingdom

    3 h-index

    5 publications

    105 citations

  6. Bielefeld University

    Bielefeld, Germany

    3 h-index

    3 publications

    93 citations

  7. KTH Royal Institute of Technology

    Stockholm, Sweden

    3 h-index

    7 publications

    134 citations

  8. University of Toronto

    Toronto, Canada

    3 h-index

    5 publications

    191 citations

1–8 of 77

Venues

  1. arXiv (Cornell University)

    Repository · 4 publications · 71 citations

    4

    h-index

  2. Journal of the ACM

    JACM · 3 publications · 239 citations

    3

    h-index

  3. DROPS (Schloss Dagstuhl – Leibniz Center for Informatics)

    Repository · 3 publications · 57 citations

    3

    h-index

  4. Journal of Symbolic Logic

    3 publications · 150 citations

    3

    h-index

  5. SIAM Journal on Computing

    3 publications · 95 citations

    3

    h-index

1–5