Non-closure Properties of 1-Inkdot Nondeterministic Turing Machines and Alternating Turing Machines with Only Universal States Using Small Space
Summary :
This paper investigates the closure properties of 1-inkdot nondeterministic Turing machines and 1-inkdot alternating Turing machines with only universal states which have sublogarithmic space. We show for example that the classes of sets accepted by these Turing machines are not closed under length-preserving homomorphism, concatenation with regular set, Kleene closure, and complementation.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E93-A No.6 pp.1148-1152
- Publication Date
- 2010/06/01
- Publicized
- Online ISSN
- 1745-1337
- DOI
- 10.1587/transfun.E93.A.1148
- Type of Manuscript
- Special Section LETTER (Special Section on Discrete Mathematics and Its Applications)
- Category
- Algorithms and Data Structures
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
Tsunehiro YOSHINAGA, Jianliang XU, Makoto SAKAMOTO, "Non-closure Properties of 1-Inkdot Nondeterministic Turing Machines and Alternating Turing Machines with Only Universal States Using Small Space" in IEICE TRANSACTIONS on Fundamentals,
vol. E93-A, no. 6, pp. 1148-1152, June 2010, doi: 10.1587/transfun.E93.A.1148.
Abstract: This paper investigates the closure properties of 1-inkdot nondeterministic Turing machines and 1-inkdot alternating Turing machines with only universal states which have sublogarithmic space. We show for example that the classes of sets accepted by these Turing machines are not closed under length-preserving homomorphism, concatenation with regular set, Kleene closure, and complementation.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E93.A.1148/_p
Copy
@ARTICLE{e93-a_6_1148,
author={Tsunehiro YOSHINAGA, Jianliang XU, Makoto SAKAMOTO, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Non-closure Properties of 1-Inkdot Nondeterministic Turing Machines and Alternating Turing Machines with Only Universal States Using Small Space},
year={2010},
volume={E93-A},
number={6},
pages={1148-1152},
abstract={This paper investigates the closure properties of 1-inkdot nondeterministic Turing machines and 1-inkdot alternating Turing machines with only universal states which have sublogarithmic space. We show for example that the classes of sets accepted by these Turing machines are not closed under length-preserving homomorphism, concatenation with regular set, Kleene closure, and complementation.},
keywords={},
doi={10.1587/transfun.E93.A.1148},
ISSN={1745-1337},
month={June},}
Copy
TY - JOUR
TI - Non-closure Properties of 1-Inkdot Nondeterministic Turing Machines and Alternating Turing Machines with Only Universal States Using Small Space
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1148
EP - 1152
AU - Tsunehiro YOSHINAGA
AU - Jianliang XU
AU - Makoto SAKAMOTO
PY - 2010
DO - 10.1587/transfun.E93.A.1148
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E93-A
IS - 6
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - June 2010
AB - This paper investigates the closure properties of 1-inkdot nondeterministic Turing machines and 1-inkdot alternating Turing machines with only universal states which have sublogarithmic space. We show for example that the classes of sets accepted by these Turing machines are not closed under length-preserving homomorphism, concatenation with regular set, Kleene closure, and complementation.
ER -
English
