Kronecker algebra-based deadlock analysis for railway systems

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, this approach delivers its results faster if constraints are added. In addition, this approach is complete and sound for railway systems, i.e., it generates neither false positives nor false negatives.

• Record URL:
  https://doi.org/10.7307/ptt.v24i5.1171
• Availability:
  • Find a library where document is available. Order URL: http://worldcat.org/issn/03535320
• Authors:
  • Mittermayr, Robert
  • Blieberger, Johann
  • Schobel, Andreas
• Publication Date: 2012

Language

• English

Media Info

• Media Type: Print
• Features: Figures; References; Tables;
• Pagination: pp 359-369
• Serial:
  • PROMET-Traffic & Transportation
  • Volume: 24
  • Issue Number: 5
  • Publisher: University of Zagreb
  • ISSN: 0353-5320
  • EISSN: 1848-4069
  • Serial URL: https://traffic2.fpz.hr/index.php/PROMTT
• Publication flags:

  Open Access (libre)

Subject/Index Terms

• TRT Terms: Algorithms; Mathematical models; Railroads
• Uncontrolled Terms: Kronecker algebra
• Subject Areas: Planning and Forecasting; Railroads; I72: Traffic and Transport Planning;

Filing Info

• Accession Number: 01469855
• Record Type: Publication
• Files: TRIS
• Created Date: Jan 17 2013 1:49PM