On the complexity of checking semantic equivalences between pushdown processes and finite-state processes
type: Item
instance of: scholarly article
title: On the complexity of checking semantic equivalences between pushdown processes and finite-state processes
zbMATH Open document ID: 1194.68162
author: Antonin Kučera
author: Richard M. Mayr
published in: Information and Computation
publication date: 2010-08-18T00:00:00Z
full work available at URL: Kucera Mayr 2010 On the Complexity of Checking Semantic Equivalences between Pushdown Processes and Finite State Processes.pdf
Mathematics Subject Classification ID: 68Q85
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 68Q55
Mathematics Subject Classification ID: 68Q60
zbMATH DE Number: 5772400
zbMATH Keywords: pushdown automata
zbMATH Keywords: verification
zbMATH Keywords: simulation
zbMATH Keywords: bisimulation
MaRDI profile type: Publication
OpenAlex ID: W2129121801
cites work: Tools and Algorithms for the Construction and Analysis of Systems
cites work: Q4551151
cites work: Decidability of bisimulation equivalence for process generating context-free languages
cites work: Process Algebra
cites work: Q4535007
cites work: Verification on infinite structures.
cites work: An elementary bisimulation decision procedure for arbitrary context-free processes
cites work: Graphes canoniques de graphes algébriques
cites work: Bisimulation equivalence is decidable for all context-free processes
cites work: Decidability of model checking for infinite-state concurrent systems
cites work: Model checking LTL with regular valuations for pushdown systems
cites work: Q4551162
cites work: The inclusion problem for simple languages
cites work: A short proof of the decidability of bisimulation for normed BPA- processes
cites work: Q3883467
cites work: A polynomial algorithm for deciding bisimilarity of normed context-free processes
cites work: Q3862379
cites work: Actions speak louder than words: proving bisimilarity for context-free processes
cites work: Undecidability of bisimilarity for Petri nets and some related problems
cites work: Deciding bisimulation-like equivalences with finite-state processes
cites work: Q4270051
cites work: Equivalence-checking on infinite-state systems: Techniques and results
cites work: Undecidability of bisimilarity by defender's forcing
cites work: Results on the propositional \(\mu\)-calculus
cites work: Q4270070
cites work: Simulation preorder over simple process algebras
cites work: Weak bisimilarity between finite-state systems and BPA or normed BPP is decidable in polynomial time
cites work: Q4484513
cites work: Q4673421
cites work: Q4536443
cites work: Q4449204
cites work: Weak bisimilarity and regularity of context-free processes is EXPTIME-hard
cites work: Q3992568
cites work: Q3907077
cites work: The Bisimulation Problem for Equational Graphs of Finite Out-Degree
cites work: Q3395948
cites work: Q4737202
cites work: Q4484512
cites work: Decidability of bisimulation equivalence for normed pushdown processes
cites work: Q4218096
cites work: The linear time -- branching time spectrum. I: The semantics of concrete, sequential processes.
cites work: Q3998976
cites work: Q4472439
cites work: Pushdown processes: Games and model-checking
DOI: 10.1016/J.IC.2010.01.003
description: scientific article; zbMATH DE number 5772400