Alpha

Alpha is an Answer Set Programming (ASP) system: It reads a logic program (a set of logical rules) and computes the corresponding answer sets. ASP falls into the category of declarative and logic programming. Its applications are solving combinatorial problems, but it also is a good tool for reasoning in the context of knowledge-representation and databases.

Alpha is the successor of OMiGA and currently in development. In contrast to many other ASP systems, Alpha implements a lazy-grounding approach in hopes of overcoming memory constraints when working with large input.

Alpha is not the fastest system available, since its goal is not to be the fastest system with current technology but to explore new technologies rapidly. Those technologies, like lazy-grounding, allow Alpha to succeed where other ASP systems fail completely. The project deliberately chooses to trade shorter execution times (which would be possible by using unmanaged runtimes, e.g. C/C++, and low-level optimization) for a more straight forward system design and possibilities to interface with the ecosystem built around the Java Virtual Machine.

Getting Started

Download a current version of the distribution jar (alpha-cli-app-${version}-bundled.jar) from Releases and save it as alpha.jar for convenience.

Running Alpha is as simple as running any other JAR:

bash $ java -jar alpha.jar

Example Usage

Solve 3-colorability for some benchmarking instance and filter for color predicates:

bash $ java -jar alpha.jar -i benchmarks/omiga/omiga-testcases/3col/3col-10-18.txt -fblue -fred -fgreen

Note that in this example the path to the input file is relative to the root of this repository. If you have not checked out the repository, you can just download the example file from GitHub.

A coder's guide to answer set programming provides a short and high-level tutorial on Answer Set Programming.

Building

Alpha uses the Gradle build automation system. Executing

bash $ ./gradlew build

will automatically fetch all dependencies (declared in build.gradle.kts) and compile the project.

Artifacts generated will be placed in the build/ subfolder of the respective module. Most notably you'll find files ready for distribution at alpha-cli-app/build/distributions/. They contain archives which in turn contain a bin/ directory with scripts to run Alpha on Linux and Windows.

If you want to generate a JAR file to be run standalone, execute

bash $ ./gradlew alpha-cli-app:bundledJar

and pick up alpha-cli-app/build/libs/alpha-cli-app-${version}-bundled.jar.

A Note on IDEs

We have contributors using IntelliJ IDEA as well as Eclipse IDE. However, we decided to not check in files related to project configuration. For both tools, standard features to "import" the project based on its Gradle build configuration are available, and they will infer sane defaults. If you run into trouble feel free to file an issue.

Suggested Reading

Beginners' Tutorials

• A coder's guide to answer set programming

Theoretical Background and Language Specification

• Answer Set Programming: A Primer
• ASP-Core-2 Input Language Format
• Conflict-Driven Answer Set Solving: From Theory to Practice
• Learning Non-Ground Rules for Answer-Set Solving

Research Papers on Alpha

Peer-reviewed publications part of journals, conferences and workshops:

2021

• Solving Configuration Problems with ASP and Declarative Domain-Specific Heuristics

2020

• Conflict Generalisation in ASP: Learning Correct and Effective Non-Ground Constraints
• Advancing Lazy-Grounding ASP Solving Techniques - Restarts, Phase Saving, Heuristics, and More

2019

• Exploiting Partial Knowledge in Declarative Domain-Specific Heuristics for ASP (supplementary material)
• Degrees of Laziness in Grounding: Effects of Lazy-Grounding Strategies on ASP Solving (preprint | supplementary material)

2018

• Exploiting Justifications for Lazy Grounding of Answer Set Programs
• Lazy Grounding for Dynamic Configuration: Efficient Large-Scale (Re)Configuration of Cyber-Physical Systems with ASP

2017

• Blending Lazy-Grounding and CDNL Search for Answer-Set Solving (preprint)
• Introducing Heuristics for Lazy-Grounding ASP Solving
• Lazy-Grounding for Answer Set Programs with External Source Access
• Techniques for Efficient Lazy-Grounding ASP Solving (technical report)

Others (e.g. non-peer-reviewed publications, less formal articles, newsletters):

• The Alpha Solver for Lazy-Grounding Answer-Set Programming

Similar Work

• Smodels, a solver usually used in conjunction with lparse.
• DLV
• ASPeRiX, a solver that implements grounding-on-the-fly.