Preface

作     者：Serge Miguet Annick Montanvert P. S. P. Wang 

作者机构：Laboratory E.R.I.C. bâtiment L Université Lumière Lyon 2 5 avenue Pierre Mendes 69676 Bron Cedex France TIMC - INFODIS Domáine de la Merci F-38700 LaFronche France Department of Computer Science and Systems Engineering Faculty of Engineering Yamaguchi University Ube 755 Japan 

出 版 物：《International Journal of Pattern Recognition and Artificial Intelligence》 

年 卷 期：1997年第11卷第7期

页      面：1023-1024页

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：Automaton two-dimensional tape connected picture one-marker closure property alternation Turing machine 

摘      要：Several nonclosure properties of each class of sets accepted by two-dimensional alternating one-marker automata, alternating one-marker automata with only universal states, nondeterministic one-marker automata, deterministic one-marker automata, alternating finite automata, and alternating finite automata with only universal states are shown. To do this, we first establish the upper bounds of the working space used by three-way alternating Turing machines with only universal states to simulate those four-way non-storage machines. These bounds provide us a simplified and unified proof method for the whole variants of one-marker and/or alternating finite state machine, without directly analyzing the complex behavior of the individual four-way machine on two-dimensional rectangular input tapes. We also summarize the known closure properties including Boolean closures for all the variants of two-dimensional alternating one-marker automata.