Three Partition Refinement Algorithms
From MaRDI portal
Publication:3801084
DOI10.1137/0216062zbMath0654.68072DBLPjournals/siamcomp/PaigeT87OpenAlexW2068361557WikidataQ56016785 ScholiaQ56016785MaRDI QIDQ3801084
Robert Paige, Robert Endre Tarjan
Publication date: 1987
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0216062
lexicographic sortingrefinementsorted setsdata structurecoarsest partitiondouble lexical orderingunmerging
Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Data structures (68P05)
Related Items (only showing first 100 items - show all)
An O ( m log n ) Algorithm for Computing Stuttering Equivalence and Branching Bisimulation ⋮ FROM C-CONTINUATIONS TO NEW QUADRATIC ALGORITHMS FOR AUTOMATON SYNTHESIS ⋮ Morphisms and Minimisation of Weighted Automata ⋮ Time abstracted bisimulation: Implicit specifications and decidability ⋮ Minimality Notions via Factorization Systems and Examples ⋮ Diameter, Eccentricities and Distance Oracle Computations on H-Minor Free Graphs and Graphs of Bounded (Distance) Vapnik–Chervonenkis Dimension ⋮ Minimal transition systems for history-preserving bisimulation ⋮ Causality, Behavioural Equivalences, and the Security of Cyberphysical Systems ⋮ Quasifibrations of graphs to find symmetries and reconstruct biological networks ⋮ Quasilinear-time Computation of Generic Modal Witnesses for Behavioural Inequivalence ⋮ Unnamed Item ⋮ Converging from branching to linear metrics on Markov chains ⋮ Strongly Chordal and Chordal Bipartite Graphs Are Sandwich Monotone ⋮ Unnamed Item ⋮ On the decidability of process equivalences for the π-calculus ⋮ On divergence-sensitive weak probabilistic bisimilarity ⋮ Interleaving vs True Concurrency: Some Instructive Security Examples ⋮ A Study on Team Bisimulations for BPP Nets ⋮ An algebraic theory of multiple clocks ⋮ Similarity-First Search: A New Algorithm with Application to Robinsonian Matrix Recognition ⋮ BISIMULATION MINIMIZATION OF TREE AUTOMATA ⋮ Reducing Acyclic Cover Transducers ⋮ An Implementation of Deterministic Tree Automata Minimization ⋮ A linear-time algorithm for semitotal domination in strongly chordal graphs ⋮ Formal lumping of polynomial differential equations through approximate equivalences ⋮ Simulation relations and applications in formal methods ⋮ Lowerbounds for Bisimulation by Partition Refinement ⋮ CARTESIAN PRODUCT PARTITIONING OF MULTI-DIMENSIONAL REACHABLE STATE SPACES ⋮ The parallel complexity of elimination ordering procedures ⋮ Dually chordal graphs ⋮ Subquadratic-time algorithm for the diameter and all eccentricities on median graphs ⋮ Robust stutter bisimulation for abstraction and controller synthesis with disturbance ⋮ Equivalence checking 40 years after: a review of bisimulation tools ⋮ Compatibility of refining and controlling plant automata with bisimulation quotients ⋮ Unnamed Item ⋮ Strong Cocomparability Graphs and Slash-Free Orderings of Matrices ⋮ Compositional Modeling and Minimization of Time-Inhomogeneous Markov Chains ⋮ Unnamed Item ⋮ Bipartite Analogues of Comparability and Cocomparability Graphs ⋮ Selected Ideas Used for Decidability and Undecidability of Bisimilarity ⋮ A Space-Efficient Probabilistic Simulation Algorithm ⋮ On the Minimisation of Acyclic Models ⋮ Towards State Space Reduction Based on T-Lumpability-Consistent Relations ⋮ On deciding some equivalences for concurrent processes ⋮ Generic top-down discrimination for sorting and partitioning in linear time ⋮ Hybrid automata with finite bisimulations ⋮ A process algebra with distributed priorities ⋮ An aperiodic set of 11 Wang tiles ⋮ An O(m log n) algorithm for branching bisimilarity on labelled transition systems ⋮ Causal Semantics for BPP Nets with Silent Moves ⋮ Rank-Based Symbolic Bisimulation ⋮ Distributed Markovian Bisimulation Reduction aimed at CSL Model Checking ⋮ The algorithmic use of hypertree structure and maximum neighbourhood orderings ⋮ A Uniform (Bi-)Simulation-Based Framework for Reducing Tree Automata ⋮ The Secret Life of Keys: On the Calculation of Mechanical Lock Systems ⋮ Minimization of Finite State Automata Through Partition Aggregation ⋮ Equivalence relations for modular performance evaluation in dtsPBC ⋮ Pushdown automata, multiset automata, and Petri nets ⋮ The tool TINA – Construction of abstract state spaces for petri nets and time petri nets ⋮ Unnamed Item ⋮ Modelling and Verifying Mobile Systems Using π-Graphs ⋮ Reasoning About Regular Properties: A Comparative Study ⋮ “On the fly” verification of behavioural equivalences and preorders ⋮ Computing the fuzzy partition corresponding to the greatest fuzzy auto-bisimulation of a fuzzy graph-based structure under the Gödel semantics ⋮ Weak bisimilarity between finite-state systems and BPA or normed BPP is decidable in polynomial time ⋮ A new genetic algorithm encoding for coalition structure generation problems ⋮ Computing \(k\)-bisimulations for large graphs: a comparison and efficiency analysis ⋮ Incremental dead state detection in logarithmic time ⋮ Distributed coalgebraic partition refinement ⋮ Generic partition refinement and weighted tree automata ⋮ Deriving Bisimulations by Simplifying Partitions ⋮ Checking equivalences between concurrent systems of finite agents (Extended abstract) ⋮ Sparse suffix and LCP array: simple, direct, small, and fast ⋮ Incremental NFA minimization ⋮ Decidability results in automata and process theory ⋮ Performance preserving equivalence for stochastic process algebra dtsdPBC ⋮ Relation coarsest partition method to observability of probabilistic Boolean networks ⋮ Computing Simulations over Tree Automata ⋮ An Incremental Bisimulation Algorithm ⋮ An Efficient Algorithm for the Construction of the Equation Tree Automaton ⋮ Two simple but efficient algorithms to recognize Robinson dissimilarities ⋮ Thread algebra for noninterference ⋮ Symbolic computation of differential equivalences ⋮ Bisimilarity Minimization in O(m logn) Time ⋮ COMPOSED BISIMULATION FOR TREE AUTOMATA ⋮ Approximated Reachability on Hybrid Automata: Falsification meets Certification ⋮ Generalizations of suffix arrays to multi-dimensional matrices. ⋮ Efficient Coalgebraic Partition Refinement ⋮ PARTITION REFINEMENT TECHNIQUES: AN INTERESTING ALGORITHMIC TOOL KIT ⋮ Models for machine-part grouping in cellular manufacturing ⋮ Timing-Sensitive Information Flow Analysis for Synchronous Systems ⋮ Improved algorithms for computing the greatest right and left invariant Boolean matrices and their application ⋮ Regular fuzzy equivalences on two - mode fuzzy Networksi ⋮ Doubly lexical ordering of dense 0--1 matrices ⋮ Testing equivalence as a bisimulation equivalence ⋮ COMPLEXITY OF CERTAIN FUNCTIONAL VARIANTS OF TOTAL DOMINATION IN CHORDAL BIPARTITE GRAPHS ⋮ An efficient algorithm for computing bisimulation equivalence ⋮ Verifying persistent security properties ⋮ A space-efficient simulation algorithm on probabilistic automata ⋮ Process Algebra and Model Checking
This page was built for publication: Three Partition Refinement Algorithms
