We introduce a class of trainable nonlinear operators based on semirings that
are suitable for use in neural networks. These operators generalize the
traditional alternation of linear operators with activation functions in neural
networks. Semirings are algebraic structures that describe a generalised
notation of linearity, greatly expanding the range of trainable operators that
can be included in neural networks. In fact, max- or min-pooling operations are
convolutions in the tropical semiring with a fixed kernel.
We perform experiments where we replace the activation functions for
trainable semiring-based operators to show that these are viable operations to
include in fully connected as well as convolutional neural networks (ConvNeXt).
We discuss some of the challenges of replacing traditional activation functions
with trainable semiring activations and the trade-offs of doing so.

基于半环的可训练非线性运算符类用于神经网络，将传统的线性运算符与激活函数进行了推广，替代了传统激活函数的可训练半环激活函数，并在全连接和卷积神经网络中进行了实验，结果表明这些可训练半环激活函数是可行的。

神经网络中的半环激活

Semiring Activation in Neural Networks

We investigate the fine-grained and the parameterized complexity of several
generalizations of binary constraint satisfaction problems (BINARY-CSPs), that
subsume variants of graph colouring problems. Our starting point is the
observation that several algorithmic approaches that resulted in complexity
upper bounds for these problems, share a common structure. We thus explore an
algebraic approach relying on semirings that unifies different generalizations
of BINARY-CSPs (such as the counting, the list, and the weighted versions), and
that facilitates a general algorithmic approach to efficiently solving them.
The latter is inspired by the (component) twin-width parameter introduced by
Bonnet et al., which we generalize via edge-labelled graphs in order to
formulate it to arbitrary binary constraints. We consider input instances with
bounded component twin-width, as well as constraint templates of bounded
component twin-width, and obtain an FPT algorithm as well as an improved,
exponential-time algorithm, for broad classes of binary constraints. We
illustrate the advantages of this framework by instantiating our general
algorithmic approach on several classes of problems (e.g., the $H$-coloring
problem and its variants), and showing that it improves the best complexity
upper bounds in the literature for several well-known problems.

本文研究了二元约束满足问题 (BINARY-CSPs) 的多种推广的复杂性及参数化复杂性，探讨了基于半环的代数方法，提出了组件双宽属性的 generalization。研究表明，在受限制的条件下，该方法在多种问题中取得了优秀算法复杂度上界。

二元 CSP 及其半环泛化的组件双宽度参数

Component twin-width as a parameter for BINARY-CSP and its semiring generalisations

We address the problem of handling provenance information in ELHr ontologies.
We consider a setting recently introduced for ontology-based data access, based
on semirings and extending classical data provenance, in which ontology axioms
are annotated with provenance tokens. A consequence inherits the provenance of
the axioms involved in deriving it, yielding a provenance polynomial as an
annotation. We analyse the semantics for the ELHr case and show that the
presence of conjunctions poses various difficulties for handling provenance,
some of which are mitigated by assuming multiplicative idempotency of the
semiring. Under this assumption, we study three problems: ontology completion
with provenance, computing the set of relevant axioms for a consequence, and
query answering.

本文章针对 ELHr 本体中的溯源信息问题，基于整环和扩展经典数据溯源的本体数据访问，对本体公理进行注释来生成溯源多项式，并分析了 ELHr 案例的语义，揭示如何处理省略符号所带来的种种困难，其中一些困难可以通过假定整环的乘法幂等性来缓解。在此基础上，研究了三个问题：使用溯源信息来生成完整的本体，计算得到与结论相关的公理集，并进行查询回答。