A Linear Operational Semantics for Termination and Complexity Analysis of ISO Prolog
| Autor: | Carsten Fuhs, Fabian Emmes, Peter Schneider-Kamp, Jürgen Giesl, Thomas Ströder |
|---|---|
| Rok vydání: | 2012 |
| Předmět: |
Computer science
Programming language Exception handling Iso standards computer.software_genre Operational semantics Prolog Action semantics Denotational semantics Well-founded semantics TheoryofComputation_LOGICSANDMEANINGSOFPROGRAMS Computer Science::Logic in Computer Science Computer Science::Programming Languages computer Logic programming computer.programming_language |
| Zdroj: | Logic-Based Program Synthesis and Transformation ISBN: 9783642322105 LOPSTR |
| DOI: | 10.1007/978-3-642-32211-2_16 |
| Popis: | We present a new operational semantics for Prolog which covers all constructs in the corresponding ISO standard (including "non-logical" concepts like cuts, meta-programming, "all solution" predicates, dynamic predicates, and exception handling). In contrast to the classical operational semantics for logic programming, our semantics is linear and not based on search trees. This has the advantage that it is particularly suitable for automated program analyses such as termination and complexity analysis. We prove that our new semantics is equivalent to the ISOProlog semantics, i.e., it computes the same answer substitutions and the derivations in both semantics have essentially the same length. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|