Relevant bibliographies by topics / Algebaic Decision Diagram

Academic literature on the topic 'Algebaic Decision Diagram'

Author: Grafiati
Published: 9 March 2023
Last updated: 10 March 2023

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Contents

Consult the lists of relevant articles, books, theses, conference reports, and other scholarly sources on the topic 'Algebaic Decision Diagram.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Journal articles on the topic "Algebaic Decision Diagram"

1

DJIDJEV, HRISTO N., and ANDRZEJ LINGAS. "ON COMPUTING VORONOI DIAGRAMS FOR SORTED POINT SETS." International Journal of Computational Geometry & Applications 05, no. 03 (September 1995): 327–37. http://dx.doi.org/10.1142/s0218195995000192.

Full text
Abstract:
We show that the Voronoi diagram of a finite sequence of points in the plane which gives sorted order of the points with respect to two perpendicular directions can be computed in linear time. In contrast, we observe that the problem of computing the Voronoi diagram of a finite sequence of points in the plane which gives the sorted order of the points with respect to a single direction requires Ω(n log n) operations in the algebraic decision tree model. As a corollary from the first result, we show that the bounded Voronoi diagrams of simple n-vertex polygons which can be efficiently cut into the so called monotone histograms can be computed in o(n log n) time.
APA, Harvard, Vancouver, ISO, and other styles
2

Rauzy, Antoine, and Yang. "Decision Diagram Algorithms to Extract Minimal Cutsets of Finite Degradation Models." Information 10, no. 12 (November 25, 2019): 368. http://dx.doi.org/10.3390/info10120368.

Full text
Abstract:
In this article, we propose decision diagram algorithms to extract minimal cutsets of finite degradation models. Finite degradation models generalize and unify combinatorial models used to support probabilistic risk, reliability and safety analyses (fault trees, attack trees, reliability block diagrams…). They formalize a key idea underlying all risk assessment methods: states of the models represent levels of degradation of the system under study. Although these states cannot be totally ordered, they have a rich algebraic structure that can be exploited to extract minimal cutsets of models, which represent the most relevant scenarios of failure. The notion of minimal cutsets we introduce here generalizes the one defined for fault trees. We show how algorithms used to calculate minimal cutsets can be lifted up to finite degradation models, thanks to a generic decomposition theorem and an extension of the binary decision diagrams technology. We discuss the implementation and performance issues. Finally, we illustrate the interest of the proposed technology by means of the use case stemmed from the oil and gas industry.
APA, Harvard, Vancouver, ISO, and other styles
3

Dudek, Jeffrey, Vu Phan, and Moshe Vardi. "ADDMC: Weighted Model Counting with Algebraic Decision Diagrams." Proceedings of the AAAI Conference on Artificial Intelligence 34, no. 02 (April 3, 2020): 1468–76. http://dx.doi.org/10.1609/aaai.v34i02.5505.

Full text
Abstract:
We present an algorithm to compute exact literal-weighted model counts of Boolean formulas in Conjunctive Normal Form. Our algorithm employs dynamic programming and uses Algebraic Decision Diagrams as the main data structure. We implement this technique in ADDMC, a new model counter. We empirically evaluate various heuristics that can be used with ADDMC. We then compare ADDMC to four state-of-the-art weighted model counters (Cachet, c2d, d4, and miniC2D) on 1914 standard model counting benchmarks and show that ADDMC significantly improves the virtual best solver.
APA, Harvard, Vancouver, ISO, and other styles
4

Bibilo, P. N., and V. I. Romanov. "Experimental Study of Algorithms for Minimization of Binary Decision Diagrams using Algebraic Representations of Cofactors." Programmnaya Ingeneria 13, no. 2 (February 17, 2022): 51–67. http://dx.doi.org/10.17587/prin.13.51-67.

