University of Twente Student Theses

Login

Investigating a Zero-One law for Linear Temporal Logic statements in large random graphs

Tretmans, Carmen (2019) Investigating a Zero-One law for Linear Temporal Logic statements in large random graphs.

[img] PDF
4MB
Abstract:This article investigates the existence of a Zero-One law for Linear Temporal Logic in random graphs. A sample statement, Always, formulated in Linear Temporal Logic is tested in four different regimes of directed as well as undirected random graphs. For two of the regimes, the ones with the highest edge probability, the probability of an Always statement to hold tends to zero when the number of nodes of the graph tends to infinity. A Zero-One Law could not be disproved. For the remaining two regimes, when the graph has a tree-like structure, a counterexample of a Zero One law is found for the undirected random graph. For the directed random graph a counterexample in this regime is assumed but not yet proven. In conclusion, a Zero-One law does not hold for Linear Temporal Logic in at least some regimes of random graphs.
Item Type:Essay (Bachelor)
Faculty:EEMCS: Electrical Engineering, Mathematics and Computer Science
Subject:31 mathematics
Programme:Applied Mathematics BSc (56965)
Link to this item:http://purl.utwente.nl/essays/77288
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page