Name
Abstract | ||
|---|---|---|
We generalize the pebble game to infinite directed acyclic graphs and use this generalization to give new and shorter proofs of the following well-known results: (1) that unbounded memory increases the power of logics of programs, and (2) that there exists a context-free grammar with infinite index. |
Year | DOI | Venue |
|---|---|---|
1997 | 10.1006/inco.1997.2640 | Information and Computation/information and Control |
Keywords | Field | DocType |
infinite pebble game,ehrenfeucht-fraisse game,model theory,shorter proof,infinite index,formal language theory,original proof,context-free language,advanced technique,tiuryn-erimbetov result,first-order logic,directed acyclic graph,context free grammar,indexation | Discrete mathematics,Combinatorics,Context-free grammar,Existential quantification,Directed graph,Directed acyclic graph,Mathematical proof,Game theory,Logic programming,Pebble,Mathematics | Journal |
Volume | Issue | ISSN |
136 | 1 | Information and Computation |
Citations | PageRank | References |
2 | 0.49 | 8 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| A. J. Kfoury | 1 | 461 | 47.34 |
| A. P. Stolboushkin | 2 | 5 | 1.31 |