-
Article
Effective Categoricity of Automatic Equivalence and Nested Equivalence Structures
We study automatic equivalence and nested equivalence structures. The goal is to compare and contrast these automatic structures with computable equivalence and nested equivalence structures. Equivalence struc...
-
Article
A Proof of the Delta Conjecture When \(\varvec{q=0}\)
In Haglund et al. (Trans. Amer. Math. Soc. 370(6):4029–4057, 2018), Haglund, Remmel and Wilson introduce a conjecture which gives a combinatorial prediction for the result of applying a certain operator to an ele...
-
Chapter
p-Rook Numbers and Cycle Counting in \(C_p \wr S_n\)
Cycle-counting rook numbers were introduced by Chung and Graham [J. Combin. Theory Ser. B 65 (1995), 273–290]. Cycle-counting q-rook numbers were introduced by Ehrenborg, Haglund, and Readdy [unpublished] and cyc...
-
Chapter
Paired Patterns in Lattice Paths
Let \(\mathscr {L}_n\) L n ...
-
Article
An iterative algorithm to eliminate edges for traveling salesman problem based on a new binomial distribution
Traveling salesman problem (TSP) is one of the extensively studied NP-hard problems. The recent research showed that the TSP on sparse graphs could be resolved in the relatively shorter computation time than that...
-
Chapter
Injection Structures Specified by Finite State Transducers
An injection structure \({\mathcal A}= (A,f)\) is a set A together with a one-place one-to-one function f.
-
Chapter and Conference Paper
Index Sets for Finite Normal Predicate Logic Programs with Function Symbols
We study the recognition problem in the metaprogramming of finite normal predicate logic programs. That is, let \(\mathcal {L}\) ...
-
Chapter and Conference Paper
Sub-computable Bounded Pseudorandomness
This paper defines a new notion of bounded pseudorandomness for certain classes of sub-computable functions where one does not have access to a universal machine for that class within the class. In particular,...
-
Chapter and Conference Paper
Forward Chaining for Hybrid ASP
In this paper, we define an analogue of the Forward Chaining (FC) algorithm due to Marek, Nerode, and Remmel [12] for Hybrid Answer Set Programming (H-ASP). The FC algorithm for normal logic programs takes as ...
-
Article
Generating Functions for Alternating Descents and Alternating Major Index
In 2008, Chebikin introduced the alternating descent set, AltDes(σ), of a permutation σ = σ 1 ··· σ n in the symmetric group S ...
-
Article
A connection between the Cantor–Bendixson derivative and the well-founded semantics of finite logic programs
Results of Schlipf (J Comput Syst Sci 51:64–86, 1995) and Fitting (Theor Comput Sci 278:25–51, 2001) show that the well-founded semantics of a finite predicate logic program can be quite complex. In this paper, w...
-
Chapter
Disjunctive Programs with Set Constraints
We study an extension of disjunctive logic programs called set constraint disjunctive (SCD) programs where the clauses of the program are allowed to have a disjunction of monotone set constraints in their head an...
-
Article
Open AccessA computational and combinatorial exposé of plethystic calculus
In recent years, plethystic calculus has emerged as a powerful technical tool for studying symmetric polynomials. In particular, some striking recent advances in the theory of Macdonald polynomials have relied...
-
Chapter and Conference Paper
Effective Categoricity of Injection Structures
We study computability theoretic properties of computable injection structures and the complexity of isomorphisms between these structures.
-
Chapter
Effectively Reasoning about Infinite Sets in Answer Set Programming
In answer set programming (ASP), one does not allow the use of function symbols. Disallowing function symbols avoids the problem of having logic programs which have stable models of excessively high complexity...
-
Article
Open AccessA p, q-Analogue of the Generalized Derangement Numbers
In this paper, we study the numbers D n,k which are defined as the number of permutations σ of the symmetric group S ...
-
Article
Space complexity of Abelian groups
We develop a theory of LOGSPACE structures and apply it to construct a number of examples of Abelian Groups which have LOGSPACE presentations. We show that all computable torsion Abelian groups have LOGSPACE pres...
-
Chapter and Conference Paper
\(\Sigma^0_1\) and \(\Pi^0_1\) Equivalence Structures
We study computability theoretic properties of \(\Sigma _{1}^{0}\) and ...
-
Chapter and Conference Paper
Automata and Answer Set Programming
In answer set programming (ASP), one does not allow the use of function symbols. Disallowing function symbols avoids the problem of having logic programs which have stable models of excessively high complexity...
-
Article
My work with Victor Marek: a mathematician looks at answer set programming
We give a brief retrospective of the work of Marek, Nerode, and Remmel on nonmonotonic logic and answer set programming.