The MathNet Korea
Information Center for Mathematical Science

논문검색

Information Center for Mathematical Science

논문검색

SIAM Journal on Computing
( Vol. 29 NO.1 / (1999))
Achilles, Turtle, and Undecidable Boundedness Problems for Small Datalog Programs
Jerzy Marcinkowski,
Pages. 231-257
Abstract
Contents 1. Introduction 1.1. Introduction 1.2. Previous works and our contribution 1.3. The method 1.4. Open
problems 1.5. Preliminaries 1.6. Example: Program boundedness vs.
uniform boundedness 1.7. Program boundedness vs. uniform
boundedness. Discussion 2. Achilles-Turtle machine 2.1. The tool:
Conway functions 2.2. Achilles-Turtle machine 2.3. Achilles-Turtle
machine. An example 3. Ternary programs 3.1. The ternary linear
program $\mathcal{P}$ 3.2. The arity 5 single recursive rule
program $\mathcal{R}$ 3.3. The ternary single recursive rule
program $\mathcal{Q}$ 4. Single rule programs 4.1. Constants:
Notational proviso 4.2. The Achilles-Turtle game 4.3. Single
linear rule program with initialization 4.4. Single rule program:
How one cannot construct it 4.5. Single rule program: How to
construct it
Key words DATALOG, query optimization, decidability
Mathmatical Subject Classification 68P15