Three Partition Refinement Algorithms
From MaRDI portal
Publication:3801084
DOI10.1137/0216062zbMath0654.68072OpenAlexW2068361557WikidataQ56016785 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
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, Weak bisimilarity between finite-state systems and BPA or normed BPP is decidable in polynomial time, Deriving Bisimulations by Simplifying Partitions, Checking equivalences between concurrent systems of finite agents (Extended abstract), Computing Simulations over Tree Automata, An Incremental Bisimulation Algorithm, An Efficient Algorithm for the Construction of the Equation Tree Automaton, 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, An optimal algorithm to recognize Robinsonian dissimilarities, A general approach to avoiding two by two submatrices, Deciding probabilistic automata weak bisimulation: theory and practice, Structural similarity: spectral methods for relaxed blockmodeling, Characterizations of two classes of digraphs, Reasoning about proportional lumpability, Computing the union join and subset graph of acyclic hypergraphs in subquadratic time, An approximation algorithm for clustering graphs with dominating diametral path, I/O-efficient algorithms for graphs of bounded treewidth, The recognition of geodetically connected graphs, Solving the all-pairs-shortest-length problem on chordal bipartite graphs, Compression of finite-state automata through failure transitions, Backward and forward bisimulation minimization of tree automata, Lumping evolutionary game dynamics on networks, Construction of Aho Corasick automaton in linear time for integer alphabets, Experiments with deterministic \(\omega\)-automata for formulas of linear temporal logic, Arbitrary arrow update logic, On recognition of threshold tolerance graphs and their complements, Locally connected spanning trees in strongly chordal graphs and proper circular-arc graphs, Symbolic models for control systems, Towards the hierarchical verification of reactive systems, An algorithmic view of gene teams, SOS formats and meta-theory: 20 years after, Action emulation, Complexity of equivalence problems for concurrent systems of finite agents, Weak bisimulation for probabilistic timed automata, Partially ordered knapsack and applications to scheduling, A tutorial on EMPA: A theory of concurrent processes with nondeterminism, priorities, probabilities and time, A uniform framework for modeling nondeterministic, probabilistic, stochastic, or mixed processes and their behavioral equivalences, Simulation relations for pattern matching in directed graphs, Translating FSP into LOTOS and networks of automata, Organizing the atoms of the clique separator decomposition into an atom tree, On the greatest solutions to weakly linear systems of fuzzy relation inequalities and equations, Weighted maximum-clique transversal sets of graphs, Clique separator decomposition of hole-free and diamond-free graphs and algorithmic consequences, The tractability frontier for NFA minimization, Arboricity, \(h\)-index, and dynamic algorithms, Bisimulations for fuzzy automata, Nondeterministic automata: equivalence, bisimulations, and uniform relations, Weighted o-minimal hybrid systems, Fast brief practical DFA minimization, Modal transition systems with weight intervals, CCS expressions, finite state processes, and three problems of equivalence, Bisimulation and simulation algorithms on probabilistic transition systems by abstract interpretation, A survey of the algorithmic aspects of modular decomposition, Strongly chordal and chordal bipartite graphs are sandwich monotone, Generalizing the Paige-Tarjan algorithm by abstract interpretation, A succinct canonical register automaton model, Characterizing and computing the structure of clique intersections in strongly chordal graphs, On the tradeoff between compositionality and exactness in weak bisimilarity for integrated-time Markovian process calculi, Computing \(H\)-joins with application to 2-modular decomposition, Minimizing the number of transitions with respect to observation equivalence, Variations of \(Y\)-dominating functions on graphs, The Dilworth number of auto-chordal bipartite graphs, Computing a perfect edge without vertex elimination ordering of a chordal bipartite graph, Polynomial time decision algorithms for probabilistic automata, A simple sub-quadratic algorithm for computing the subset partial order, Using multiset discrimination to solve language processing problems without hashing, Minimisation of acyclic deterministic automata in linear time, Computing maximal weak and other bisimulations, A simple linear time algorithm for the domatic partition problem on strongly chordal graphs, The parallel complexity of coarsest set partition problems, Monge and feasibility sequences in general flow problems, Strong elimination ordering of the total graph of a tree, On bisimulations for description logics, Automatic verification of distributed systems: the process algebra approach., EXPTIME-completeness of thorough refinement on modal transition systems, Deciding bisimilarity is P-complete, Computation of the greatest simulations and bisimulations between fuzzy automata, The algorithmic complexity of mixed domination in graphs, \(H\)-join decomposable graphs and algorithms with runtime single exponential in rankwidth, On the computational complexity of bisimulation, redux, Signed and minus clique-transversal functions on graphs, Fuzzy relation equations and reduction of fuzzy automata, A linear-time algorithm for paired-domination problem in strongly chordal graphs, From tree automata to string automata minimization, On the complexity of signed and minus total domination in graphs, Reduction of fuzzy automata by means of fuzzy quasi-orders, Tempus fugit: How to plug it, Is hyper-extensionality preservable under deletions of graph elements?, From a simple elimination ordering to a strong elimination ordering in linear time, (Bi)simulations up-to characterise process semantics, \(k\)-tuple domination in graphs, Optimal state-space lumping in Markov chains, Hardness of equivalence checking for composed finite-state systems, Fast equation automaton computation, Set constraints and logic programming, Improved algorithms for the multicut and multiflow problems in rooted trees, Sorting in linear time?, Algorithmic aspects of a general modular decomposition theory, Phylogenetic graph models beyond trees, On performance congruences for process algebras, A process algebra with distributed priorities, Probabilistic weak simulation is decidable in polynomial time, An efficient simulation algorithm based on abstract interpretation, Priorities in process algebras, The domatic number problem on some perfect graph families, Finding dominating cliques efficiently, in strongly chordal graphs and undirected path graphs, Stepwise development of process-algebraic specifications in decorated trace semantics, Checking timed Büchi automata emptiness efficiently, 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, Reducing Boolean networks with backward Boolean equivalence, An efficient algorithm to determine probabilistic bisimulation, Stochastic equivalence for performance analysis of concurrent systems in dtsiPBC, Permuting matrices to avoid forbidden submatrices, Priority and abstraction in process algebra, Two Observations in Dioid Based Model Refinement, Injective hulls of various graph classes, Manipulation of regular expressions using derivatives: an overview, Tight lower and upper bounds for the complexity of canonical colour refinement, Applying clique-decomposition for computing Gromov hyperbolicity, Algorithmic aspects of the generalized clique-transversal problem on chordal graphs, On the relations between Markov chain lumpability and reversibility, Computing Behavioral Relations for Probabilistic Concurrent Systems, Symblicit algorithms for mean-payoff and shortest path in monotonic Markov decision processes, All-pairs-shortest-length on strongly chordal graphs, The algorithmic use of hypertree structure and maximum neighbourhood orderings, Design of decentralized critical observers for networks of finite state machines: a formal method approach, Finding a sun in building-free graphs, A tableau construction for finite linear-time temporal logic, Verification of finite-state machines: a distributed approach, A Normal Form for Stateful Connectors, Differential Bisimulation for a Markovian Process Algebra, On the decidability of process equivalences for the \(\pi\)-calculus, Maximum vertex-weighted matching in strongly chordal graphs, On the axiomatisability of priority. III: Priority strikes again, On the complexity of variations of mixed domination on graphs†, Generalizations of suffix arrays to multi-dimensional matrices., Undecidability of domino games and hhp-bisimilarity., A good characterization of squares of strongly chordal split graphs, Variations of maximum-clique transversal sets on graphs, A linear-time algorithm for finding locally connected spanning trees on circular-arc graphs, Positional Dominance: Concepts and Algorithms, Partition refinement of component interaction automata, Deadlock-freedom in component systems with architectural constraints, Counting minimal transversals of \(\beta\)-acyclic hypergraphs, Team equivalences for finite-state machines with silent moves, Strongly orderable graphs. A common generalization of strongly chordal and chordal bipartite graphs, Rainbow domination and related problems on strongly chordal graphs, A logical framework for privacy-preserving social network publication, Deciding bisimilarity and similarity for probabilistic processes., Team bisimilarity, and its associated modal logic, for BPP nets, Mutual transferability for \((F, B, R)\)-domination on strongly chordal graphs and cactus graphs, Deciding orthogonal bisimulation, Forward Bisimulations for Nondeterministic Symbolic Finite Automata, From generic partition refinement to weighted tree automata minimization, A large-scale assessment of exact lumping of quantitative models in the biomodels repository, Computing the Maximum Bisimulation with Spiking Neural P Systems, The complexity of identifying characteristic formulae, Probabilistic Bisimulation and Simulation Algorithms by Abstract Interpretation, Applying model-checking to solve queries on semistructured data, Lumping-based equivalences in Markovian automata: algorithms and applications to product-form analyses, Set graphs. II. Complexity of set graph recognition and similar problems, Complexity of distance paired-domination problem in graphs, On the strong chromatic index and maximum induced matching of tree-cographs, permutation graphs and chordal bipartite graphs, Hermes: a simple and efficient algorithm for building the AOC-poset of a binary relation, Bisimulation relations for weighted automata, Recognition and computation of minimal triangulations for AT-free claw-free and co-comparability graphs, A simple linear time algorithm for cograph recognition, Linear-time modular decomposition of directed graphs, Coalgebraic minimization of HD-automata for the \(\pi\)-calculus using polymorphic types, Fast algorithms for identifying maximal common connected sets of interval graphs, Signed clique-transversal functions in graphs, The degree-preserving spanning tree problem in strongly chordal and directed path graphs, The quest for minimal quotients for probabilistic and Markov automata, An axiomatic semantics for \(\mathsf{ioco} \underline{\mathsf{s}}\) conformance relation, Connection between logical and algebraic approaches to concurrent systems, Aggregation-based minimization of finite state automata, Computation of the greatest right and left invariant fuzzy quasi-orders and fuzzy equivalences, Evaluating the quality of image matrices in blockmodeling, Fast Implementation of the Traveling-Salesman-Problem Method for Reordering Columns within Supernodes, A study on team bisimulation and H-team bisimulation for BPP nets, On list \(k\)-coloring convex bipartite graphs, Quantitative Abstractions for Collective Adaptive Systems, Optimizing Pointer Analysis Using Bisimilarity, Construction of tree automata from regular expressions, Modelling declassification policies using abstract domain completeness, Verification and strategy synthesis for coalition announcement logic, Bisimilarity on basic parallel processes, A complexity analysis of bisimilarity for value-passing processes, AN EFFICIENT FULLY SYMBOLIC BISIMULATION ALGORITHM FOR NON-DETERMINISTIC SYSTEMS, Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing, A reduction technique for weighted grouping problems, Re-describing an algorithm by Hopcroft, Reduced-order observer design for fault diagnosis of Boolean control networks, Canonical derivatives, partial derivatives and finite automaton constructions., Efficiently decomposing, recognizing and triangulating hole-free graphs without diamonds, A partition refinement algorithm for the \(\pi\)-calculus, Iterating transducers, Unwinding biological systems, Employing behavioral preorders to define controllability for nondeterministic discrete-event systems, Compositional verification of asynchronous concurrent systems using CADP, An extension of ERODE to reduce Boolean networks by backward Boolean equivalence, Operational and abstract semantics of the query language G-Log
