On the public citation graph

Deciding bisimilarity is P -complete

https://doi.org/10.1007/bf03180566
0 signed · 97 inferred · view as graph

Inferred edges come from two machine sources: sweeps of open repository metadata (mostly SSRN and Zenodo), and a bulk OpenAlex citation snapshot. Every row below is labelled with the one it came from. Neither is a complete citation index — absence here is not evidence of absence.

Is this your work? Sign in with ORCID and put your name on the claims that are yours.
Claim with ORCID
Reference health. See whether every reference in this work resolves to a known work and none has been retracted — and get a dated CiteStamped badge you can embed.
See reference health

What this work says

Outgoing claims: the papers this work cites, builds on, or argues with.

inferredcites →https://doi.org/10.1007/3-540-10235-3openalex-snapshot
A Calculus of Communicating Systems
inferredcites →https://doi.org/10.1007/3-540-52148-8_3openalex-snapshot
The concurrency workbench
inferredcites →https://doi.org/10.1007/978-3-642-75357-2openalex-snapshot
Structural Complexity II
inferredcites →https://doi.org/10.1007/978-3-642-79235-9openalex-snapshot
Structural Complexity I
inferredcites →https://doi.org/10.1007/978-3-662-25209-3_20openalex-snapshot
Parallel complexity in the design and analysis of concurrent systems
inferredcites →https://doi.org/10.1007/bf01887209openalex-snapshot
Automated analysis of mutual exclusion algorithms using CCS
inferredcites →https://doi.org/10.1007/bfb0017309openalex-snapshot
Concurrency and automata on infinite sequences
inferredcites →https://doi.org/10.1016/0022-0000(90)90022-dopenalex-snapshot
On uniformity within NC1
inferredcites →https://doi.org/10.1016/0890-5401(89)90070-9openalex-snapshot
A complete axiomatisation for observational congruence of finite-state behaviours
inferredcites →https://doi.org/10.1016/0890-5401(90)90025-dopenalex-snapshot
CCS expressions, finite state processes, and three problems of equivalence
inferredcites →https://doi.org/10.1016/b978-0-444-88071-0.50022-9openalex-snapshot
Parallel Algorithms for Shared-Memory Machines
inferredcites →https://doi.org/10.1109/tc.1986.1676783openalex-snapshot
New Classes for Parallel Complexity: A Study of Unification and Other Complete Problems for P
inferredcites →https://doi.org/10.1137/0216062openalex-snapshot
Three Partition Refinement Algorithms
inferredcites →https://doi.org/10.1145/360248.360251openalex-snapshot
Formal verification of parallel programs
inferredcites →https://doi.org/10.1145/76359.76370openalex-snapshot
P-uniform circuit complexity

What points at this work

Incoming claims: where this work appears in other papers’ reference lists and arguments.

