6533b839fe1ef96bd12a6db0

RESEARCH PRODUCT

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

Abuzer YakaryilmazA. C. Cem Say

subject

Discrete mathematicsNondeterministic algorithmTheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGESUnary operationComputationTheory of computationComputer Science (miscellaneous)Pushdown automatonSpace (mathematics)MathematicsLanguage recognitionExponential function

description

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.

yearjournalcountryeditionlanguage
2013-12-01International Journal of Foundations of Computer Science
https://doi.org/10.1142/s0129054113500329