An infinite pebble game and applications

DOI10.1006/INCO.1997.2640zbMATH Open0874.68242OpenAlexW2090930788MaRDI QIDQ1362906FDOQ1362906

Authors: 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

Recommendations

• Computer Science Logic
• Interpolation, preservation, and pebble games
• scientific article; zbMATH DE number 4189511
• Two dynamic programming algorithms for which interpreted pebbling helps

zbMATH Keywords

directed acyclic graphspebble game

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (7)

• Computer Science Logic
• White pebbles help
• Pebble games over ordered structural abstractions
• Recursion versus tail recursion over \(\overline{\mathbb{F}}_p\)
• PEBBLE GAMES AND LINEAR EQUATIONS
• A difference in complexity between recursion and tail recursion
• Graph reachability and pebble automata over infinite alphabets

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1362906)