Walking on Data Words

详细信息    查看全文

• 作者：Amaldev Manuel ; Anca Muscholl ; Gabriele Puppis
• 刊名：Theory of Computing Systems
• 出版年：2016
• 出版时间：August 2016
• 年：2016
• 卷：59
• 期：2
• 页码：180-208
• 全文大小：1,188 KB
• 刊物类别：Computer Science
• 刊物主题：Theory of Computation
  Computational Mathematics and Numerical Analysis
  
• 出版者：Springer New York
• ISSN：1433-0490
• 卷排序：59

文摘

Data words are words with additional edges that connect pairs of positions carrying the same data value. We consider a natural model of automaton walking on data words, called Data Walking Automaton, and study its closure properties, expressiveness, and the complexity of some basic decision problems. Specifically, we show that the class of deterministic Data Walking Automata is closed under all Boolean operations, and that the class of non-deterministic Data Walking Automata has decidable emptiness, universality, and containment problems. We also prove that deterministic Data Walking Automata are strictly less expressive than non-deterministic Data Walking Automata, which in turn are captured by Class Memory Automata.KeywordsData languagesWalking automata