Some notes on the abstraction operation for multi-terminal binary decision diagrams

DOI10.1007/S10703-013-0198-0MaRDI QIDQ2248099zbMATH OpenOpenAlexFDO

Authors Ludwig Griebl, Johann Schuster

Publication date 30 June 2014

Published in Formal Methods in System Design (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1303.6186

zbMATH Keywords

abstractionabstraction operationalgebraic decision diagrammulti-terminal binary decision diagramswitching function

Mathematics Subject Classification ID

Applications of universal algebra in computer science (08A70) Data structures (68P05) Specification and verification (program logics, model checking, etc.) (68Q60) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Abstract: The starting point of this work are inaccurate statements found in the literature for Multi-terminal Binary Decision Diagrams (MTBDDs) regarding the well-definedness of the MTBDD abstraction operation. The statements try to relate an operation * on a set of terminal values M to the property that the abstraction over this operation does depend on the order of the abstracted variables. This paper gives a necessary and sufficient condition for the independence of the abstraction operation of the order of the abstracted variables in the case of an underlying monoid and it treats the more general setting of a magma.

Recommendations

• Partially-shared zero-suppressed multi-terminal BDDs: Concept, algorithms and applications
• A unifying approach to edge-valued and arithmetic transform decision diagrams
• Binary decision diagrams
• scientific article; zbMATH DE number 1423226
• scientific article; zbMATH DE number 1759447

Cites work

• scientific article; zbMATH DE number 3121644 (Why is no real title available?)
• scientific article; zbMATH DE number 3836338 (Why is no real title available?)
• scientific article; zbMATH DE number 3440338 (Why is no real title available?)
• scientific article; zbMATH DE number 2215847 (Why is no real title available?)
• Über entropische Gruppoide

Describes a project that uses

Uses Software

• PRISM

This page was built for publication: Some notes on the abstraction operation for multi-terminal binary decision diagrams

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2248099)