On the Expressive Power of Dynamic Logic
We show that "looping" of while-programs can be expressed in Regular First Order Dynamic Logic, disproving a conjecture made by Harel and Pratt. In addition we show that the expressive power of quantifier-free Dynamic Logic increases when nondeterminism is introduced in the programs that a...
| Principais autores: | , |
|---|---|
| Publicado em: |
2023
|
| Acesso em linha: | https://hdl.handle.net/1721.1/148984 |
| _version_ | 1826200795810365440 |
|---|---|
| author | Meyer, Albert R. Winklmann, Karl |
| author_facet | Meyer, Albert R. Winklmann, Karl |
| author_sort | Meyer, Albert R. |
| collection | MIT |
| description | We show that "looping" of while-programs can be expressed in Regular First Order Dynamic Logic, disproving a conjecture made by Harel and Pratt. In addition we show that the expressive power of quantifier-free Dynamic Logic increases when nondeterminism is introduced in the programs that are part of formulae of Dynamic Logic. Allowing Assignments of random values to variables also increases expressive power. |
| first_indexed | 2024-09-23T11:41:55Z |
| id | mit-1721.1/148984 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T11:41:55Z |
| publishDate | 2023 |
| record_format | dspace |
| spelling | mit-1721.1/1489842023-03-30T03:50:32Z On the Expressive Power of Dynamic Logic Meyer, Albert R. Winklmann, Karl We show that "looping" of while-programs can be expressed in Regular First Order Dynamic Logic, disproving a conjecture made by Harel and Pratt. In addition we show that the expressive power of quantifier-free Dynamic Logic increases when nondeterminism is introduced in the programs that are part of formulae of Dynamic Logic. Allowing Assignments of random values to variables also increases expressive power. 2023-03-29T14:15:59Z 2023-03-29T14:15:59Z 1980-02 https://hdl.handle.net/1721.1/148984 6681628 MIT-LCS-TM-157 application/pdf |
| spellingShingle | Meyer, Albert R. Winklmann, Karl On the Expressive Power of Dynamic Logic |
| title | On the Expressive Power of Dynamic Logic |
| title_full | On the Expressive Power of Dynamic Logic |
| title_fullStr | On the Expressive Power of Dynamic Logic |
| title_full_unstemmed | On the Expressive Power of Dynamic Logic |
| title_short | On the Expressive Power of Dynamic Logic |
| title_sort | on the expressive power of dynamic logic |
| url | https://hdl.handle.net/1721.1/148984 |
| work_keys_str_mv | AT meyeralbertr ontheexpressivepowerofdynamiclogic AT winklmannkarl ontheexpressivepowerofdynamiclogic |