Machines that Can Output Empty Words

被引：0
作者：
Christian Glaßer
Stephen Travers
机构：
[1] Universität Würzburg,Theoretische Informatik
来源：
Theory of Computing Systems | 2009年 / 44卷
关键词：
Computational complexity; Polynomial-time hierarchy; Leaf languages; Gap theorems;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
We propose the e-model for leaf languages which complements the known balanced and unbalanced concepts. Inspired by the neutral behavior of rejecting paths of NP machines, we allow transducers to output empty words.
引用
收藏
页码：369 / 390
页数：21
相关论文
共 36 条
[1]  
Blass A.(1982)On the unique satisfiability problem Inf. Control 82 80-88
[2]  
Gurevich Y.(1995)On the acceptance power of regular languages Theor. Comput. Sci. 148 207-225
[3]  
Borchert B.(1999)On existentially first-order definable languages and their relation to NP Theor. Inf. Appl. 33 259-269
[4]  
Borchert B.(2005)The dot-depth and the polynomial hierarchies correspond on the delta levels Int. J. Found. Comput. Sci. 16 625-644
[5]  
Kuske D.(1992)A uniform approach to define complexity classes Theor. Comput. Sci. 104 263-283
[6]  
Stephan F.(1976)Hierarchies of aperiodic languages RAIRO Inf. Theor. 10 33-49
[7]  
Borchert B.(1998)Lindström quantifiers and leaf language definability Int. J. Found. Comput. Sci. 9 277-294
[8]  
Lange K.(1971)Dot-depth of star-free events J. Comput. Syst. Sci. 5 1-16
[9]  
Stephan F.(2007)Languages polylog-time reducible to dot-depth 1/2 J. Comput. Syst. Sci. 73 36-56
[10]  
Tesson P.(2007)Autoreducibility, mitoticity, and immunity J. Comput. Syst. Sci. 73 735-754
1234