Relating Answer Set Programming and Many-sorted Logics for Formal Verification

• URL: http://arxiv.org/abs/2502.09230v1
• Date: Thu, 13 Feb 2025 11:52:40 GMT
• Title: Relating Answer Set Programming and Many-sorted Logics for Formal Verification
• Authors: Zachary Hansen,
• Abstract summary: My research agenda has been focused on addressing three issues with the intention of making ASP verification an accessible, routine task. I have investigated alternative semantics for ASP based on translations into the logic of here-and-there and many-sorted first-order logic. These semantics promote a modular understanding of logic programs, bypass grounding, and enable us to use automated theorem provers to automatically verify properties of programs.
• Score: 1.223779595809275
• License:
• Abstract: Answer Set Programming (ASP) is an important logic programming paradigm within the field of Knowledge Representation and Reasoning. As a concise, human-readable, declarative language, ASP is an excellent tool for developing trustworthy (especially, artificially intelligent) software systems. However, formally verifying ASP programs offers some unique challenges, such as 1. a lack of modularity (the meanings of rules are difficult to define in isolation from the enclosing program), 2. the ground-and-solve semantics (the meanings of rules are dependent on the input data with which the program is grounded), and 3. limitations of existing tools. My research agenda has been focused on addressing these three issues with the intention of making ASP verification an accessible, routine task that is regularly performed alongside program development. In this vein, I have investigated alternative semantics for ASP based on translations into the logic of here-and-there and many-sorted first-order logic. These semantics promote a modular understanding of logic programs, bypass grounding, and enable us to use automated theorem provers to automatically verify properties of programs.

Related papers

• Combining Logic with Large Language Models for Automatic Debugging and Repair of ASP Programs [1.0650780147044159]
  FormHe is a tool that combines logic-based techniques and Large Language Models to identify and correct issues in Answer Set Programming submissions. We show that FormHe accurately detects faults in 94% of cases and successfully repairs 58% of incorrect submissions.
  arXiv  Detail & Related papers  (2024-10-28T12:30:48Z)
• Finite Groundings for ASP with Functions: A Journey through Consistency [21.53198582611571]
  It is known that enhancing ASP with function symbols makes basic reasoning problems highly undecidable. We show reductions that give an intuition for the high level of undecidability. These insights allow for a more fine-grained analysis where we characterize ASP programs as "frugal" and "non-proliferous"
  arXiv  Detail & Related papers  (2024-05-08T11:50:08Z)
• NExT: Teaching Large Language Models to Reason about Code Execution [50.93581376646064]
  Large language models (LLMs) of code are typically trained on the surface textual form of programs. We propose NExT, a method to teach LLMs to inspect the execution traces of programs and reason about their run-time behavior.
  arXiv  Detail & Related papers  (2024-04-23T01:46:32Z)
• When Do Program-of-Thoughts Work for Reasoning? [51.2699797837818]
  We propose complexity-impacted reasoning score (CIRS) to measure correlation between code and reasoning abilities. Specifically, we use the abstract syntax tree to encode the structural information and calculate logical complexity. Code will be integrated into the EasyInstruct framework at https://github.com/zjunlp/EasyInstruct.
  arXiv  Detail & Related papers  (2023-08-29T17:22:39Z)
• Coupling Large Language Models with Logic Programming for Robust and General Reasoning from Text [5.532477732693001]
  We show that a large language model can serve as a highly effective few-shot semantically. It can convert natural language sentences into a logical form that serves as input for answer set programs. We demonstrate that this method achieves state-of-the-art performance on several benchmarks, including bAbI, StepGame, CLUTRR, and gSCAN.
  arXiv  Detail & Related papers  (2023-07-15T03:29:59Z)
• Fact-Checking Complex Claims with Program-Guided Reasoning [99.7212240712869]
  Program-Guided Fact-Checking (ProgramFC) is a novel fact-checking model that decomposes complex claims into simpler sub-tasks. We first leverage the in-context learning ability of large language models to generate reasoning programs. We execute the program by delegating each sub-task to the corresponding sub-task handler.
  arXiv  Detail & Related papers  (2023-05-22T06:11:15Z)
• Tools and Methodologies for Verifying Answer Set Programs [0.0]
  ASP is a powerful declarative programming paradigm commonly used for solving challenging search and optimization problems. As an approach to Knowledge Representation and Reasoning, ASP benefits from its simplicity, conciseness and rigorously defined semantics. My research is concerned with extending the theory and tools supporting the verification of ASP progams.
  arXiv  Detail & Related papers  (2022-08-05T10:50:21Z)
• Enforcing Consistency in Weakly Supervised Semantic Parsing [68.2211621631765]
  We explore the use of consistency between the output programs for related inputs to reduce the impact of spurious programs. We find that a more consistent formalism leads to improved model performance even without consistency-based training.
  arXiv  Detail & Related papers  (2021-07-13T03:48:04Z)
• How could Neural Networks understand Programs? [67.4217527949013]
  It is difficult to build a model to better understand programs, by either directly applying off-the-shelf NLP pre-training techniques to the source code, or adding features to the model by theshelf. We propose a novel program semantics learning paradigm, that the model should learn from information composed of (1) the representations which align well with the fundamental operations in operational semantics, and (2) the information of environment transition.
  arXiv  Detail & Related papers  (2021-05-10T12:21:42Z)
• A Machine Learning guided Rewriting Approach for ASP Logic Programs [0.0]
  We describe an approach based on Machine Learning (ML) to automatically decide whether to rewrite. In particular, given an ASP program and a set of input facts, our approach chooses whether and how to rewrite input rules based on a set of features measuring their structural properties and domain information.
  arXiv  Detail & Related papers  (2020-09-22T00:51:13Z)
• The ILASP system for Inductive Learning of Answer Set Programs [79.41112438865386]
  Our system learns Answer Set Programs, including normal rules, choice rules and hard and weak constraints. We first give a general overview of ILASP's learning framework and its capabilities. This is followed by a comprehensive summary of the evolution of the ILASP system.
  arXiv  Detail & Related papers  (2020-05-02T19:04:12Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.