Dynamical Recognizers: Real-Time Language Recognition by Analog Computers

Cristopher Moore
Additional contact information
Cristopher Moore: http://www.santafe.edu/~moore

Working Papers from Santa Fe Institute

Abstract: Following Pollack, we consider a model of analog computer which can recognize various languages in real time. We encode an input word as a point in R[super d] by composing iterated maps, and then apply inequalities to the resulting point to test for membership in the language.

Each class of maps and inequalities, such as quadratic functions with rational coefficients, is capable of recognizing a particular class of languages; for instance, linear and quadratic maps can have both stack-like and queue-like memories. We use methods equivalent to the Vapnik-Chervonenkis dimension to separate some of our classes from each other, e.g., linear maps are less powerful than quadratic or piecewise-linear ones, polynomials are less powerful than elementary (trigonometric and exponential) maps, and deterministic polynomials of each degree are less powerful than their non-deterministic counterparts.

Comparing these dynamical classes with various discrete language classes helps illuminate how iterated maps can store and retrieve information in the continuum, the extent to which computation can be hidden in the encoding from symbol sequences into continuous spaces, and the relationship between analog and digital computation in general.

We relate this model to other models of analog computation; for instance, it can be seen as a real-time, constant-space, off-line version of Blum, Shub, and Smale's real-valued machines.

Key words. language recognition, real-time computation, analog computation, dynamical systems, automata theory, neural networks, Spootie

Date: 1996-05
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wop:safiwp:96-05-023

Access Statistics for this paper

More papers in Working Papers from Santa Fe Institute Contact information at EDIRC.
Bibliographic data for series maintained by Thomas Krichel ().