University of Twente Student Theses
As of Friday, 8 August 2025, the current Student Theses repository is no longer available for thesis uploads. A new Student Theses repository will be available starting Friday, 15 August 2025.
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.
|
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: | https://purl.utwente.nl/essays/77288 |
| Export this item as: | BibTeX EndNote HTML Citation Reference Manager |
Show download statistics for this publication
Show download statistics for this publicationRepository Staff Only: item control page