"RIV/00216224:14330/04:00010251!RIV08-MSM-14330___" . "Springer-Verlag" . . "probabilistic bisimilarity; probabilistic systems"@en . . "Ku\u010Dera, Anton\u00EDn" . "We prove that probabilistic bisimilarity is decidable over probabilistic extensions of BPA and BPP processes. For normed subclasses of probabilistic BPA and BPP processes we obtain polynomial-time algorithms. Further, we show that probabilistic bisimilarity between probabilistic pushdown automata and finite-state systems is decidable in exponential time. If the number of control states in PDA is bounded by a fixed constant, then the algorithm needs only polynomial time."@en . "16"^^ . . . "Stra\u017Eovsk\u00FD, Old\u0159ich" . "Rozhodnutelnost pravd\u011Bpodobnostn\u00ED bisimulace pro nekone\u010Dn\u011B-stavov\u00E9 pravd\u011Bpodobnostn\u00ED syst\u00E9my"@cs . . "14330" . "Rozhodnutelnost pravd\u011Bpodobnostn\u00ED bisimulace pro nekone\u010Dn\u011B-stavov\u00E9 pravd\u011Bpodobnostn\u00ED syst\u00E9my"@cs . . . "559506" . "We prove that probabilistic bisimilarity is decidable over probabilistic extensions of BPA and BPP processes. For normed subclasses of probabilistic BPA and BPP processes we obtain polynomial-time algorithms. Further, we show that probabilistic bisimilarity between probabilistic pushdown automata and finite-state systems is decidable in exponential time. If the number of control states in PDA is bounded by a fixed constant, then the algorithm needs only polynomial time." . "2004-01-01+01:00"^^ . . . "Proceedings of 15th International Conference on Concurrency Theory (CONCUR 2004)" . "Br\u00E1zdil, Tom\u00E1\u0161" . "Deciding Probabilistic Bisimilarity Over Infinite-State Probabilistic Systems"@en . "RIV/00216224:14330/04:00010251" . "P(GA201/03/1161), Z(MSM 143300001)" . . . "Deciding Probabilistic Bisimilarity Over Infinite-State Probabilistic Systems" . "V \u010Dl\u00E1nku je dok\u00E1z\u00E1no, \u017Ee pravd\u011Bpodobnostn\u00ED bisimulace je rozhodnuteln\u00E1 pro pravd\u011Bpodobnostn\u00ED roz\u0161\u00ED\u0159en\u00ED BPA a BPP proces\u016F. Pro normovan\u00E9 podt\u0159\u00EDdy pravd\u011Bpodobnostn\u00EDch BPA a BPP proces\u016F jsou prezentov\u00E1ny algoritmy, jejich\u017E \u010Dasov\u00E1 slo\u017Eitost je polynomi\u00E1ln\u00ED. D\u00E1le je dok\u00E1z\u00E1no, \u017Ee pravd\u011Bpodobnostn\u00ED bisimulace mezi pravd\u011Bpodobnostn\u00EDmi z\u00E1sobn\u00EDkov\u00FDmi automaty a kone\u010Dn\u011B-stavov\u00FDmi pravd\u011Bpodobnostn\u00EDmi syst\u00E9my je rozhodnuteln\u00E1 v exponenci\u00E1ln\u00EDm \u010Dase. Pokud je po\u010Det kontroln\u00EDch stav\u016F z\u00E1sobn\u00EDkov\u00E9ho automatu omezen fixn\u00ED konstantou, pak je tato \u010Dasov\u00E1 slo\u017Eitost polynomi\u00E1ln\u00ED."@cs . "Deciding Probabilistic Bisimilarity Over Infinite-State Probabilistic Systems" . . "3"^^ . . "August 31 - September 3, 2004, London, UK" . . "[0927D048A72A]" . "3-540-22940-X" . . . . . "Deciding Probabilistic Bisimilarity Over Infinite-State Probabilistic Systems"@en . "3"^^ . "Berlin" . . "193-208" .