%0 Journal Article %1 ito1997nonclosure %A Ito, Akira %A Inoue, Katsushi %A Wang, Yue %D 1997 %J International Journal of Pattern Recognition and Artificial Intelligence %K 2013 automata languages picture %P 1025 %T Nonclosure Properties of Two-Dimensional One-Marker Automata %U http://www.worldscientific.com/doi/abs/10.1142/S0218001497000469#citedBySection %V Volume 11 %X 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. Read More: http://www.worldscientific.com/doi/abs/10.1142/S0218001497000469#citedBySection

@article{ito1997nonclosure, abstract = {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. Read More: http://www.worldscientific.com/doi/abs/10.1142/S0218001497000469#citedBySection}, added-at = {2013-06-15T21:31:49.000+0200}, author = {Ito, Akira and Inoue, Katsushi and Wang, Yue}, biburl = {https://www.bibsonomy.org/bibtex/2522d74de23169e91e6717582e95dad0b/s_6wg2xw}, description = {Nonclosure Properties of Two-Dimensional One-Marker Automata (World Scientific)}, interhash = {5ccde8e1fa1e05c8dd1959e7fc99a36b}, intrahash = {522d74de23169e91e6717582e95dad0b}, journal = {International Journal of Pattern Recognition and Artificial Intelligence}, keywords = {2013 automata languages picture}, pages = 1025, timestamp = {2014-04-07T15:55:43.000+0200}, title = {Nonclosure Properties of Two-Dimensional One-Marker Automata}, url = {http://www.worldscientific.com/doi/abs/10.1142/S0218001497000469#citedBySection}, volume = {Volume 11}, year = 1997 }