inferred← citeshttps://doi.org/10.1006/inco.2001.2920openalex-snapshot
On the Complexity of Verifying Concurrent Transition Systems
inferred← citeshttps://doi.org/10.1007/11690634_19openalex-snapshot
Undecidability Results for Bisimilarity on Prefix Rewrite Systems
inferred← citeshttps://doi.org/10.1007/11874683_6openalex-snapshot
Visibly Pushdown Automata: From Language Equivalence to Simulation and Bisimulation
inferred← citeshttps://doi.org/10.1007/3-540-44450-5_12openalex-snapshot
Fair Equivalence Relations
inferred← citeshttps://doi.org/10.1007/3-540-44622-2_20openalex-snapshot
Axiomatizing the Least Fixed Point Operation and Binary Supremum
inferred← citeshttps://doi.org/10.1007/3-540-44929-9_33openalex-snapshot
On the Complexity of Bisimulation Problems for Pushdown Automata
inferred← citeshttps://doi.org/10.1007/3-540-45022-x_29openalex-snapshot
On the Complexity of Bisimulation Problems for Basic Parallel Processes
inferred← citeshttps://doi.org/10.1007/3-540-45465-9_61openalex-snapshot
Strong Bisimilarity and Regularity of Basic Process Algebra Is PSPACE-Hard
inferred← citeshttps://doi.org/10.1007/3-540-45627-9_29openalex-snapshot
P-Hardness of Equivalence Testing on Finite-State Processes
inferred← citeshttps://doi.org/10.1007/3-540-45694-5_39openalex-snapshot
Why Is Simulation Harder than Bisimulation?
inferred← citeshttps://doi.org/10.1007/3-540-45841-7_44openalex-snapshot
Strong Bisimilarity and Regularity of Basic Parallel Processes Is PSPACE-Hard
inferred← citeshttps://doi.org/10.1007/3-540-46432-8_3openalex-snapshot
Verifying Performance Equivalence for Timed Basic Parallel Processes
inferred← citeshttps://doi.org/10.1007/3-540-61474-5_84openalex-snapshot
Verification of fair transition systems
inferred← citeshttps://doi.org/10.1007/3-540-63045-7_30openalex-snapshot
Capturing bisimulation-invariant Ptime
inferred← citeshttps://doi.org/10.1007/3-540-63141-0_18openalex-snapshot
On the complexity of verifying concurrent transition systems
inferred← citeshttps://doi.org/10.1007/978-3-030-30923-7_1openalex-snapshot
Model Verification Through Dependency Graphs
inferred← citeshttps://doi.org/10.1007/978-3-030-90636-8_7openalex-snapshot
A Linear Parallel Algorithm to Compute Bisimulation and Relational Coarsest Partitions
inferred← citeshttps://doi.org/10.1007/978-3-030-99527-0_9openalex-snapshot
Distributed Coalgebraic Partition Refinement
inferred← citeshttps://doi.org/10.1007/978-3-031-30727-0openalex-snapshot
Complexity of Interaction
inferred← citeshttps://doi.org/10.1007/978-3-031-65633-0_8openalex-snapshot
Bisimulation Learning
inferred← citeshttps://doi.org/10.1007/978-3-031-71112-1_24openalex-snapshot
On the Complexity of Decision Problems for Parameterized Finite State Synchronous Transducers
inferred← citeshttps://doi.org/10.1007/978-3-031-91361-7_6openalex-snapshot
On Bisimulation in Modal Logics for Games on Graphs: An Algorithmic Study
inferred← citeshttps://doi.org/10.1007/978-3-031-98685-7_8openalex-snapshot
Branching Bisimulation Learning
inferred← citeshttps://doi.org/10.1007/978-3-319-47677-3_13openalex-snapshot
Distributed Computation of Fixed Points on Dependency Graphs
inferred← citeshttps://doi.org/10.1007/978-3-319-63121-9_3openalex-snapshot
30 Years of Modal Transition Systems: Survey of Extensions and Analysis
inferred← citeshttps://doi.org/10.1007/978-3-540-39910-0_30openalex-snapshot
Fair Equivalence Relations
inferred← citeshttps://doi.org/10.1007/978-3-540-45138-9_46openalex-snapshot
A Polynomial-Time Algorithm for Deciding True Concurrency Equivalences of Basic Parallel Processes
inferred← citeshttps://doi.org/10.1007/978-3-642-03466-4_7openalex-snapshot
Checking Thorough Refinement on Modal Transition Systems Is EXPTIME-Complete
inferred← citeshttps://doi.org/10.1007/978-3-642-15375-4_13openalex-snapshot
Bisimilarity of One-Counter Processes Is PSPACE-Complete
inferred← citeshttps://doi.org/10.1007/978-3-642-17511-4_8openalex-snapshot
Hardness of Preorder Checking for Basic Formalisms
inferred← citeshttps://doi.org/10.1007/978-3-642-24372-1_20openalex-snapshot
Parametric Modal Transition Systems
inferred← citeshttps://doi.org/10.1007/978-3-642-28729-9_29openalex-snapshot
On the Complexity of Computing Probabilistic Bisimilarity
inferred← citeshttps://doi.org/10.1007/978-3-642-39212-2_23openalex-snapshot
Checking Equality and Regularity for Normed BPA with Silent Moves
inferred← citeshttps://doi.org/10.1007/978-3-662-25209-3_20openalex-snapshot
Parallel complexity in the design and analysis of concurrent systems
inferred← citeshttps://doi.org/10.1007/978-3-662-47666-6_27openalex-snapshot
Compressed Tree Canonization
inferred← citeshttps://doi.org/10.1007/bfb0055622openalex-snapshot
Alternating refinement relations
inferred← citeshttps://doi.org/10.1007/s00236-008-0088-xopenalex-snapshot
Hardness of equivalence checking for composed finite-state systems
inferred← citeshttps://doi.org/10.1007/s00236-015-0215-4openalex-snapshot
Refinement checking on parametric modal transition systems
inferred← citeshttps://doi.org/10.1007/s10009-004-0159-4openalex-snapshot
A distributed algorithm for strong bisimulation reduction of state spaces
inferred← citeshttps://doi.org/10.1007/s10009-020-00578-9openalex-snapshot
Dependency graphs with applications to verification
inferred← citeshttps://doi.org/10.1007/s10270-022-01060-7openalex-snapshot
Linear parallel algorithms to compute strong and branching bisimilarity
inferred← citeshttps://doi.org/10.1007/s11229-012-0215-7openalex-snapshot
Exploring the tractability border in epistemic tasks
inferred← citeshttps://doi.org/10.1007/s11704-021-0340-xopenalex-snapshot
The parametric complexity of bisimulation equivalence of normed pushdown automata
inferred← citeshttps://doi.org/10.1016/0020-0190(91)90224-6openalex-snapshot
The parallel complexity of two problems on concurrency
inferred← citeshttps://doi.org/10.1016/b978-0-444-51624-4.50009-5openalex-snapshot
Concurrency Theory: A Historical Perspective on Coinduction and Process Calculi
inferred← citeshttps://doi.org/10.1016/j.apal.2010.11.001openalex-snapshot
The strength of extensionality II — Weak weak set theories without infinity
inferred← citeshttps://doi.org/10.1016/j.entcs.2004.04.026openalex-snapshot
Weak Bisimilarity and Regularity of Context-Free Processes is EXPTIME-hard
inferred← citeshttps://doi.org/10.1016/j.entcs.2013.09.011openalex-snapshot
A Connection Between Concurrency and Language Theory
inferred← citeshttps://doi.org/10.1016/j.ic.2004.06.003openalex-snapshot
On the computational complexity of bisimulation, redux
inferred← citeshttps://doi.org/10.1016/j.ic.2012.08.001openalex-snapshot
EXPTIME-completeness of thorough refinement on modal transition systems
inferred← citeshttps://doi.org/10.1016/j.ijar.2014.10.001openalex-snapshot
Lattice-valued simulations for quantitative transition systems
inferred← citeshttps://doi.org/10.1016/j.jcss.2013.11.003openalex-snapshot
Bisimulation equivalence and regularity for real-time one-counter automata
inferred← citeshttps://doi.org/10.1016/j.tcs.2004.10.008openalex-snapshot
Weak bisimilarity and regularity of context-free processes is EXPTIME-hard
inferred← citeshttps://doi.org/10.1016/j.tcs.2009.06.009openalex-snapshot
On determinism in modal transition systems
inferred← citeshttps://doi.org/10.1016/j.tcs.2011.08.037openalex-snapshot
Hardness of preorder checking for basic formalisms
inferred← citeshttps://doi.org/10.1016/j.tcs.2020.07.044openalex-snapshot
On the axiomatisability of priority III: Priority strikes again
inferred← citeshttps://doi.org/10.1016/j.tcs.2021.11.027openalex-snapshot
Bisimilarity on Basic Parallel Processes
inferred← citeshttps://doi.org/10.1016/s0304-3975(96)80714-6openalex-snapshot
Deciding bisimulation and trace equivalences for systems with many identical processes
inferred← citeshttps://doi.org/10.1016/s0304-3975(98)00314-4openalex-snapshot
Bisimulation-invariant PTIME and higher-dimensional μ-calculus
inferred← citeshttps://doi.org/10.1016/s1571-0661(05)80390-1openalex-snapshot
A Distributed Algorithm for Strong Bisimulation Reduction of State Spaces
inferred← citeshttps://doi.org/10.1017/cbo9780511792588.004openalex-snapshot
The algorithmics of bisimilarity
inferred← citeshttps://doi.org/10.1093/logcom/exad018openalex-snapshot
Bisimulation in model-changing modal logics: An algorithmic study
inferred← citeshttps://doi.org/10.1109/lics.1994.316075openalex-snapshot
On the parallel complexity of model checking in the modal mu-calculus
inferred← citeshttps://doi.org/10.1109/lics.1998.705674openalex-snapshot
Linear vs. branching time: a complexity-theoretic perspective
inferred← citeshttps://doi.org/10.1109/sct.1991.160267openalex-snapshot
Adaptive logspace and depth-bounded reducibilities
inferred← citeshttps://doi.org/10.1109/sfcs.1996.548485openalex-snapshot
Equivalence in finite-variable logics is complete for polynomial time
inferred← citeshttps://doi.org/10.1142/9789812562494_0054openalex-snapshot
ROADMAP OF INFINITE RESULTS
inferred← citeshttps://doi.org/10.1145/1326554.1326559openalex-snapshot
Undecidability of bisimilarity by defender's forcing
inferred← citeshttps://doi.org/10.1145/1516507.1516510openalex-snapshot
On the origins of bisimulation and coinduction
inferred← citeshttps://doi.org/10.1145/507234.507235openalex-snapshot
Distributed query evaluation on semistructured data
inferred← citeshttps://doi.org/10.1145/778348.778357openalex-snapshot
On the computational complexity of bisimulation, redux
inferred← citeshttps://doi.org/10.1613/jair.5637openalex-snapshot
Bisimulations on Data Graphs
inferred← citeshttps://doi.org/10.2168/lmcs-5(1:2)2009openalex-snapshot
Beyond Language Equivalence on Visibly Pushdown Automata
inferred← citeshttps://doi.org/10.23638/lmcs-13(4:17)2017openalex-snapshot
Branching Bisimilarity of Normed BPA Processes as a Rational Monoid
inferred← citeshttps://doi.org/10.23638/lmcs-14(4:5)2018openalex-snapshot
The Complexity of Bisimulation and Simulation on Finite Systems
inferred← citeshttps://doi.org/10.4204/eptcs.409.13openalex-snapshot
An Evaluation of Massively Parallel Algorithms for DFA Minimization
inferred← citeshttps://doi.org/10.4230/lipics.fsttcs.2012.160openalex-snapshot
On Bisimilarity of Higher-Order Pushdown Automata: Undecidability at Order Two
inferred← citeshttps://doi.org/10.48550/arxiv.1303.0044openalex-snapshot
A connection between concurrency and language theory
inferred← citeshttps://doi.org/10.48550/arxiv.1702.05578openalex-snapshot
Two Lower Bounds for BPA
inferred← citeshttps://doi.org/10.5860/choice.33-3959openalex-snapshot
Limits to parallel computation: P-completeness theory
inferred← citeshttps://doi.org/10.6092/unibo/amsdottorato/1433openalex-snapshot
Expressiveness of Concurrent Languages
inferred← citeshttps://doi.org/10.7146/brics.v7i25.20153openalex-snapshot
Continuous Additive Algebras and Injective Simulations of Synchronization Trees
Editorial review for independent work. ICSAC — the Institute for Complexity Science and Advanced Computing — runs a structured editorial panel for researchers publishing outside journals, and publishes on CiteStamp rails. Submission is free and goes through ORCID: icsacinstitute.org/submit.