An Infinite Pebble Game and Applications

M. Ben-Or, R. Cleve, 1988, Computing algebraic formulas using a constant number of registers, Proceedings of 20th ACM Symposium on Theory of Computing, 254, 257 Erimbetov, 1981, On the expressive power of programming logics Erimbetov, 1981, A fragment of a logic with infinite formulas, 30 Dijkstra, 1976 Harel, 1979, 68 B. Kalyasundaram, G. Schnitger, 1988, On the power of white pebbles, Proceedings of 20th ACM Symposium on Theory of Computing, 258, 266 Kfoury, 1983, Definability by programs in first-order structures, Theoret. Comput. Sci., 25, 1, 10.1016/0304-3975(83)90013-0 Kfoury, 1989, Some open problems in the theory of program schemes and dynamic logics, Russ. Math. Surv., 44, 43, 10.1070/RM1989v044n01ABEH002007 D. Kozen, 1984, Pebbling, edgings, and equational logic, Proceedings 16th ACM Symposium on Theory of Computing, 428, 435 Kozen, 1990, Logics of programs, 789 Musikaev, 1993, Limitations of the program memory and the expressive power of dynamic logics, Inform. and Comput., 103, 195, 10.1006/inco.1993.1018 Paterson, 1970, MIT A.I. Lab Technical Memo, 201 Pippenger, 1981, Pebbling with an auxiliary pushdown, J. Comput. System Sci., 23, 151, 10.1016/0022-0000(81)90011-8 Pippenger, 1982, Advances in Pebbling, Lecture Notes in Computer Science, 140, 10.1007/BFb0012787 Salomaa, 1969, On the index of a context-free grammar and language, Inform. and Control, 14, 474, 10.1016/S0019-9958(69)90164-8 Salomaa, 1973 J. Savage, J. Vitter, 1984, Parallelism in space-time tradeoffs, Proceedings of International Workshop on VLSI: Algorithms and Architecture, Amalfi, Italy Tiuryn, 1984, Unbounded program memory adds to the expressive power of first-order programming logic, Inform. and Control, 60, 12, 10.1016/S0019-9958(84)80020-0 Tiuryn, 1981, Implicit definability of finite binary trees by sets of equations, 171