Chaotic Fixed Point Iterations

In this paper we present a new fixed point theorem applicable for a countable system of recursive equations. We demonstrate the power and versatility of our result by applications in automata theory (AT), data flow analysis (DFA), and program optimization (PO). In AT and DFA this is demonstrated by proving the correctness of partitioning algorithms computing (strong) bisimulation and of workset algorithms computing solutions of data flow analysis problems, repectively, and in PO for proving the optimality of an algorithm for partial dead code elimination. Moreover, we show that our approach is more general than vector iterations. Keywords Fixed point, chaotic iteration, vector iteration, automata theory, data flow analysis, program optimization, partitioning algorithms, bisimulation, workset algorithms, partial dead code elimination. Contents 1 Introduction 1 2 Theory 2 2.1 The Main Theorem : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 2 2.2 Vector Iterations : : : ..