首页 | 本学科首页   官方微博 | 高级检索  
     


Independent finite automata on Cayley graphs
Authors:Ville Salo  Ilkka Törmä
Affiliation:1.Center of Mathematical Modeling,University of Chile,Santiago,Chile;2.Department of Computer Science,Boston University,Boston,USA;3.Department of Mathematics and Statistics,University of Turku,Turku,Finland
Abstract:In the setting of symbolic dynamics on discrete finitely generated infinite groups, we define a model of finite automata with multiple independent heads that walk on Cayley graphs, called group-walking automata, and use it to define subshifts. We characterize the torsion groups (also known as periodic groups) as those on which the group-walking automata are strictly weaker than Turing machines, and those on which the head hierarchy is infinite.
Keywords:
本文献已被 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号