On Distinguishing NC1 and NL

被引：1

作者：

Krebs, Andreas ^{[1
]}

Lange, Klaus-Joern ^{[1
]}

Ludwig, Michael ^{[1
]}

机构：

[1] Univ Tubingen, WSI, D-72076 Tubingen, Germany

来源：

DEVELOPMENTS IN LANGUAGE THEORY (DLT 2015) | 2015年 / 9168卷

关键词：

LANGUAGES;

D O I：

10.1007/978-3-319-21500-6_27

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We obtain results within the area of dense completeness, which describes a close relation between families of formal languages and complexity classes. Previously we were able show that this relation exists between counter languages and NL but not between the regular languages and NC1. We narrow the gap between the regular languages and the counter languages by considering visibly counter languages. It turns out that they are not densely complete for NC1. At the same time we found a restricted counter automaton model which is densely complete for NL. Besides counter automata we show more positive examples in terms of L-systems.

引用

页码：340 / 351

页数：12