University of Twente Student Theses
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