Full text
Abstract:
BDD (Binary Decision Diagram) is used for technology-independent optimization, performed as the first stage in the synthesis of logic circuits in the design of ASIC (application-specific integrated circuit). BDD is an acyclic graph defining a Boolean function or a system of Boolean functions. Each vertex of this graph is associated with the complete or reduced Shannon expansion formula. Binary decision diagrams with mutually inverse subfunctions (cofac-tors) are considered. We have developed algorithms for finding algebraic representations of cofactors of the same BDD level in the form of a disjunction or conjunction of other inverse or non-inverse cofactors of the same BDD level. The algorithms make it possible to reduce the number of literals by replacing the Shannon expansion formulas with simpler logical formulas and to reduce the number of literals in the description of a system of Boolean functions. We propose to use the developed algorithms for an additional logical optimization of the constructed BDD representations of systems of Boolean functions. Experimental results of the application of the corresponding programs in the synthesis of logic circuits in the design library of custom VLSI CMOS circuits are presented.
APA, Harvard, Vancouver, ISO, and other styles
5

Pralet, C., G. Verfaillie, and T. Schiex. "An Algebraic Graphical Model for Decision with Uncertainties, Feasibilities, and Utilities." Journal of Artificial Intelligence Research 29 (August 23, 2007): 421–89. http://dx.doi.org/10.1613/jair.2151.

Full text
Abstract:
Numerous formalisms and dedicated algorithms have been designed in the last decades to model and solve decision making problems. Some formalisms, such as constraint networks, can express "simple" decision problems, while others are designed to take into account uncertainties, unfeasible decisions, and utilities. Even in a single formalism, several variants are often proposed to model different types of uncertainty (probability, possibility...) or utility (additive or not). In this article, we introduce an algebraic graphical model that encompasses a large number of such formalisms: (1) we first adapt previous structures from Friedman, Chu and Halpern for representing uncertainty, utility, and expected utility in order to deal with generic forms of sequential decision making; (2) on these structures, we then introduce composite graphical models that express information via variables linked by "local" functions, thanks to conditional independence; (3) on these graphical models, we finally define a simple class of queries which can represent various scenarios in terms of observabilities and controllabilities. A natural decision-tree semantics for such queries is completed by an equivalent operational semantics, which induces generic algorithms. The proposed framework, called the Plausibility-Feasibility-Utility (PFU) framework, not only provides a better understanding of the links between existing formalisms, but it also covers yet unpublished frameworks (such as possibilistic influence diagrams) and unifies formalisms such as quantified boolean formulas and influence diagrams. Our backtrack and variable elimination generic algorithms are a first step towards unified algorithms.
APA, Harvard, Vancouver, ISO, and other styles
6

Joshi, S., and R. Khardon. "Probabilistic Relational Planning with First Order Decision Diagrams." Journal of Artificial Intelligence Research 41 (June 21, 2011): 231–66. http://dx.doi.org/10.1613/jair.3205.

Full text
Abstract:
Dynamic programming algorithms have been successfully applied to propositional stochastic planning problems by using compact representations, in particular algebraic decision diagrams, to capture domain dynamics and value functions. Work on symbolic dynamic programming lifted these ideas to first order logic using several representation schemes. Recent work introduced a first order variant of decision diagrams (FODD) and developed a value iteration algorithm for this representation. This paper develops several improvements to the FODD algorithm that make the approach practical. These include, new reduction operators that decrease the size of the representation, several speedup techniques, and techniques for value approximation. Incorporating these, the paper presents a planning system, FODD-Planner, for solving relational stochastic planning problems. The system is evaluated on several domains, including problems from the recent international planning competition, and shows competitive performance with top ranking systems. This is the first demonstration of feasibility of this approach and it shows that abstraction through compact representation is a promising approach to stochastic planning.
APA, Harvard, Vancouver, ISO, and other styles
7

Falkowski, B. J., and Chip-Hong Chang. "Efficient calculation of Gray code-ordered Walsh spectra through algebraic decision diagrams." Electronics Letters 34, no. 9 (1998): 848. http://dx.doi.org/10.1049/el:19980606.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

