A reduction of security notions in designated confirmer signatures
Since the invention of designated confirmer signatures (DCS), a number of schemes with various properties and different underlying mathematical problems have been developed. Although a considerable amount of work has been dedicated to the design of DCS ...
Relating the extra connectivity and the conditional diagnosability of regular graphs under the comparison model
Extra connectivity and conditional diagnosability are two crucial subjects for a multiprocessor system's ability to tolerate and diagnose faulty processors. The extra connectivity and the conditional diagnosability of many well-known multiprocessor ...
Solving the Many to Many assignment problem by improving the Kuhn-Munkres algorithm with backtracking
The Many to Many (M-M) assignment problem is an important open problem where one task is assigned to many, but different, agents and one agent may undertake many, but different, tasks. The Kuhn-Munkres (K-M) algorithm is a famous and traditional process ...
Computing equality-free and repetitive string factorisations
For a string w, a factorisation is any tuple ( u 1 , u 2 , , u k ) of strings that satisfies w = u 1 u 2 u k . A factorisation is called equality-free if each two factors are different, its size is the number of factors (counting each occurrence of ...
Input-driven languages are linear conjunctive
Linear conjunctive grammars define the same family of languages as one-way real-time cellular automata (A. Okhotin, "On the equivalence of linear conjunctive grammars to trellis automata", RAIRO ITA, 2004), and this family is known to be incomparable ...
Quantified conjunctive queries on partially ordered sets
We study the computational problem of checking whether a quantified conjunctive query (a first-order sentence built using only conjunction as Boolean connective) is true in a finite poset (a reflexive, antisymmetric, and transitive directed graph). We ...
Complexity of reversible circuits and their quantum implementations
We provide an extensive overview of upper bounds on the number of gates needed in reversible and quantum circuits. As reversible gate libraries we consider single-target gates, mixed-polarity multiple-controlled Toffoli gates, and the set consisting of ...
Extended dualization
The dualization in arbitrary posets is a well-studied problem in combinatorial enumeration and is a crucial step in many applications in logics, databases, artificial intelligence and pattern mining.The objective of this paper is to study reductions of ...
Hierarchical complexity of 2-clique-colouring weakly chordal graphs and perfect graphs having cliques of size at least 3
A clique of a graph is a maximal set of vertices of size at least 2 that induces a complete graph. A k-clique-colouring of a graph is a colouring of the vertices with at most k colours such that no clique is monochromatic. Défossez proved that the 2-...
Working in binary protects the repetends of 1/3h
Colussi (2011) described the binary strings that iterate to 1 under the Collatz map.We confirm Colussi's description via elementary methods.Colussi's strings hold the repetends of 1 / 3 h , optionally rotated and replicated.It is only in binary that we ...