System Development & Implementation
Three defeasible reasoners were developed that given a defeasible implication statement in the form, a ~> b and knowledge base K, returns whether or not the query is entailed by K.

Optimization 1


Power Set

The power set is a combination of all possible subsets. This approach uses conjunctions and disjunctions to combine the power set of statements within a rank into longer but fewer statements. It then uses this power set to determine if a query is entailed by the knowledge base.


Space Complexity

This approach lowered the overall statements that are stored. This changed the space complexity from O(n^2) to O(n). This allowed for more statements to be handled within a single rank.

Optimization 2


Fibonacci Search

This approach is similar to the ternary search however, it uses the Fibonacci sequence to create the search ranges. The search ranges are divided into three parts to locate the element in the data structure.


Time Complexity

This approach is the same time complexity as the ternary search, O(log3n). The approach determines the rank to be removed and uses the power set approach on the rank to check the query against the statements.

Optimization 3


Concurrent Approach

This approach uses the console-application to allow the user to enter a single text file that contains multiple query statements simultaneously instead of each query being done one at a time.


Concurrency & Speedup

The approach divides the queries into three sets of threads and performs the Fibonacci search approach with each set. This allows for a speedup of up to three times faster than doing each query sequentially.

Technologies Used
Java 18.0.2
TweetyProject library 1.20
Apache Maven 3.8.6
Results & Findings

Execution Times Between Optimisations

Execution Times of Power Set Methods

All optimizations are combined to create a fully functional console-application and test different understandings of scalability. The results of the tests showed that the Fibonacci search required more entailment checks within the first two thirds of the knowledge base for larger knowledge bases. However, it did outperform the previous approaches for smaller knowledge bases. The power set approach proved to slightly improve upon the execution times of the previous iteration of the same approach. This is due to the improvement of the space complexity since there is less reading of memory involved.
It is clear that for larger knowledge bases, the overhead of execution times for the Fibonacci search implementation increases because the first two thirds become larger and therefore require more entailment checks. The power set approach shows the importance of space complexity and how it affects execution times. The concurrent approach shows a large improvement for reading in and evaluating multiple queries at a time.
To view the codebase, click GitHub Respository.