Speck, David, Florian Geißer, and Robert Mattmüller. "Symbolic Planning with Edge-Valued Multi-Valued Decision Diagrams." Proceedings of the International Conference on Automated Planning and Scheduling 28 (June 15, 2018): 250–58. http://dx.doi.org/10.1609/icaps.v28i1.13890.

Full text
Abstract:
Symbolic representations have attracted significant attention in optimal planning. Binary Decision Diagrams (BDDs) form the basis for symbolic search algorithms. Closely related are Algebraic Decision Diagrams (ADDs), used to represent heuristic functions. Also, progress was made in dealing with models that take state-dependent action costs into account. Here, costs are represented as Edge-valued Multi-valued Decision Diagrams (EVMDDs), which can be exponentially more compact than the corresponding ADD representation. However, they were not yet considered for symbolic planning. In this work, we study EVMDD-based symbolic search for optimal planning. We define EVMDD-based representations of state sets and transition relations, and show how to compute the necessary operations required for EVMDD-A*. This EVMDD-based version of symbolic A* generalizes its BDD variant, and allows to solve planning tasks with state-dependent action costs. We prove theoretically that our approach is sound, complete and optimal. Additionally, we present an empirical analysis comparing EVMDD-A* to BDD-A* and explicit A* search. Our results underscore the usefulness of symbolic approaches and the feasibility of dealing with models that go beyond unit costs.
APA, Harvard, Vancouver, ISO, and other styles
9

Van den Broeck, Guy, Ingo Thon, Martijn Van Otterlo, and Luc De Raedt. "DTProbLog: A Decision-Theoretic Probabilistic Prolog." Proceedings of the AAAI Conference on Artificial Intelligence 24, no. 1 (July 4, 2010): 1217–22. http://dx.doi.org/10.1609/aaai.v24i1.7755.

Full text
Abstract:
We introduce DTProbLog, a decision-theoretic extension of Prolog and its probabilistic variant ProbLog. DTProbLog is a simple but expressive probabilistic programming language that allows the modeling of a wide variety of domains, such as viral marketing. In DTProbLog, the utility of a strategy (a particular choice of actions) is defined as the expected reward for its execution in the presence of probabilistic effects. The key contribution of this paper is the introduction of exact, as well as approximate, solvers to compute the optimal strategy for a DTProbLog program and the decision problem it represents, by making use of binary and algebraic decision diagrams. We also report on experimental results that show the effectiveness and the practical usefulness of the approach.
APA, Harvard, Vancouver, ISO, and other styles
10

Friedl, Katalin, and László Kabódi. "Storing the Quantum Fourier Operator in the QuIDD Data Structure." Acta Cybernetica 23, no. 2 (2017): 503–12. http://dx.doi.org/10.14232/actacyb.23.2.2017.5.

Full text
Abstract:
Quantum algorithms can be simulated using classical computers, but the typical time complexity of the simulation is exponential. There are some data structures which can speed up this simulation to make it possible to test these algorithms on classical computers using more than a few qubits. One of them is QuIDD by Viamontes et al., which is an extension of the Algebraic Decision Diagram. In this paper, we examine the matrix of Fourier operator and its QuIDD representation. To utilize the structure of the operator we propose two orderings (reversed column variables and even-odd order), both resulting in smaller data structure than the standard one. After that, we propose a new method of storing the Fourier operator, using a weighted decision diagram that further reduces its size. It should be the topic of subsequent research whether the basic operations can be performed efficiently on this weighted structure.
APA, Harvard, Vancouver, ISO, and other styles
More sources

Dissertations / Theses on the topic "Algebaic Decision Diagram"

1

MOLTENI, MARIA CHIARA. "ON THE SECURITY OF CRYPTOGRAPHIC CIRCUITS:PROTECTION AGAINST PROBING ATTACKS AND PERFORMANCE IMPROVEMENT OF GARBLED CIRCUITS." Doctoral thesis, Università degli Studi di Milano, 2022. http://hdl.handle.net/2434/920426.

