1 citations · 1 across the 4 of their papers we have counts for
7 papers
Languages given by Finite Automata over the Unary Alphabet
Wojciech Czerwiński, Maciej Dębski, Tomasz Gogasz +5
This paper studies the complexity of operations on finite automata and the complexity of their decision problems when the alphabet is unary. Let denote the maximum of the numbe…
An Exact Algorithm for finding Maximum Induced Matching in Subcubic Graphs
Gordon Hoi, Ammar Fathin Sabili, Frank Stephan
The Maximum Induced Matching problem asks to find the maximum such that, given a graph , can we find a subset of vertices of size for which every vertices …
Improved Algorithms for the General Exact Satisfiability Problem
Gordon Hoi, Frank Stephan
The Exact Satisfiability problem asks if we can find a satisfying assignment to each clause such that exactly one literal in each clause is assigned , while the rest are all ass…
An Improved Exact Algorithm for the Exact Satisfiability Problem
Gordon Hoi
The Exact Satisfiability problem, XSAT, is defined as the problem of finding a satisfying assignment to a formula in CNF such that exactly one literal in each clause is assigne…
A Faster Exact Algorithm to Count X3SAT Solutions
Gordon Hoi, Sanjay Jain, Frank Stephan
The Exact Satisfiability problem, XSAT, is defined as the problem of finding a satisfying assignment to a formula in CNF such that there is exactly one literal in each clause assig…
A Fast Exponential Time Algorithm for Max Hamming Distance X3SAT
Gordon Hoi, Sanjay Jain, Frank Stephan
X3SAT is the problem of whether one can satisfy a given set of clauses with up to three literals such that in every clause, exactly one literal is true and the others are false. A…
Partial functions and domination
C. T. Chong, Gordon Hoi, Frank Stephan +1
The current work introduces the notion of pdominant sets and studies their recursion-theoretic properties. Here a set A is called pdominant iff there is a partial A-recursive funct…