We study a presentation of the Khovanov - Lauda - Rouquier's candidate 2-categorification of a quantum group using algebraic rewriting methods. We use a computational approach based on rewriting ...modulo the isotopy axioms of its pivotal structure to compute a family of linear bases for all the vector spaces of 2-cells of this 2-category. We show that these bases correspond to Khovanov and Lauda's conjectured generating sets, proving the non-degeneracy of their diagrammatic calculus. This implies that this 2-category is a categorification of Lusztig's idempotented and integral quantum group Uq(g) associated with a symmetrizable simply-laced Kac-Moody algebra g.
Abstract An algorithm of digital logarithm calculation for the Galois field $$GF(257)$$ G F ( 257 ) is proposed. It is shown that this field is coupled with one of the most important existing ...standards that uses a digital representation of the signal through 256 levels. It is shown that for this case it is advisable to use the specifics of quasi-Mersenne prime numbers, representable in the form $${p=2}^{n}+1$$ p = 2 n + 1 , which includes the number 257. For fields $$GF({2}^{n}+1)$$ G F ( 2 n + 1 ) , an alternating encoding can be used, in which non-zero elements of the field are displayed through binary characters corresponding to the numbers + 1 and − 1. In such an encoding, multiplying a field element by 2 is reduced to a quasi-cyclic permutation of binary symbols (the permuted symbol changes sign). Proposed approach makes it possible to significantly simplify the design of computing devices for calculation of digital logarithm and multiplication of numbers modulo 257. A concrete scheme of a device for digital logarithm calculation in this field is presented. It is also shown that this circuit can be equipped with a universal adder modulo an arbitrary number, which makes it possible to implement any operations in the field under consideration. It is shown that proposed digital algorithm can also be used to reduce 256-valued logic operations to algebraic form. It is shown that the proposed approach is of significant interest for the development of UAV on-board computers operating as part of a group.
Case split is a core proof rule in current decision procedures for the theory of string constraints. Its use is the primary cause of the state space explosion in string constraint solving, since it ...is the only rule that creates branches in the proof tree. Moreover, explicit handling of the case split rule may cause recomputation of the same tasks in multiple branches of the proof tree. In this paper, we propose a symbolic algorithm that significantly reduces such a redundancy. In particular, we encode a string constraint as a regular language and proof rules as rational transducers. This allows us to perform similar steps in the proof tree only once, alleviating the state space explosion. We also extend the encoding to handle arbitrary Boolean combinations of string constraints, length constraints, and regular constraints. In our experimental results, we validate that our technique works in many practical cases where other state-of-the-art solvers fail to provide an answer; our Python prototype implementation solved over 50% of string constraints that could not be solved by the other tools.
•Solving string constraints using regular model checking.•Nielsen transformation using automata and transducers.•Compact encoding of the generated state space.•Provides significant advantage on hard formulae.
Multi-agent pathfinding with continuous time Andreychuk, Anton; Yakovlev, Konstantin; Surynek, Pavel ...
Artificial intelligence,
April 2022, 2022-04-00, 20220401, Volume:
305
Journal Article
Peer reviewed
Open access
Multi-Agent Pathfinding (MAPF) is the problem of finding paths for multiple agents such that each agent reaches its goal and the agents do not collide. In recent years, variants of MAPF have risen in ...a wide range of real-world applications such as warehouse management and autonomous vehicles. Optimizing common MAPF objectives, such as minimizing sum-of-costs or makespan, is computationally intractable, but state-of-the-art algorithms are able to solve optimally problems with dozens of agents. However, most MAPF algorithms assume that (1) time is discretized into time steps and (2) the duration of every action is one time step. These simplifying assumptions limit the applicability of MAPF algorithms in real-world applications and raise non-trivial questions such as how to discretize time in an effective manner. We propose two novel MAPF algorithms for finding optimal solutions that do not rely on any time discretization. In particular, our algorithms do not require quantization of wait and move actions' durations, allowing these durations to take any value required to find optimal solutions. The first algorithm we propose, called Continuous-time Conflict-Based Search (CCBS), draws on ideas from Safe Interval Path Planning (SIPP), a single-agent pathfinding algorithm designed to cope with dynamic obstacles, and Conflict-Based Search (CBS), a state-of-the-art search-based MAPF algorithm. SMT-CCBS builds on similar ideas, but is based on a different state-of-the-art MAPF algorithm called SMT-CBS, which applied a SAT Modulo Theory (SMT) problem-solving procedure. CCBS guarantees to return solutions that have minimal sum-of-costs, while SMT-CCBS guarantees to return solutions that have minimal makespan. We implemented CCBS and SMT-CCBS and evaluated them on grid-based MAPF problems and general graphs (roadmaps). The results show that both algorithms can efficiently solve optimally non-trivial MAPF problems.
Abstract
The concept of one modulo three mean labeling graph is, if there is an injective function
φ
from the vertex set of G to the set {
a
/0 ≤
a
≤ 3
q
− 2
and either a
≡ 0(
mod
3)
or a
≡ 1 (
mod
...3)} where q is the number of edges of G and
φ
induces a bijection
φ
* from the edge set of G to {
a
/1≤
a
≤ 3
q
− 2,
a
≡ 1 (
mod
3) } given by
φ
*
(
u
υ
)
=
φ
(
u
)
+
φ
(
υ
)
2
and the function
φ
is called one modulo three mean labeling of G. In this paper, we obtain the results of one modulo three mean labeling of some several graphs.
We investigate the query evaluation problem for fixed queries over fully dynamic databases, where tuples can be inserted or deleted. The task is to design a dynamic algorithm that immediately reports ...the new result of a fixed query after every database update.
We consider queries in first-order logic (FO) and its extension with modulo-counting quantifiers (FO+MOD) and show that they can be efficiently evaluated under updates, provided that the dynamic database does not exceed a certain degree bound.
In particular, we construct a data structure that allows us to answer a Boolean FO+MOD query and to compute the size of the result of a non-Boolean query within constant time after every database update. Furthermore, after every database update, we can update the data structure in constant time such that afterwards we are able to test within constant time for a given tuple whether or not it belongs to the query result, to enumerate all tuples in the new query result, and to enumerate the difference between the old and the new query result with constant delay between the output tuples. The preprocessing time needed to build the data structure is linear in the size of the database.
Our results extend earlier work on the evaluation of first-order queries on static databases of bounded degree and rely on an effective Hanf normal form for FO+MOD recently obtained by Heimberg, Kuske, and Schweikardt (LICS 2016).
Convergence of an abstract reduction system is the property that the possible derivations from a given initial state all end in the same final state. Relaxing this by “modulo equivalence” means that ...these final states need not be identical, only equivalent wrt. a specified equivalence relation.
We generalize this notion for probabilistic abstract reduction systems, naming it almost-sure convergence modulo equivalence, such that the final states are reached with probability 1. We relate it to the well-studied properties of almost-sure termination and confluence/convergence of probabilistic and non-probabilistic systems. In addition, we provide a transformational approach for proving – or disproving – almost-sure convergence modulo equivalence of given systems.
We provide a Bernoullicity criterion for pk-Lipschitz functions on Zp in van der Put's expansion, and employ it to present a Bernoullicity for a certain class of pk-Lipschitz functions on Zp in ...Mahler's expansion.
PDF
