An infinite pebble game and applications

DOI10.1006/inco.1997.2640zbMath0874.68242OpenAlexW2090930788MaRDI QIDQ1362906

O. Diekmann

Publication date: 10 November 1997

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://hdl.handle.net/2144/1596

zbMATH Keywords

directed acyclic graphspebble game

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Grammars and rewriting systems (68Q42)

Related Items (2)

Recursion versus tail recursion over \(\overline{\mathbb{F}}_p\) ⋮ A difference in complexity between recursion and tail recursion

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Pebbling with an auxiliary pushdown
• Definability by programs in first-order structures
• First-order dynamic logic
• Limitations of the program memory and the expressive power of dynamic logics
• Unbounded program memory adds to the expressive power of first-order programming logic
• Some open questions in the theory of program schemes and dynamic logics
• Computing Algebraic Formulas Using a Constant Number of Registers
• Programming as a Discipline of Mathematical Nature
• On the index of a context-free grammar and language

This page was built for publication: An infinite pebble game and applications