A linear time solution to the single function coarsest partition problem
From MaRDI portal
Publication:1063420
DOI10.1016/0304-3975(85)90159-8zbMath0574.68060OpenAlexW2005652416MaRDI QIDQ1063420
Robert Bonic, Robert Paige, Robert Endre Tarjan
Publication date: 1985
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(85)90159-8
Analysis of algorithms and problem complexity (68Q25) Combinatorial aspects of partitions of integers (05A17) Formal languages and automata (68Q45) Discrete mathematics in relation to computer science (68R99)
Related Items
An efficient parallel algorithm for the single function coarsest partition problem, Taming the complexity of biochemical models through bisimulation and collapsing: theory and practice, An efficient algorithm for computing bisimulation equivalence, Mechanical translation of set theoretic problem specifications into efficient RAM code - a case study, Tight lower and upper bounds for the complexity of canonical colour refinement, An efficient algorithm for a special case of the set partition problem, Generalizations of suffix arrays to multi-dimensional matrices., Lowerbounds for Bisimulation by Partition Refinement, Fast parallel Lyndon factorization with applications, On extremal cases of Hopcroft's algorithm, Optimal canonization of all substrings of a string, Standard Sturmian words and automata minimization algorithms, Hopcroft's algorithm and tree-like automata, Using multiset discrimination to solve language processing problems without hashing, Computing the Maximum Bisimulation with Spiking Neural P Systems, The parallel complexity of coarsest set partition problems, Rank-Based Symbolic Bisimulation, Continuant polynomials and worst-case behavior of Hopcroft's minimization algorithm, Hopcroft’s Minimization Technique: Queues or Stacks?, A theory of ultimately periodic languages and automata with an application to time granularity, An Incremental Bisimulation Algorithm, On Extremal Cases of Hopcroft’s Algorithm, Generalizations of suffix arrays to multi-dimensional matrices., AN EFFICIENT FULLY SYMBOLIC BISIMULATION ALGORITHM FOR NON-DETERMINISTIC SYSTEMS, Sorting and doubling techniques for set partitioning and automata minimization problems, Re-describing an algorithm by Hopcroft, A derived algorithm for evaluating \(\varepsilon\)-expressions over abstract sets, Transformational derivation of an improved alias analysis algorithm, An NSF proposal
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Lexicographically least circular substrings
- A lattice-theoretical fixpoint theorem and its applications
- Linear Automaton Transformations
- The promotion and accumulation strategies in transformational programming
- Fast Decision Procedures Based on Congruence Closure
- Variations on the Common Subexpression Problem
- Fast canonization of circular strings
- Satins and Twills: An Introduction to the Geometry of Fabrics
- Finite Differencing of Computable Expressions
- Experience with the SETL Optimizer
- Automatic data structure choice in a language of very high level
- Fast Pattern Matching in Strings
- The Invalidity of Markoff's Schema
