An Exponential Lower Bound on the Size of a Binary Moment Diagram Representing Integer Division (Special Section on Discrete Mathematics and Its Applications)
スポンサーリンク
概要
- 論文の詳細を見る
A binary moment diagram, which was proposed for arithmetic circuit verification, is a directed acyclic graph representing a function from binary-vectors to integers (f: {0, 1}^n → Z). A multiplicative binary moment diagram is an extension of a binary moment diagram with edge weights attached. A multiplicative binary moment diagram can represent addition, multiplication and many other functions with polynomial numbers of vertices. Lower bounds for division, however, had not been investigated. In this paper, we show an exponential lower bound on the number of vertices of a multiplicative binary moment diagram representing a quotient function or a remainder function.
- 社団法人電子情報通信学会の論文
- 1999-05-25
著者
-
Hamaguchi K
Osaka Univ. Toyonaka‐shi Jpn
-
Hamaguchi Kiyoharu
The Graduate School Of Information Science And Technology Osaka University
-
NAKANISHI MASAKI
Department of Chemistry and Biotechnology, Faculty of Engineering, The University of Tokyo
-
Hamaguchi Kiyoharu
Department Of Bioinformatic Engineering Guraduate School Of Information Science And Technology Osaka
-
Kashiwabara Toshinobu
The Graduate School Of Information Science And Technology Osaka University
-
Kashiwabara Toshinobu
Department Of Bioinformatic Engineering Guraduate School Of Information Science And Technology Osaka
-
Kashiwabara Toshinobu
The Department Of Information And Computer Sciences Osaka University
-
Nakanishi Masaki
The Graduate School Of Information Science Nara Institute Of Science And Technology
-
Nakanishi Masaki
Department Of Chemistry And Biotechnology Faculty Of Engineering The University Of Tokyo
-
Nakanishi Masaki
Nara Institute Of Technology
-
Nakanishi Masaki
Department of Applied Chemistry, Nagoya Institute of Technology
関連論文
- Enhancement of Mutation Frequency with Nucleotide Triphosphate Analogs in PCR Random Mutagenesis
- Verifying Signal-Transition Consistency of High-Level Designs Based on Symbolic Simulation(Special Issue on Test and Verification of VLSI)
- Bit Length Optimization of Fractional Part on Floating to Fixed Point Conversion for High-Level Synthesis(Logic and High Synthesis)(VLSI Design and CAD Algorithms)
- Look Up Table Compaction Based on Folding of Logic Functions(Special Section on VLSI Design and CAD Algorithms)
- A Partially Explicit Method for Efficient Symbolic Checking of Language Containment (Special Section on VLSI Design and CAD Algorithms)
- Bit-Length Optimization Method for High-Level Synthesis Based on Non-linear Programming Technique(System Level Design,VLSI Design and CAD Algorithms)
- Regular Temporal Logic Expressively Equivalent to Finite Automata and Its Application to Logic Design Verification
- Algorithms for Generating Maximum Weight Independent Sets in Circle Graphs, Circular-Arc Overlap Graphs, and Spider Graphs
- Expressive Power of Quantum Pushdown Automata with Classical Stack Operations under the Perfect-Soundness Condition(Computation and Computational Models)
- On the Power of Non-deterministic Quantum Finite Automata(Special Issue on Selected Papers from LA Symposium)
- An Exponential Lower Bound on the Size of a Binary Moment Diagram Representing Integer Division (Special Section on Discrete Mathematics and Its Applications)
- A Representation Diagram for Maximal Independent Sets of a Graph(Special Section on Discrete Mathematics and Its Applications)
- The Complexity of the Optimal Variable Ordering Problems of a Shared Binary Decision Diagram
- Automatic Generation of Java-Based, Database-Independent Query API
- Automatic Generation of Java-Based, Database-Independent Query API
- Comparison of Granisetron and the Combination of Granisetron plus Methylprednisolone in the Prophylaxis of Cisplatin-Induced Emesis
- Structure of physalin M isolated from Physalis alkekengi var. francketi.