This file is part of IDEAS, which uses RePEc data


[ Papers | Articles | Software | Books | Chapters | Authors | Institutions | JEL Classification | NEP reports | Search | New papers by email | Author registration | Rankings | Volunteers | FAQ | Blog | Help! ]

Dynamical Recognizers: Real-Time Language Recognition by Analog Computers

Author info | Abstract | Publisher info | Download info | Related research | Statistics
Author Info
Cristopher Moore
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

Download Info
To our knowledge, this item is not available for download. To find whether it is available, there are three options:
1. Check below under "Related research" whether another version of this item is available online.
2. Check on the provider's web page whether it is in fact available.
3. Perform a search for a similarly titled item that would be available.

Publisher Info
Paper provided by Santa Fe Institute in its series Working Papers with number 96-05-023.

Download reference. The following formats are available: HTML (with abstract), plain text (with abstract), BibTeX, RIS (EndNote, RefMan, ProCite), ReDIF
Length:
Date of creation: May 1996
Date of revision:
Handle: RePEc:wop:safiwp:96-05-023

Contact details of provider:
Postal: 1399 Hyde Park Road, Santa Fe, New Mexico 87501
Web page: http://www.santafe.edu/sfi/publications/working-papers.html
More information through EDIRC

For technical questions regarding this item, or to correct its listing, contact: (Thomas Krichel).

Related research
Keywords:

Statistics
Access and download statistics

Did you know? IDEAS also indexes book chapters.

This page was last updated on 2009-12-16.

This information is provided to you by IDEAS at the Department of Economics, College of Liberal Arts and Sciences, University of Connecticut using RePEc data on a server sponsored by the Society for Economic Dynamics.