Back to search

University of Waterloo

Symmetry Reduction and Compositional Verification on Timed Automata

Abstract

dc:description.abstract

This thesis is about techniques for the analysis of concurrent and real-time systems. As the first contribution, we describe a technique that incorporates automatic symmetry detection and symmetry reduction in the analysis of systems modeled by timed automata. First, our approach detects structural symmetries arising from process templates of realtime systems, requiring no additional input from the user. Then, the technique involves finding all variables of type process identifier and computing a set of generators that forms a group of automorphisms. Our technique is fully automatic, and not restricted to fully symmetric systems. The second contribution of this thesis is that we combine elements of compositional proof, abstraction and local symmetry to decide whether a safety property holds for every process instance in a parameterized family of real-time process networks. Analysis is performed on a small cut-off network; that is, a small instance whose compositional proof generalizes to the entire parametric family. Our results show that verification is decidable in time polynomial in the state space of the “cut-off” instance. Then we apply these ideas to analyze Fischer’s protocol, CSMA/CD protocol and Train-Bridge protocol.

Degree

thesis:*
Grantor dc:publisher
University of Waterloo
Year dc:date.issued
2017

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Nguyen, Hoang Linh
Advisor dc:contributor.advisor
  • Trefler, Richard

Subjects

dc:subject × 4

Rights

Language dc:language.iso
en

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/10012/12191

Chain of custody

source
Harvested from
University of Waterloo
Base URL
dspacemainprd01.lib.uwaterloo.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Nguyen, Hoang Linh. Symmetry Reduction and Compositional Verification on Timed Automata. University of Waterloo, 2017. http://hdl.handle.net/10012/12191