Full text
Abstract:
Dealing with secure computation and communication in hardware devices, an attacker that threatens to security of the systems can be of two different types. The first type of attacker is external to the exchange of secret messages and tries to steal some sensitive information. Probing a circuit is a useful technique through which an attacker can derive information correlated with the secret manipulated by a cryptographic circuit. Probing security is the branch of research that tries to devise models, tools and countermeasures against this type of attacks. We define a new methodology that allows to determine if a gadget (i.e., a portion of a circuit) is secure against probing attacks. Moreover, we reason about composability of gadgets, in such a way that also this composition is probing secure. The reasoning is extended also to the case in which glitches are considered, namely when the attacks are mounted when timing hazards are present. The proposed methodology is based on the construction of the Walsh matrix of a Boolean function that describes the operations of the circuit. This method allows reaching an exact solution, but generally needs a lot of computation’s time (mainly for big gadgets). To overcome the problem, we propose to compute the Walsh matrix exploiting the theory and applications of Algebraic Decision Diagrams (ADDs). Different is the case when the malicious part is internal: each party is interested in protecting its own sensitive information from all the others. When the parties are only two, from literature the garbled circuit protocol is a solution that allows to reach a result implying some secrets, without sharing them. The cost of this protocol depends on the number of extit{and} gates in the circuit that implements the Boolean function describing the protocol computations. In this context, we work to reduce the number of multiplications in two classes of particular Boolean functions, called autosymmetric and D-reducible. Moreover, in the context of the garbled circuit protocol, we discuss some innovative solutions to further reduce the protocol's costs, as the application of the 3-valued logic. This logic is an extension of the Boolean one, resulting from the addition of a new element to the set Boolean set ${0,1}$.
APA, Harvard, Vancouver, ISO, and other styles
2

Ng, David. "Modeling circuit-level leakage current using algebraic decision diagrams." 2005. http://link.library.utoronto.ca/eir/EIRdetail.cfm?Resources__ID=370239&T=F.

Full text
APA, Harvard, Vancouver, ISO, and other styles

Books on the topic "Algebaic Decision Diagram"

1

Ng, David. Modeling circuit-level leakage current using algebraic decision diagrams. 2005.

Find full text
APA, Harvard, Vancouver, ISO, and other styles

Book chapters on the topic "Algebaic Decision Diagram"

1

Raddum, Håvard, and Oleksandr Kazymyrov. "Algebraic Attacks Using Binary Decision Diagrams." In Cryptography and Information Security in the Balkans, 40–54. Cham: Springer International Publishing, 2015. http://dx.doi.org/10.1007/978-3-319-21356-9_4.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Atampore, Francis, and Michael Winter. "Relation Algebras, Matrices, and Multi-valued Decision Diagrams." In Relational and Algebraic Methods in Computer Science, 248–63. Berlin, Heidelberg: Springer Berlin Heidelberg, 2012. http://dx.doi.org/10.1007/978-3-642-33314-9_17.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Kim, Kee-Eung, and Thomas Dean. "Solving Factored MDPs with Large Action Space Using Algebraic Decision Diagrams." In Lecture Notes in Computer Science, 80–89. Berlin, Heidelberg: Springer Berlin Heidelberg, 2002. http://dx.doi.org/10.1007/3-540-45683-x_11.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Murtovi, Alnis, Alexander Bainczyk, and Bernhard Steffen. "Forest GUMP: A Tool for Explanation." In Tools and Algorithms for the Construction and Analysis of Systems, 314–31. Cham: Springer International Publishing, 2022. http://dx.doi.org/10.1007/978-3-030-99527-0_17.

Full text
Abstract:
AbstractIn this paper, we present Forest GUMP (for Generalized, Unifying Merge Process) a tool for providing tangible experience with three concepts of explanation. Besides the well-known model explanation and outcome explanation, Forest GUMP also supports class characterization, i.e., the precise characterization of all samples with the same classification. Key technology to achieve these results is algebraic aggregation, i.e., the transformation of a Random Forest into a semantically equivalent, concise white-box representation in terms of Algebraic Decision Diagrams (ADDs). The paper sketches the method and illustrates the use of Forest GUMP along an illustrative example taken from the literature. This way readers should acquire an intuition about the tool, and the way how it should be used to increase the understanding not only of the considered dataset, but also of the character of Random Forests and the ADD technology, here enriched to comprise infeasible path elimination.
APA, Harvard, Vancouver, ISO, and other styles
5

