6533b85efe1ef96bd12c0629

RESEARCH PRODUCT

The Minimum Amount of Useful Space: New Results and New Directions

Klaus ReinhardtKlaus ReinhardtAbuzer Yakaryilmaz

subject

CombinatoricsDiscrete mathematicsRegular languageUnary operationQuantum registerUnary languagePushdown automatonSpace (mathematics)Upper and lower boundsAutomatonMathematics

description

We consider minimal space requirements when using memory with restricted access policy (pushdown - hence giving pushdown automata (PDAs), and counter - hence giving counter automata (CAs)) in connection with two-way and realtime head motion. The main results are that: (i) loglogn is a tight space lower bound for accepting general nonregular languages on weak realtime PDAs, (ii) there exist unary nonregular languages accepted by realtime alternating CAs within weak logn space, (iii) there exist nonregular languages accepted by two-way DPADs within strong loglogn space, and, (iv) there exist unary nonregular languages accepted by two-way CAs with quantum and classical states within middle logn space and bounded error.

yearjournalcountryeditionlanguage
2014-01-01
https://doi.org/10.1007/978-3-319-09698-8_28