Search results for "Succinctness"

showing 2 items of 2 documents

Error-Free Affine, Unitary, and Probabilistic OBDDs

2018

We introduce the affine OBDD model and show that zero-error affine OBDDs can be exponentially narrower than bounded-error unitary and probabilistic OBDDs on certain problems. Moreover, we show that Las Vegas unitary and probabilistic OBDDs can be quadratically narrower than deterministic OBDDs. We also obtain the same results for the automata versions of these models.

Discrete mathematicsQuadratic growthLas vegas010102 general mathematicsProbabilistic logic02 engineering and technologyComputer Science::Computational ComplexityComputer Science::Artificial Intelligence01 natural sciencesUnitary stateAutomatonSuccinctnessComputer Science::Logic in Computer Science0202 electrical engineering electronic engineering information engineering020201 artificial intelligence & image processingAffine transformation0101 mathematicsComputer Science::DatabasesZero errorMathematics
researchProduct

Verification of scope-dependent hierarchical state machines

2008

AbstractA hierarchical state machine (Hsm) is a finite state machine where a vertex can either expand to another hierarchical state machine (box) or be a basic vertex (node). Each node is labeled with atomic propositions. We study an extension of such model which allows atomic propositions to label also boxes (Shsm). We show that Shsms can be exponentially more succinct than Shsms and verification is in general harder by an exponential factor. We carefully establish the computational complexity of reachability, cycle detection, and model checking against general Ltl and Ctl specifications. We also discuss some natural and interesting restrictions of the considered problems for which we can …

Model checkingVertex (graph theory)Model checkingFinite-state machineComputational complexity theoryTemporal logicAutomataTheoretical Computer ScienceComputer Science ApplicationsSuccinctnessComputational Theory and MathematicsReachabilityComputer Science::Logic in Computer ScienceHierarchical state machinesTemporal logicCycle detectionAlgorithmComputer Science::DatabasesMathematicsInformation SystemsInformation and Computation
researchProduct