Lazreg, Sami, Maxime Cordy, and Axel Legay. "Verification of Variability-Intensive Stochastic Systems with Statistical Model Checking." In Leveraging Applications of Formal Methods, Verification and Validation. Adaptation and Learning, 448–71. Cham: Springer Nature Switzerland, 2022. http://dx.doi.org/10.1007/978-3-031-19759-8_27.

Full text
Abstract:
AbstractWe propose a simulation-based approach to verify Variability-Intensive Systems (VISs) with stochastic behaviour. Given an LTL formula and a model of the VIS behaviour, our method estimates the probability for each variant to satisfy the formula. This allows us to learn the products of the VIS for which the probability stands above a certain threshold. To achieve this, our method samples VIS executions from all variants at once and keeps track of the occurrence probability of these executions in any given variant. The efficiency of this algorithm relies on Algebraic Decision Diagram (ADD), a dedicated data structure that enables orthogonal treatment of variability, stochasticity and property satisfaction. We implemented our approach as an extension of the ProVeLines model checker. Our experiments validate that our method can produce accurate estimations of the probability for the variants to satisfy the given properties.
APA, Harvard, Vancouver, ISO, and other styles
6

Král’, Danie. "Algebraic and Uniqueness Properties of Parity Ordered Binary Decision Diagrams and Their Generalization." In Lecture Notes in Computer Science, 477–87. Berlin, Heidelberg: Springer Berlin Heidelberg, 2000. http://dx.doi.org/10.1007/3-540-44612-5_43.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

"Algebraic Structures for the Fourier Transform on Finite Groups." In Decision Diagram Techniques for Micro- and Nanoelectronic Design Handbook, 891–95. CRC Press, 2005. http://dx.doi.org/10.1201/9781420037586.axa.

Full text
APA, Harvard, Vancouver, ISO, and other styles

Conference papers on the topic "Algebaic Decision Diagram"

1

Herrmann, Ricardo G., and Leliane N. de Barros. "Algebraic Sentential Decision Diagrams in Symbolic Probabilistic Planning." In 2013 Brazilian Conference on Intelligent Systems (BRACIS). IEEE, 2013. http://dx.doi.org/10.1109/bracis.2013.37.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Xiang, Zhimin, Yongwei Chen, Jin Liu, and Xiaoxiao Wo. "Service Routing Analysis in Optical Network with Algebraic Decision Diagram." In 2015 3rd International Conference on Mechatronics and Industrial Informatics. Paris, France: Atlantis Press, 2015. http://dx.doi.org/10.2991/icmii-15.2015.73.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Jiang, Wei, Siwei Zhou, Luyao Ye, Dongdong Zhao, Jing Tian, W. Eric Wong, and Jianwen Xiang. "An Algebraic Binary Decision Diagram for Analysis of Dynamic Fault Tree." In 2018 5th International Conference on Dependable Systems and Their Applications (DSA). IEEE, 2018. http://dx.doi.org/10.1109/dsa.2018.00018.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Fang, Ying, Tianlong Gu, Liang Chang, and Long Li. "Algebraic Decision Diagram-Based CP-ABE with Constant Secret and Fast Decryption." In 2020 International Conference on Cyber-Enabled Distributed Computing and Knowledge Discovery (CyberC). IEEE, 2020. http://dx.doi.org/10.1109/cyberc49757.2020.00025.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Gulati, K., N. Jayakumar, and S. P. Khatri. "An algebraic decision diagram (ADD) based technique to find leakage histograms of combinational designs." In ISLPED '05. Proceedings of the 2005 International Symposium on Low Power Electronics and Design. IEEE, 2005. http://dx.doi.org/10.1109/lpe.2005.195497.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

