Metadata
Author: WikiMatrix
Data
Czech[cs]
Deterministické bezkontextové jazyky mohou být rozpoznávány deterministickým Turingovým strojem s pamětí velikosti O(log2 n) v polynomiálním čase; v důsledku toho je třída deterministických bezkontextových jazyků podtřídou třídy složitosti SC.
English[en]
Deterministic context-free languages can be recognized by a deterministic Turing machine in polynomial time and O(log2 n) space; as a corollary, DCFL is a subset of the complexity class SC.