Differences between 2d neighborhoods according to real time computation
A Grandjean - … Conference on Developments in Language Theory, 2017 - Springer
International Conference on Developments in Language Theory, 2017•Springer
Cellular automata are a parallel model of computation. This paper presents studies about
the impact of the choice of the neighborhood on small complexity classes, mainly the real
time class. The main result states that given two neighborhoods N and N', if N has a limiting
vertex in some direction and N'have no vertex in that direction then there is a language
recognizable in real time with N'and not with N. One easy corollary is that real time classes
for two neighborhoods may be incomparable (and such neighborhoods are easy to …
the impact of the choice of the neighborhood on small complexity classes, mainly the real
time class. The main result states that given two neighborhoods N and N', if N has a limiting
vertex in some direction and N'have no vertex in that direction then there is a language
recognizable in real time with N'and not with N. One easy corollary is that real time classes
for two neighborhoods may be incomparable (and such neighborhoods are easy to …
Abstract
Cellular automata are a parallel model of computation. This paper presents studies about the impact of the choice of the neighborhood on small complexity classes, mainly the real time class. The main result states that given two neighborhoods and , if has a limiting vertex in some direction and have no vertex in that direction then there is a language recognizable in real time with and not with . One easy corollary is that real time classes for two neighborhoods may be incomparable (and such neighborhoods are easy to construct).
Springer
以上显示的是最相近的搜索结果。 查看全部搜索结果