Christel Baier
Abstract
Lossy channel systems (LCS's) are systems of finite state processes that communicate via unreliable unbounded fifo channels. We introduce NPLCS's, a variant of LCS's where message losses have a probabilistic behavior while the component processes behave nondeterministically, and study the decidability of qualitative verification problems for ω-regular linear-time properties.
We show that—in contrast to finite-state Markov decision processes—the satisfaction relation for linear-time formulas depends on the type of schedulers that resolve the nondeterminism. While the qualitative model checking problem for the full class of history-dependent schedulers is undecidable, the same question for finite-memory schedulers can be solved algorithmically. Additionally, some special kinds of reachability, or recurrent reachability, qualitative properties yield decidable verification problems for the full class of schedulers, which—for this restricted class of problems—are as powerful as finite-memory schedulers, or even a subclass of them.
- Abdulla, P. A., Baier, C., Purushothaman Iyer, S., and Jonsson, B. 2005a. Simulating perfect channels with probabilistic lossy channels. Inform. Comput. 197, 1--2, 22--40.Google Scholar
Cross Ref
- Abdulla, P. A., Bertrand, N., Rabinovich, A., and Schnoebelen, Ph. 2005b. Verification of probabilistic systems with faulty communication. Inform. Comput. 202, 2, 141--165.Google ScholarDigital Library
- Abdulla, P. A., Čerāns, K., Jonsson, B., and Tsay, Y.-K. 2000. Algorithmic analysis of programs with well quasi-ordered domains. Inform. Comput. 160, 1/2, 109--127.Google Scholar
- Abdulla, P. A., Collomb-Annichini, A., Bouajjani, A., and Jonsson, B. 2004. Using forward reachability analysis for verification of lossy channel systems. Form. Methods Syst. Design 25, 1, 39--65. Google ScholarDigital Library
- Abdulla, P. A. and Jonsson, B. 1996a. Undecidable verification problems for programs with unreliable channels. Inform. Comput. 130, 1, 71--90. Google ScholarDigital Library
- Abdulla, P. A. and Jonsson, B. 1996b. Verifying programs with unreliable channels. Inform. Comput. 127, 2, 91--101.Google ScholarCross Ref
- Baier, C., Bertrand, N., and Schnoebelen, Ph. 2006. A note on the attractor-property of infinite-state Markov chains. Inform. Proces. Lett. 97, 2, 58--63. Google ScholarDigital Library
- Baier, C. and Engelen, B. 1999. Establishing qualitative properties for probabilistic lossy channel systems: An algorithmic approach. In Proceedings of the 5th International AMAST Workshop Formal Methods for Real-Time and Probabilistic Systems (ARTS), Bamberg, Germany. Lecture Notes in Computer Science, vol. 1601. Springer, 34--52. Google ScholarDigital Library
- Bertrand, N. and Schnoebelen, Ph. 2003. Model checking lossy channels systems is probably decidable. In Proceedings of the 6th International Conference on Foundations of Software Science and Computation Structures (FOSSACS), Warsaw, Poland. Lecture Notes in Computer Science, vol. 2620. Springer, 120--135.Google ScholarCross Ref
- Bertrand, N. and Schnoebelen, Ph. 2004. Verifying nondeterministic channel systems with probabilistic message losses. In Proceedings of the 3rd International Workshop on Automated Verification of Infinite-State Systems (AVIS), 2004. Barcelona, Spain. R. Bharadwaj, Ed.Google Scholar
- Brand, D. and Zafiropulo, P. 1983. On communicating finite-state machines. J. ACM 30, 2, 323--342. Google ScholarDigital Library
- Cécé, G., Finkel, A., and Purushothaman Iyer, S. 1996. Unreliable channels are easier to verify than perfect channels. Inform. Comput. 124, 1, 20--31. Google ScholarDigital Library
- Courcoubetis, C. and Yannakakis, M. 1995. The complexity of probabilistic verification. J. ACM 42, 4, 857--907. Google ScholarDigital Library
- Emerson, E. A. 1990. Temporal and modal logic. In Handbook of Theoretical Computer Science, J. v. Leeuwen, Ed. Vol. B. Elsevier Science, Chap. 16, 995--1072. Google ScholarDigital Library
- Finkel, A. 1994. Decidability of the termination problem for completely specificied protocols. Distrib. Comput. 7, 3, 129--135. Google ScholarDigital Library
- Finkel, A. and Schnoebelen, Ph. 2001. Well-structured transition systems everywhere! Theoret. Comput. Sci. 256, 1--2, 63--92. Google ScholarDigital Library
- Grädel, E., Thomas, W., and Wilke, T., Eds. 2002. Automata, Logics, and Infinite Games: A Guide to Current Research. Lecture Notes in Computer Science, vol. 2500. Springer.Google Scholar
- Kemeny, J. G., Snell, J. L., and Knapp, A. W. 1966. Denumerable Markov Chains. D. Van Nostrand Co., Princeton, NJ.Google Scholar
- Masson, B. and Schnoebelen, Ph. 2002. On verifying fair lossy channel systems. In Proceedings of the 27th International Symposium on Mathematical Foundations of Computer Science (MFCS). Warsaw, Poland. Lecture Notes in Computer Science, vol. 2420. Springer, 543--555. Google ScholarDigital Library
- Mayr, R. 2003. Undecidable problems in unreliable computations. Theoret. Comput. Sci. 297, 1--3, 337--354. Google ScholarDigital Library
- Pachl, J. K. 1987. Protocol description and analysis based on a state transition model with channel expressions. In Proceedings of the 7th IFIP WG6.1 International Workshop on Protocol Specification, Testing, and Verification (PSTV). Zurich, Switzerland. North-Holland, 207--219. Google ScholarDigital Library
- Panangaden, P. 2001. Measure and probability for concurrency theorists. Theoret. Comput. Sci. 253, 2, 287--309. Google ScholarDigital Library
- Purushothaman Iyer, S. and Narasimha, M. 1997. Probabilistic lossy channel systems. In Proceedings of the 7th International Joint Conference on Theory and Practice of Software Development (TAPSOFT). Lille, France. Lecture Notes in Computer Science, vol. 1214. Springer, 667--681. Google ScholarDigital Library
- Puterman, M. L. 1994. Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley & Sons. Google ScholarDigital Library
- Rabinovich, A. 2003. Quantitative analysis of probabilistic lossy channel systems. In Proceedings of the 30th International Coll. Automata, Languages, and Programming (ICALP). Eindhoven, NL. Lecture Notes in Computer Science, vol. 2719. Springer, 1008--1021.Google Scholar
- Schnoebelen, Ph. 2001. Bisimulation and other undecidable equivalences for lossy channel systems. In Proceedings of the 4th International Symposium on Theoretical Aspects of Computer Software (TACS). Sendai, Japan. Lecture Notes in Computer Science, vol. 2215. Springer, 385--399. Google ScholarDigital Library
- Schnoebelen, Ph. 2002. Verifying lossy channel systems has nonprimitive recursive complexity. Inform. Proces. Lett. 83, 5, 251--261. Google ScholarDigital Library
- Schnoebelen, Ph. 2004. The verification of probabilistic lossy channel systems. In Validation of Stochastic Systems---A Guide to Current Research, C. Baier et al. Eds. Lecture Notes in Computer Science, vol. 2925. Springer, 445--465.Google Scholar
- Vardi, M. Y. 1985. Automatic verification of probabilistic concurrent finite-state programs. In Proceedings of the 26th Symposium on Foundations of Computer Science (FOCS). Portland, OR. IEEE Computer Society Press, 327--338.Google ScholarDigital Library
- Vardi, M. Y. 1999. Probabilistic linear-time model checking: An overview of the automata-theoretic approach. In Proceedings of the 5th International AMAST Workshop Formal Methods for Real-Time and Probabilistic Systems (ARTS). Bamberg, Germany. Lecture Notes in Computer Science, vol. 1601. Springer, 265--276. Google ScholarDigital Library
Index Terms
- Verifying nondeterministic probabilistic channel systems against ω-regular linear-time properties
Recommendations
Complexity of Topological Properties of Regular ω-Languages
We determine the complexity of topological properties (i.e., properties closed under the Wadge equivalence) of regular ω-languages by showing that they are typically NL-complete (PSPACE-complete) for the deterministic Muller, Mostowski and Büchi ...
Complexity of Topological Properties of Regular ω-Languages
We determine the complexity of topological properties (i.e., properties closed under the Wadge equivalence) of regular ω-languages by showing that they are typically NL-complete (PSPACE-complete) for the deterministic Muller, Mostowski and Büchi ...
Closure properties and descriptional complexity of deterministic regular expressions
We study the descriptional complexity of regular languages that are definable by deterministic regular expressions, i.e., we examine worst-case blow-ups in size when translating between different representations for such languages. As representations of ...
Comments