Leaf-Size Bounded Real-Time Synchronized Alternating One-Way Multicounter Machines
スポンサーリンク
概要
- 論文の詳細を見る
This paper investigates the properties of synchronized alternating one-way multicounter machines (1samcm's) which operate in real time (1samcm-real's) and whose leaf-sizes are bounded by a constant or some function of the length of an input. Leaf-size reflects the number of processors which run in parallel in scanning a given input. We first consider the hierarchies of 1samcm-real's based on the number of counters and constant leaf-sizes. We next show that 1samcm-real's are less powerful than 1samcm's which operate in linear time when the leaf-sizes of these machines are bounded by a function L(n) such that lim_<n→∞<[L(n)log n/n]=0 and L(n)≧2.
- 社団法人電子情報通信学会の論文
- 1994-03-25
著者
-
Inoue Katsushi
Faculty Of Engineering Yamaguchi University
-
Matsuno Hiroshi
Oshima National College Of Maritime Technology
-
Inoue K
The Department Of Computer Science And Systems Engineering Faculty Of Engineering Yamaguchi Universi
-
Inoue Katsushi
Department Of Electronics Engineering
-
Takanami Itsuo
Faculty of Engineering, Yamaguchi University
-
Takanami I
Faculty Of Engineering Yamaguchi University
-
Inoue K
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
- 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
- Constructing biological pathway models with hybrid functional Petri nets
- Biopathways representation and simulation on hybrid functional Petri net
- 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
- Modeling and Simulation of Fission Yeast Cell Cycle on Hybrid Functional Petri Net(Hybrid Systems)(Concurrent Systems and Hybrid Systems)
- Efficiency of Parallel Computation on the Binary-Tree Machine CORAL'83
- 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
- XML documentation of biopathways and their simulations in Genomic Object Net
- 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)