IEICE TRANSACTIONS on Information
Some Properties on Input Head Reversal-Bounded Two-Dimensional Turing Machines
Summary :
This paper investigates properties of space-bounded "two-dimensional Turing machines (2-tm's)," whose input tapes are restricted to square ones, with bounded input head reversals in vertical direction. We first investigate a relationship between determinism and nondeterminism for space-bounded and input head reversal-bounded 2-tm's. We then investigate how the number of input head reversals affects the accepting power of sublinearly space-bounded 2-tm's. Finally, we investigate necessary and sufficient spaces for three-way 2-tm's to simulate four-way two-dimensional finite automata with constant input head reversals.
- Publication
- IEICE TRANSACTIONS on Information Vol.E86-D No.2 pp.201-212
- Publication Date
- 2003/02/01
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- Special Section PAPER (Special Issue on Selected Papers from LA Symposium)
- Category
- Turing Machine, Recursive Functions
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Masatoshi MORITA, Katsushi INOUE, Akira ITO, Yue WANG, "Some Properties on Input Head Reversal-Bounded Two-Dimensional Turing Machines" in IEICE TRANSACTIONS on Information,
vol. E86-D, no. 2, pp. 201-212, February 2003, doi: .
Abstract: This paper investigates properties of space-bounded "two-dimensional Turing machines (2-tm's)," whose input tapes are restricted to square ones, with bounded input head reversals in vertical direction. We first investigate a relationship between determinism and nondeterminism for space-bounded and input head reversal-bounded 2-tm's. We then investigate how the number of input head reversals affects the accepting power of sublinearly space-bounded 2-tm's. Finally, we investigate necessary and sufficient spaces for three-way 2-tm's to simulate four-way two-dimensional finite automata with constant input head reversals.
URL: https://global.ieice.org/en_transactions/information/10.1587/e86-d_2_201/_p
Copy
@ARTICLE{e86-d_2_201,
author={Masatoshi MORITA, Katsushi INOUE, Akira ITO, Yue WANG, },
journal={IEICE TRANSACTIONS on Information},
title={Some Properties on Input Head Reversal-Bounded Two-Dimensional Turing Machines},
year={2003},
volume={E86-D},
number={2},
pages={201-212},
abstract={This paper investigates properties of space-bounded "two-dimensional Turing machines (2-tm's)," whose input tapes are restricted to square ones, with bounded input head reversals in vertical direction. We first investigate a relationship between determinism and nondeterminism for space-bounded and input head reversal-bounded 2-tm's. We then investigate how the number of input head reversals affects the accepting power of sublinearly space-bounded 2-tm's. Finally, we investigate necessary and sufficient spaces for three-way 2-tm's to simulate four-way two-dimensional finite automata with constant input head reversals.},
keywords={},
doi={},
ISSN={},
month={February},}
Copy
TY - JOUR
TI - Some Properties on Input Head Reversal-Bounded Two-Dimensional Turing Machines
T2 - IEICE TRANSACTIONS on Information
SP - 201
EP - 212
AU - Masatoshi MORITA
AU - Katsushi INOUE
AU - Akira ITO
AU - Yue WANG
PY - 2003
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E86-D
IS - 2
JA - IEICE TRANSACTIONS on Information
Y1 - February 2003
AB - This paper investigates properties of space-bounded "two-dimensional Turing machines (2-tm's)," whose input tapes are restricted to square ones, with bounded input head reversals in vertical direction. We first investigate a relationship between determinism and nondeterminism for space-bounded and input head reversal-bounded 2-tm's. We then investigate how the number of input head reversals affects the accepting power of sublinearly space-bounded 2-tm's. Finally, we investigate necessary and sufficient spaces for three-way 2-tm's to simulate four-way two-dimensional finite automata with constant input head reversals.
ER -
English
