. "The Complexity of Bisimilarity-Checking for One-Counter Processes"@en . "concurrency; one-counter automata; bisimilarity"@en . "304" . . . "The Complexity of Bisimilarity-Checking for One-Counter Processes"@cs . . . "0304-3975" . . "RIV/00216224:14330/03:00008108!RIV08-MSM-14330___" . "RIV/00216224:14330/03:00008108" . . "157-183" . "The Complexity of Bisimilarity-Checking for One-Counter Processes"@cs . . . . . "We study the problem of bisimilarity-checking between processes of one-counter automata and finite-state processes. We show that deciding weak bisimilarity between processes of one-counter nets and finite-state processes is DP-hard. Then we design an algorithm which decides weak bisimilarity between processes of one-counter automata and finite-state processes in time which is polynomial for a large subclass of instances, giving a kind of characterization of all hard instances as a byproduct."@en . . . "[EFC8B142B942]" . "Theoretical Computer Science" . "27"^^ . "1-3" . "1"^^ . . "We study the problem of bisimilarity-checking between processes of one-counter automata and finite-state processes. We show that deciding weak bisimilarity between processes of one-counter nets and finite-state processes is DP-hard. Then we design an algorithm which decides weak bisimilarity between processes of one-counter automata and finite-state processes in time which is polynomial for a large subclass of instances, giving a kind of characterization of all hard instances as a byproduct." . "The Complexity of Bisimilarity-Checking for One-Counter Processes" . "P(GA201/03/1161), Z(MSM 143300001)" . . "1"^^ . "NL - Nizozemsko" . "We study the problem of bisimilarity-checking between processes of one-counter automata and finite-state processes. We show that deciding weak bisimilarity between processes of one-counter nets and finite-state processes is DP-hard. Then we design an algorithm which decides weak bisimilarity between processes of one-counter automata and finite-state processes in time which is polynomial for a large subclass of instances, giving a kind of characterization of all hard instances as a byproduct."@cs . "601856" . "14330" . "Ku\u010Dera, Anton\u00EDn" . . "The Complexity of Bisimilarity-Checking for One-Counter Processes"@en . "The Complexity of Bisimilarity-Checking for One-Counter Processes" . .