10/6/97- Whitney Tabor
Cornell University
Metric Relations among Analog Computers

The recent work on real-valued automata (e.g., Blum, Shub, and Smale, 1989; Koiran, 1993; Bournez and Cosnard, 1996; Siegelmann, 1996; Moore, (to appear)) has focused largely on questions about computational complexity and tractability. It is also revealing to examine the metric relations that such automata induce on formal languages via the natural metrics on their parameter paces. This brings the theory of computational classification closer to theories of learning and statistical modeling which depend on measuring distances between models. With this in mind, I develop a general method of simulating pushdown automata with real-valued automata. I then explore the metric organization of these devices in a basic example and show how it fleshes out the skeletal structure of the Chomsky Hierarchy in an appealing way.