Massively Parallel Search for Transition-Tables of Polyautomata.

Abstract

One of the fundamental tasks in automata theory is to look for transitiontables that implement a given specification. In principle, most of this task can be performed by a computer. But a combinatorial explosion in the number of possible transition-tables quickly renders brute force search impractical. This paper demonstrates two approaches to extend the frontier of tractable problem sizes. Firstly, an efficient heuristic technique is used which dramatically prunes the search space without giving up completeness. Secondly, a massively parallel implementation is described which achieves near linear speedup on as many as 16384 Processors. These techniques yield some new results regarding two open problems involving cellular automata and trellis automata. 1 Introduction A recurring theme in computer science is the wish to automatically infer programs from a problem specification. In general, program inference is undecidable and even in cases where it is decidable its computational comple...