Back to search

University of South Florida

Algorithms and Data Structures for Efficient Timing Analysis of Asynchronous Real-time Systems

Abstract

dc:description

This thesis presents a framework to verify asynchronous real-time systems based on model checking. These systems are modeled by using a common modeling formalism named Labeled Petri-nets(LPNs). In order to verify the real-time systems algorithmically, the zone-based timing analysis method is used for LPNs. It searches the state space with timing information (represented by zones). When there is a high degree of concurrency in the model, firing concurrent enabled transitions in different order may result in different zones, and these zones may be combined without affecting the verification result. Since the zone-based method could not deal with this problem efficiently, the POSET timing analysis method is adopted for LPNs. It separates concurrency from causality and generates an exactly one zone for a single state. But it needs to maintain an extra POSET matrix for each state. In order to save time and memory, an improved zone-based timing analysis method is introduced by integrating above two methods. It searches the state space with zones but eliminates the use of the POSET matrix, which generates the same result as with the POSET method. To illustrate these methods, a circuit example is used throughout the thesis. Since the state space generated is usually very large, a graph data structure named multi-value decision diagrams (MDDs) is implemented to store the zones compactly. In order to share common clock value of dierent zones, two zone encoding methods are described: direct encoding and minimal constraint encoding. They ignore the unnecessary information in zones thus reduce the length of the integer tuples. The effectiveness of these two encoding methods is demonstrated by experimental result of the circuit example.

Degree

thesis:*
Level thesis:degree_level
Thesis
Discipline thesis:degree_discipline
Computer Science and Engineering
Grantor
University of South Florida
Year dc:date
2013

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Zhang, Yingying
Contributors dc:contributor
  • Hao Zheng

Subjects

dc:subject × 8

Rights

Language dc:language
EN-US

Identifiers

dc:identifier.*
Repository record dc:identifier
https://digitalcommons.usf.edu/etd/4622

Chain of custody

source
Harvested from
University of South Florida
Base URL
digitalcommons.usf.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Zhang, Yingying. Algorithms and Data Structures for Efficient Timing Analysis of Asynchronous Real-time Systems. Thesis thesis, University of South Florida, 2013. https://digitalcommons.usf.edu/etd/4622