Gulati, Kanupriya, Nikhil Jayakumar, and Sunil P. Khatri. "An algebraic decision diagram (ADD) based technique to find leakage histograms of combinational designs." In the 2005 international symposium. New York, New York, USA: ACM Press, 2005. http://dx.doi.org/10.1145/1077603.1077633.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Bobbio, Andrea, and Roberta Terruggia. "Reliability and quality of service in weighted probabilistic networks using Algebraic Decision Diagrams." In 2009 Annual Reliability and Maintainability Symposium (RAMS). IEEE, 2009. http://dx.doi.org/10.1109/rams.2009.4914643.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

Farahmandi, Farimah, Bijan Alizadeh, and Zain Navabi. "Effective Combination of Algebraic Techniques and Decision Diagrams to Formally Verify Large Arithmetic Circuits." In 2014 IEEE Computer Society Annual Symposium on VLSI (ISVLSI). IEEE, 2014. http://dx.doi.org/10.1109/isvlsi.2014.109.

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

Kolb, Samuel, Martin Mladenov, Scott Sanner, Vaishak Belle, and Kristian Kersting. "Efficient Symbolic Integration for Probabilistic Inference." In Twenty-Seventh International Joint Conference on Artificial Intelligence {IJCAI-18}. California: International Joint Conferences on Artificial Intelligence Organization, 2018. http://dx.doi.org/10.24963/ijcai.2018/698.

Full text
Abstract:
Weighted model integration (WMI) extends weighted model counting (WMC) to the integration of functions over mixed discrete-continuous probability spaces. It has shown tremendous promise for solving inference problems in graphical models and probabilistic programs. Yet, state-of-the-art tools for WMI are generally limited either by the range of amenable theories, or in terms of performance. To address both limitations, we propose the use of extended algebraic decision diagrams (XADDs) as a compilation language for WMI. Aside from tackling typical WMI problems, XADDs also enable partial WMI yielding parametrized solutions. To overcome the main roadblock of XADDs -- the computational cost of integration -- we formulate a novel and powerful exact symbolic dynamic programming (SDP) algorithm that seamlessly handles Boolean, integer-valued and real variables, and is able to effectively cache partial computations, unlike its predecessor. Our empirical results demonstrate that these contributions can lead to a significant computational reduction over existing probabilistic inference algorithms.
APA, Harvard, Vancouver, ISO, and other styles
10

Dudek, Jeffrey M., Aditya A. Shrotri, and Moshe Y. Vardi. "DPSampler: Exact Weighted Sampling Using Dynamic Programming." In Thirty-First International Joint Conference on Artificial Intelligence {IJCAI-22}. California: International Joint Conferences on Artificial Intelligence Organization, 2022. http://dx.doi.org/10.24963/ijcai.2022/250.

Full text
Abstract:
The problem of exact weighted sampling of solutions of Boolean formulas has applications in Bayesian inference, testing, and verification. The state-of-the-art approach to sampling involves carefully decomposing the input formula and compiling a data structure called d-DNNF in the process. Recent work in the closely connected field of model counting, however, has shown that smartly composing different subformulas using dynamic programming and Algebraic Decision Diagrams (ADDs) can outperform d-DNNF-style approaches on many benchmarks. In this work, we present a modular algorithm called DPSampler that extends such dynamic-programming techniques to the problem of exact weighted sampling. DPSampler operates in three phases. First, an execution plan in the form of a project-join tree is computed using tree decompositions. Second, the plan is used to compile the input formula into a succinct tree-of-ADDs representation. Third, this tree is traversed to generate a random sample. This decoupling of planning, compilation and sampling phases enables usage of specialized libraries for each purpose in a black-box fashion. Further, our novel ADD-sampling algorithm avoids the need for expensive dynamic memory allocation required in previous work. Extensive experiments over diverse sets of benchmarks show DPSampler is more scalable and versatile than existing approaches.
APA, Harvard, Vancouver, ISO, and other styles
You might also be interested in the extended bibliographies on the topic 'Algebaic Decision Diagram' for particular source types:
Journal articles
We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!

To the bibliography