TIGHT BOUNDS FOR THE SPACE COMPLEXITY OF NONREGULAR LANGUAGE RECOGNITION BY REAL-TIME MACHINES

We examine the minimum amount of memory for real-time, as opposed to one-way, computation accepting nonregular languages. We consider deterministic, nondeterministic and alternating machines working within strong, middle and weak space, and processing general or unary inputs. In most cases, we are a...

Full description

Saved in:
Bibliographic Details
Published in:International journal of foundations of computer science 2013-12, Vol.24 (8), p.1243-1253
Main Authors: YAKARYILMAZ, ABUZER, CEM SAY, A. C.
Format: Article
Language:English
Subjects:
Acceptance
Computation
Computer memory
Devices
Foundations
Lower bounds
Real time
Recognition
Stacks
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We examine the minimum amount of memory for real-time, as opposed to one-way, computation accepting nonregular languages. We consider deterministic, nondeterministic and alternating machines working within strong, middle and weak space, and processing general or unary inputs. In most cases, we are able to show that the lower bounds for one-way machines remain tight in the real-time case. Memory lower bounds for nonregular acceptance on other devices are also addressed. It is shown that increasing the number of stacks of real-time pushdown automata can result in exponential improvement in the total amount of space usage for nonregular language recognition.
ISSN:0129-0541
1793-6373
DOI:10.1142/S0129054113500329