On 1-Inkdot Alternating Pushdown Automata with Sublogarithmic Space(Theory of Automata, Formal Language Theory)
スポンサーリンク
概要
- 論文の詳細を見る
This paper introduces a 1-inkdot two-way alternating pushdown automaton which is a two-way alternating pushdown automaton (2apda) with the additional power of marking at most 1 tape-cell on the input (with in inkdot) once. We first investigate a relationship between the accepting powers of sublogarithmically space-bounded 2apda's with and without 1 inkdot, and show, example, that sublogarithmically spacebounded 2apda's with 1 inkdot are more powerful than those which have no inkdots. We next investigate an alternation hierarchy for sublogarithmically space-bounded 1-inkdot 2apda's, and show that the alternation hierarchy on the first level for 1-inkdot 2apda's holds, and we also show that 1-inkdot two-way nondeterministic pushdown automata using sublogarithmic space are incomparable with 1-inkdot two-way alternating pushdown automata with only universal states using the same space.
- 社団法人電子情報通信学会の論文
- 2003-09-01
著者
-
YOSHINAGA Tsunehiro
Department of Computer Science and Electrics Engineering, Tokuyama College of Technology
-
INOUE Katsushi
Department of Computer Science and Systems Engineering, Faculty of Engineering, Yamaguchi University
-
Inoue Katsushi
Department Of Computer Science And Systems Engineering Faculty Of Engineering Yamaguchi University
-
Inoue K
Department Of Computer Science And Systems Engineering Faculty Of Engineering Yamaguchi University
-
CHEN Yong
Department of Bacteriology, School of Medicine, The University of Tokushima
-
Xu Jianliang
Department Of Computer Science Ocean University Of China
-
Xu Jianliang
Department Of Computer Science And Systems Engineering Faculty Of Engineering Yamaguchi University
-
Yoshinaga Tsunehiro
Department Of Computer Science And Electronics Engineering Tokuyama College Of Technology
-
Yoshinaga Tsunehiro
Department Of Computer Science And Electrics Engineering
-
Yoshinaga Tsunehiro
Department Of Computer Science And Electronic Engineering Tokuyama College Of Technology
-
Chen Yong
Department Of Bacteriology School Of Medicine The University Of Tokushima
関連論文
- Sublinear Space-Bounded One-Way Self-Verifying Nondeterministic Turing Machines
- Non-closure Property of One-Pebble Turing Machines with Sublogarithmic Space(Discrete Mathematics and Its Applications)
- Inhibition of Pancreatic Tumor Cell Growth in Culture by p21^ Recombinant Adenovirus
- Purification and Characterization of a Fibrinogen-Degrading Protease in Bacteroides fragilis Strain YCH46
- 空間量が対数以下に制限された存在(全称)状態のみからなる1-インクドット交代チューリングマシンの閉包性について
- Space hierarchies of three-dimensional turing machines
- Immunosuppressive effect of IDO on T cells in patients with chronic hepatitis B
- Some Properties on Input Head Reversal-Bounded Two-Dimensional Turing Machines (Special Issue on Selected Papers from LA Symposium)
- Self-Verifying Nondeterministic and Las Vegas Multihead Finite Automata (Special Section on Discrete Mathematics and Its Applications)
- A Relationship between Two-Way Deterministic One-Counter Automata and One-Pebble Deterministic Turing Machines with Sublogarithmic Space
- Alternating Rebound Turing Machines (Special Section on Discrete Mathematics and Its Applications)
- Some Observations Concerning Alternating Pushdown Automata with Sublogarithmic Space
- On Multi-Inkdot Two-Way Alternating Turing Machines and Pushdown Automata with Sublogarithmic Space and Constant Leaf-Size
- A Note on Alternating Pushdown Automata with Sublogarithmic Space
- A Note on One-way Auxiliary Pushdown Automata
- A Note on Alternating Pushdown Automata With Sublogarithmic Space
- Inkdot versus Pebble over Two-Dimensional Languages
- An algorithm for tower of hanoi with four or more poles
- A note on bottom-up pyramid acceptors
- Video file system
- A modified algorithm for taking reciprocal of n-bit integers
- Non-closure Properties of 1-Inkdot Nondeterministic Turing Machines and Alternating Turing Machines with Only Universal States Using Small Space
- Atomic Force Microscopic Examination of Chromosomes Treated with Trypsin or Ethidium Bromide
- A note on multihead on-line turing machines
- On Simple One-Way Multihead Pushdown Automata
- Sensing Two-Way Three Heads are Better than Two
- Effect of nutrient salts eluted from hedoro blocks on growth and survival rate of gametophyte and juvenile Eisenia bicyclis
- A Note on Alternating Multi-Counter Automata with Small Space
- Alternating Finite Automata with Counters and Stack-Counters Operating in Realtime
- Hierarchical Properties of Realtime One-Way Alternating Multi-Stack-Counter Automata (Special Section on Discrete Mathematics and Its Applications)
- A Note on Realtime One-Way Alternating and Deterministic Multi-Counter Automata(Special Issue on Selected Papers from LA Symposium)
- Las Vegas, Self-Verifying Nondeterministic and Deterministic One-Way Multi-Counter Automata with Bounded Time
- Template Synthesis of Arrays of One-dimensional Gold Nanowires Standing on a Carbon Film
- Adenosine A_ receptor is highly expressed in human hepatocellular carcinoma
- Three-dimensional multicounter auaomata
- Formation and Aggregation of Lipid Rafts in γδT Cells Following Stimulation with Mycobacterium tuberculosis Antigens
- Sublogarithmic Space-Bounded Multi-Inkdot Alternating Turing Machines with Only Existential (Universal) States(Discrete Mathematics and Its Applications)
- Polynomial Time-Bounded Alternating Multi-Counter Automata
- Some Observations on One-way Alternating Pushdown Automata with Sublinear Space(Discrete Mathematics and Its Applications)
- On 1-Inkdot Alternating Pushdown Automata with Sublogarithmic Space(Theory of Automata, Formal Language Theory)
- Some Observations on 1-Inkdot Alternating Multi-Counter Automata with Sublinear Space
- ALTERNATION FOR TWO-WAY (INKDOT) MULTI-COUNTER AUTOMATA WITH SUBLINEAR SPACE
- A leaf-size hierarchy of three-dimensional alternating turing Machines
- A note on decision problems for three-way two-dimensional finite automata
- Sublinear Space-Bounded Multi-Inkdot Alternating Multi-Counter Automata with Only Universal States
- D-1-3 Non-Closure Properties of Cooperating Systems of One-Way Alternating Finite Automata with Only Universal States