Affordable Access

Publisher Website

The recognition of deterministic CFLs in small time and space

Authors
Journal
Information and Control
0019-9958
Publisher
Elsevier
Publication Date
Volume
56
Identifiers
DOI: 10.1016/s0019-9958(83)80049-7

Abstract

Let S( n) be a nice space bound such that log 2 n ⩽ S( n) ⩽ n. Then every DCFL is recognized by a multitape Turing machine simultaneously in time O( n 2/ S( n)) and space O( S( n)), and this time bound is optimal. If the machine is allowed a random access input, then the time bound can be improved so that the time-space product is O( n 1 + ɛ ).

There are no comments yet on this publication. Be the first to share your thoughts.