Closure properties of alternating one-way multihead finite automata with constant leaf-sizes
スポンサーリンク
概要
- 論文の詳細を見る
Previous Papers introduced alternating multihead finite automata with constant leaf-sizes (AMHFACLs) and investigated several properties of these automata. Leaf-size, in a sense, reflects the number of processors that run in parallel in scanning a given input word. AMHFACLs are more realistic parallel computation models than ordinary alternating multihead finite automata, because of the restriction that the number of processors running in parallel should be constant. This paper examines the closure properties of the class of sets accepted by one-way AMHFACLs and one-way alternating simple multihead finite automata with constant leaf-sizes in the operations of taking union, intersection, complementation, concatenation, Kleene closure, reversal, andε-free homomorphism.
- 一般社団法人情報処理学会の論文
- 1991-02-10
著者
-
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)