Classes of Szilard Languages in NC^1
Liliana Cojocaru, Erkki Mäkinen, Ferucio Laurenţiu Ţiplea · 2009
We prove that Szilard languages of context-free grammars can be accepted by an indexing alternating Turing machine (indexing ATM) in logarithmic time and space. The same result holds for leftmost Szilard languages of unrestricted (phrase-structure or type 0) grammars. Since the class of languages recognizable by an indexing ATM in logarithmic time equals the UE-uniform NC1class, we obtain that the above classes of Szilard languages are in NC1. The inclusions are strict, since there exist languages in NC1that cannot be Szilard languages of any context-free or unrestricted grammar.