A Note on One-Way Multicounter Machines and Cooperating Systems of One-Way Finite Automata
スポンサーリンク
概要
- 論文の詳細を見る
For each two positive integers r, s, let ℒ [1DCM(r)-Time(n^s)] (ℒ[1NCM(r)-Time(n^s)]) and ℒ[1DCM(r)-Space(n^s)] (ℒ[1NCM(r)-Space(n^s)]) be the classes of languages accepted in time n^s and in space n^s, respectively, by one-way deterministic (nondeterministic) r-counter machines. We show that for each X∈{D,N}, ℒ[1XCM(r)-Time(n^s)]≠^^⊂ℒ [1XCM(r+1)-Time(n^s)] and ℒ[1XCM(r)-Space(n^s)]≠^^⊂ℒ [1XCM(r+1)-Space(n^s)]. We also investigate the relationships between one-way multicounter machines and cooperating systems of one-way finite automata. In particular, it is shown that one-way (one-) counter machines and cooperating systems of two one-way finite automata are equivalent in accepting power.
- 社団法人電子情報通信学会の論文
- 1993-10-25
著者
-
Inoue Katsushi
Faculty Of Engineering Yamaguchi University
-
Inoue K
The Department Of Computer Science And Systems Engineering Faculty Of Engineering Yamaguchi Universi
-
Wang Y
Media And Information Technology Center Yamaguchi University
-
Wang Yue
Faculty Of Engineering Yamaguchi University
-
Inoue Katsushi
Department Of Electronics Engineering
-
Takanami Itsuo
Faculty of Engineering, Yamaguchi University
-
Takanami I
Faculty Of Engineering Yamaguchi University
-
Takanami Itsuo
Faculty Of Engineering Iwate University
関連論文
- Path-Bounded One-Way Multihead Finite Automata(Foundations of Computer Science)
- 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 Note on Sensing Semi-One-Way Simple Multihead Finite Automata (Special lssue on Selected Papers from LA Synposium)
- 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)
- On the Sensing Function of One-Way Simple Multihead Finite Automata
- A Note on Probabilistic Rebound Automata
- Identification of mutations in the Bruton's tyrosine kinase gene, including a novel genomic rearrangements resulting in large deletion, in Korean X-linked agammaglobulinemia patients
- 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
- Video file system
- A modified algorithm for taking reciprocal of n-bit integers
- Leaf-Size Bounded Real-Time Synchronized Alternating One-Way Multicounter Machines
- Closure properties of alternating one-way multihead finite automata with constant leaf-sizes
- A note on synchronized alternating Turing machines with small space bounds
- Alternating multihead finite automata with constant leaf-sizes
- A note on reversal complexities of real-time counter machines
- Alternating one-way multihead Turing machines with only universal states
- A note on multihead on-line turing machines
- A Linear-Time Normalization of One-Dimensional Quadtrees
- On Simple One-Way Multihead Pushdown Automata
- Sensing Two-Way Three Heads are Better than Two
- A Note on Alternating Multi-Counter Automata with Small Space
- Multihead Finite Automata with Markers (Special Section on Discrete Mathematics and Its Applications)
- A Note on One-Way Multicounter Machines and Cooperating Systems of One-Way Finite Automata
- Some Hierarchy Results on Multihead Automata over a One-Letter Alphabet
- 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)
- Three-Dimensionally Fully Space Constructible Functions
- Self-Reconstruction of 3D Mesh Arrays with 11/2-Track Switches by Digital Neural Circuits (Special Issue on Integrated Electronics and New System Paradigms)
- A Built-in Self-Reconfigurable Scheme for 3D Mesh Arrays
- An Efficient Method for Reconfiguring the 11/2 Track-Switch Mesh Array
- A Built-In Self-Reconstruction Approach for Partitioned Mesh-Arrays Using Neural Algorithm (Special Issue on Architectures, Algorithms and Networks for Massively parallel Computing)
- Quantitative Measures of Modic Changes in Lumbar Spine Magnetic Resonance Imaging : Intra- and Inter-rater Reliability
- ISSLS Prize Winner : Lumbar Vertebral Endplate Lesions : Associations With Disc Degeneration and Back Pain History