Robert Mittermayr
Johann Blieberger
Andreas Schöbel
Deadlock analysis for railway systems differs in several aspects from deadlock analysis in computer science. While the problem of deadlock analysis for standard computer systems is well-understood, multi-threaded embedded computer systems pose new challenges. A novel approach in this area can easily be applied to deadlock analysis in the domain of railway systems. The approach is based on Kronecker algebra. A lazy implementation of the matrix operations even allows analysing exponentially sized systems in a very efficient manner. The running time of the algorithm does not depend on the problem size but on the size of the solution. While other approaches suffer from the fact that additional constraints make the problem and its solution harder, our approach delivers its results faster if constraints are added. In addition, our approach is complete and sound for railway systems, i.e., it generates neither false positives nor false negatives.
Stallings, W.: Operating Systems, 4th Ed., Upper Saddle River, New Jersey: Prentice-Hall, 2001
Coffman, E. G. J., Elphick, M. J. and Shoshani, A.: “System deadlocks,” ACM Computing Surveys, Vol. 3, No. 2, pp. 67-78,
Dijkstra, E. W.: “Een algorithme ter voorkoming van de dodelijke omarming (EWD-108)”.
Mittermayr, R. and Blieberger, J.: “Shared Memory Concurrent System Verification using Kronecker Algebra”, 2011. [Online]. Available: http://arxiv.org/abs/1109.5522.
Miller, J.: “Earliest Known Uses of Some of the Words of Mathematics”, 2011. [Online]. Available: http://jeff560.tripod.com/k.html. [Accessed 26 Sept. 2011]
Bellman, R.: Introduction to Matrix Analysis, Classics in Applied Mathematics, 2nd Ed., Society for Industrial and Applied Mathematics, 1997
Graham, A.: Kronecker Products and Matrix Calculus with Applications, New York: Ellis Horwood Ltd., 1981
Davio, M. “Kronecker Products and Shuffle Algebra”, IEEE Trans. Computers,
Guest Editor: Eleonora Papadimitriou, PhD
Editors: Marko Matulin, PhD, Dario Babić, PhD, Marko Ševrović, PhD
The mission of our journal is to provide high quality communication of research results, which is crucial for the effectiveness of scientific research, the promotion of scientific information, new ideas, and original research in the field of traffic and transportation engineering.
1848-4069
0353-5320
Proud publisher
Accelerating Discoveries in Traffic Science |
2024 © Promet - Traffic&Transportation journal
