Paper Info
Title
Tight Bounds For The Space Complexity Of Nonregular Language Recognition By Real-Time Machines
Abstract
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 oneway 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.
Year
DOI
Venue
2013
10.1142/S0129054113500329
INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE
Keywords
DocType
Volume
Theory of computation, real-time, space bounded computation
Journal
24
Issue
ISSN
Citations 
8
0129-0541
5
PageRank 
References 
Authors
0.56
12
2
Name
Order
Citations
PageRank
Abuzer Yakaryilmaz116825.31
A. C. Cem Say219326.13