2026-02-06
Furusawa, Hitoshi, Guttmann, Walter, Furusawa, Hitoshi, Guttmann, Walter
Previous work has axiomatised the cardinality operation in relation algebras, which counts the number of edges of an unweighted graph. We generalise the cardinality axioms to Stone relation algebras, which model weighted graphs, and study the relationships between various axioms for cardinality. This results in simpler cardinality axioms also for relation algebras. We give sufficient conditions for the representability of Stone relation algebras and for Stone relation algebras to be relation algebras.
DOI: 10.46298/fi.123472026-01-11
Jurkiewicz, M., Prabucka, K., Jurkiewicz, M., Prabucka, K.
In this paper we construct a new efficient updatable encryption (UE) scheme based on FrodoPKE learning with errors key encapsulation. We analyse the security of the proposed scheme in the backward-leak uni-directional setting within the rand-ind-eu-cpa model. Since the underlying computationally hard problem here is LWE, the scheme is secure against both classical and quantum attacks.
DOI: 10.46298/fi.144252026-01-11
Leśniak, Mateusz, Wroński, Michał, Leśniak, Mateusz, Wroński, Michał
This paper demonstrates that applying spin reversal transformations (SRT), commonly known as a sufficient method for privacy enhancement in problems solved using quantum annealing, does not guarantee privacy for all possible cases. We show how to recover the original problem from the Ising problem obtained using SRT when the resulting problem in Ising form represents the algebraic attack on the $E_0$ stream cipher. A small example illustrates how to retrieve the original problem from that transformed by SRT. Moreover, we show that our method is efficient also for full-scale problems.
DOI: 10.46298/fi.143462025-12-29
Widemann, Baltasar Trancón y, Lepper, Markus, Widemann, Baltasar Trancón y, Lepper, Markus
Units of measure with prefixes and conversion rules are given a formal semantic model in terms of categorial group theory. Basic structures and both natural and contingent semantic operations are defined. Conversion rules are represented as a class of ternary relations with both group-like and category-like properties. A hierarchy of subclasses is explored, each satisfying stronger useful algebraic properties than the preceding, culminating in a direct efficient conversion-by-rewriting algorithm.
DOI: 10.46298/fi.124362025-12-27
Brogni, Anthony, Joosten, Sebastiaan J. C., Brogni, Anthony, Joosten, Sebastiaan J. C.
This paper presents the development of a software tool that enables the translation of first-order predicate logic with at most three variables into relation algebra. The tool was developed using the Z3 theorem prover, leveraging its capabilities to enhance reliability, generate code, and expedite development. The resulting standalone Python program allows users to translate first-order logic formulas into relation algebra, eliminating the need to work with relation algebra explicitly. This paper outlines the theoretical background of first-order logic, relation algebra, and the translation process. It also describes the implementation details, including validation of the software tool using Z3 for testing correctness. By demonstrating the feasibility of utilizing first-order logic as an alternative language for expressing relation algebra, this tool paves the way for integrating first-order logic into tools traditionally relying on relation algebra as input.
DOI: 10.46298/fi.117102025-12-23
Di Lavore, Elena, Leal, Wilmer, de Paiva, Valeria, Di Lavore, Elena, Leal, Wilmer, de Paiva, Valeria
The categorical modeling of Petri nets has received much attention recently. The Dialectica construction has also had its fair share of attention. We revisit the use of the Dialectica construction as a categorical model for Petri nets generalising the original application to suggest that Petri nets with different kinds of transitions can be modelled in the same categorical framework. Transitions representing truth-values, probabilities, rates or multiplicities, evaluated in different algebraic structures called lineales are useful and are modelled here in the same category. We investigate (categorical instances of) this generalised model and its connections to more recent models of categorical nets.
DOI: 10.46298/fi.131252025-10-31
Fruehwirth, Thom, Fruehwirth, Thom
We introduce a just-in-time runtime program transformation strategy based on repeated recursion unfolding. Our online program optimization generates several versions of a recursion differentiated by the minimal number of recursive steps covered. The base case of the recursion is ignored in our technique. Our method is introduced here on the basis of single linear direct recursive rules. When a recursive call is encountered at runtime, first an unfolder creates specializations of the associated recursive rule on-the-fly and then an interpreter applies these rules to the call. Our approach reduces the number of recursive rule applications to its logarithm at the expense of introducing a logarithmic number of generic unfolded rules. We prove correctness of our online optimization technique and determine its time complexity. For recursions which have enough simplifyable unfoldings, a super-linear is possible, i.e. speedup by more than a constant factor. The necessary simplification is problem-specific and has to be provided at compile-time. In our speedup analysis, we prove a sufficient condition as well as a sufficient and necessary condition for super-linear speedup relating the complexity of the recursive steps of the original rule and the unfolded rules. We have implemented an unfolder and meta-interpreter for runtime repeated recursion unfolding with just five rules in Constraint Handling Rules (CHR) embedded in Prolog. We illustrate the feasibility of our approach with simplifications, time complexity results and benchmarks for some basic tractable algorithms. The simplifications require some insight and were derived manually. The runtime improvement quickly reaches several orders of magnitude, consistent with the super-linear speedup predicted by our theorems.
DOI: 10.46298/fi.115472025-10-27
Manuel, Paul, Klavzar, Sandi, Prabha, R., Arokiaraj, Andrew, Manuel, Paul, Klavzar, Sandi, Prabha, R., Arokiaraj, Andrew
A geodesic cover, also known as an isometric path cover, of a graph is a set of geodesics which cover the vertex set of the graph. An edge geodesic cover of a graph is a set of geodesics which cover the edge set of the graph. The geodesic (edge) cover number of a graph is the cardinality of a minimum (edge) geodesic cover. The (edge) geodesic cover problem of a graph is to find the (edge) geodesic cover number of the graph. Surprisingly, only partial solutions for these problems are available for most situations. In this paper we demonstrate that the geodesic cover number of the $r$-dimensional butterfly is $\lceil (2/3)2^r\rceil$ and that its edge geodesic cover number is $2^r$.
DOI: 10.46298/fi.102012025-10-26
Sun, Yali, Zhang, Mingzu, Feng, Xing, Yang, Xing, Sun, Yali, Zhang, Mingzu, Feng, Xing, Yang, Xing
Reliability assessment of interconnection networks is critical to the design and maintenance of multiprocessor systems. The $(n, k)$-enhanced hypercube $Q_{n,k}$, as a variation of the hypercube $Q_{n}$, was proposed by Tzeng and Wei in 1991. As an extension of traditional edge-connectivity, $h$-extra edge-connectivity of a connected graph $G,$ $λ_h(G),$ is an essential parameter for evaluating the reliability of interconnection networks. This article intends to study the $h$-extra edge-connectivity of the $(n,2)$-enhanced hypercube $Q_{n,2}$. Suppose that the link malfunction of an interconnection network $Q_{n,2}$ does not isolate any subnetwork with no more than $h-1$ processors, the minimum number of these possible faulty links concentrates on a constant $2^{n-1}$ for each integer $\lceil\frac{11\times2^{n-1}}{48}\rceil \leq h \leq 2^{n-1}$ and $n\geq 9$. That is, for about $77.083\%$ of values where $h\leq2^{n-1},$ the corresponding $h$-extra edge-connectivity of $Q_{n,2}$, $λ_h(Q_{n,2})$, presents a concentration phenomenon. Moreover, the lower and upper bounds of $h$ mentioned above are both tight.
DOI: 10.46298/fi.134872025-08-29
de'Liguoro, Ugo, Treglia, Riccardo, de'Liguoro, Ugo, Treglia, Riccardo
We study the semantics of an untyped lambda-calculus equipped with operators representing read and write operations from and to a global store. We adopt the monadic approach to model side-effects and treat read and write as algebraic operations over a monad. We introduce operational and denotational semantics and a type assignment system of intersection types and prove that types are invariant under the reduction and expansion of term and state configurations. Finally, we characterize convergent terms via their typings.
DOI: 10.46298/fi.100102025-07-16
Pahlke, Johannes, Sbalzarini, Ivo F., Pahlke, Johannes, Sbalzarini, Ivo F.
We investigate the computational power of particle methods, a well-established class of algorit hms with applications in scientific computing and computer simulation. The computational power of a compute model determines the class of problems it can solve. Automata theory allows describing the computational power of abstract machines (automata) and the problems they can solve. At the top of the Chomsky hierarchy of formal languages and grammars are Turing machines, which resemble the concept on which most modern computers are built. Although particle methods can be interpreted as automata based on their formal definition, their computational power has so far not been studied. We address this by analyzing Turing completeness of particle methods. In particular, we prove two sets of restrictions under which a particle method is still Turing powerful, and we show when it loses Turing powerfulness. This contributes to understanding the theoretical foundations of particle methods and provides insight into the powerfulness of computer simulations.
DOI: 10.46298/fi.112272025-07-05
Choffrut, Christian, Choffrut, Christian
We show that the equational theory of the structure $\langle ω^ω: (x,y)\mapsto x+y, x\mapsto ωx \rangle $ is finitely axiomatizable and give a simple axiom schema when the domain is the set of transfinite ordinals. We give an algorithm that given a pair of terms $(E,F)$ decides in linear time with respect of their common length whether or not $E=F$ is a consequence of the axioms.
DOI: 10.46298/fi.137342025-05-14
Calamoneri, Tiziana, Monti, Angelo, Petroni, Fabrizio, Calamoneri, Tiziana, Monti, Angelo, Petroni, Fabrizio
A graph G is a multi-interval PCG if there exist an edge weighted tree T with non-negative real values and disjoint intervals of the non-negative real half-line such that each node of G is uniquely associated to a leaf of T and there is an edge between two nodes in G if and only if the weighted distance between their corresponding leaves in T lies within any such intervals. If the number of intervals is k, then we call the graph a k-interval-PCG; in symbols, G = k-interval-PCG (T, I1, . . . , Ik). It is known that 2-interval-PCGs do not contain all graphs and the smallest known graph outside this class has 135 nodes. Here we prove that all graphs with at most 8 nodes are 2-interval-PCGs, so doing one step towards the determination of the smallest value of n such that there exists an n node graph that is not a 2-interval-PCG.
2025-05-14
Mielniczuk, Jan, Wawrzeńczyk, Adam, Mielniczuk, Jan, Wawrzeńczyk, Adam
In the paper we argue that performance of the classifiers based on Empirical Risk Minimization (ERM) for positive unlabeled data, which are designed for case-control sampling scheme may significantly deteriorate when applied to a single-sample scenario. We reveal why their behavior depends, in all but very specific cases, on the scenario. Also, we introduce a single-sample case analogue of the popular non-negative risk classifier designed for case-control data and compare its performance with the original proposal. We show that the significant differences occur between them, especiall when half or more positive of observations are labeled. The opposite case when ERM minimizer designed for the case-control case is applied for single-sample data is also considered and similar conclusions are drawn. Taking into account difference of scenarios requires a sole, but crucial, change in the definition of the Empirical Risk.
2025-05-14
Rudi, Ali Gholami, Rudi, Ali Gholami
Given a set of disks in the plane, the goal of the problem studied in this paper is to choose a subset of these disks such that none of its members contains the centre of any other. Each disk not in this subset must be merged with one of its nearby disks that is, increasing the latter's radius. This problem has applications in labelling rotating maps and in visualizing the distribution of entities in static maps. We prove that this problem is NP-hard. We also present an ILP formulation for this problem, and a polynomial-time algorithm for the special case in which the centres of all disks are on a line.
2024-11-10
Baudon, Thaïs, Fuhs, Carsten, Gonnord, Laure, Baudon, Thaïs, Fuhs, Carsten, Gonnord, Laure
We revisit parallel-innermost term rewriting as a model of parallel computation on inductive data structures and provide a corresponding notion of runtime complexity parametric in the size of the start term. We propose automatic techniques to derive both upper and lower bounds on parallel complexity of rewriting that enable a direct reuse of existing techniques for sequential complexity. Our approach to find lower bounds requires confluence of the parallel-innermost rewrite relation, thus we also provide effective sufficient criteria for proving confluence. The applicability and the precision of the method are demonstrated by the relatively light effort in extending the program analysis tool AProVE and by experiments on numerous benchmarks from the literature.
2024-11-10
Auger, David, Cohen, Johanne, Lobstein, Antoine, Auger, David, Cohen, Johanne, Lobstein, Antoine
We introduce a game where players selfishly choose a resource and endure a cost depending on the number of players choosing nearby resources. We model the influences among resources by a weighted graph, directed or not. These games are generalizations of well-known games like Wardrop and congestion games. We study the conditions of equilibria existence and their efficiency if they exist. We conclude with studies of games whose influences among resources can be modelled by simple graphs.
2024-11-10
Guttmann, Walter, Guttmann, Walter
This paper studies how to use relation algebras, which are useful for high-level specification and verification, for proving the correctness of lower-level array-based implementations of algorithms. We give a simple relation-algebraic semantics of read and write operations on associative arrays. The array operations seamlessly integrate with assignments in computation models supporting while-programs. As a result, relation algebras can be used for verifying programs with associative arrays. We verify the correctness of an array-based implementation of disjoint-set forests using the union-by-rank strategy and find operations with path compression, path splitting and path halving. All results are formally proved in Isabelle/HOL. This paper is an extended version of [1].
2024-11-10
Castellani, Ilaria, Dezani-Ciancaglini, Mariangiola, Giannini, Paola, Castellani, Ilaria, Dezani-Ciancaglini, Mariangiola, Giannini, Paola
We propose an interpretation of multiparty sessions with asynchronous communication as Flow Event Structures. We introduce a new notion of global type for asynchronous multiparty sessions, ensuring the expected properties for sessions, including progress. Our global types, which reflect asynchrony more directly than standard global types and are more permissive, are themselves interpreted as Prime Event Structures. The main result is that the Event Structure interpretation of a session is equivalent, when the session is typable, to the Event Structure interpretation of its global type.
2024-11-10
Hakanen, Anni, Yero, Ismael G., Hakanen, Anni, Yero, Ismael G.
This investigation is firstly focused into showing that two metric parameters represent the same object in graph theory. That is, we prove that the multiset resolving sets and the ID-colorings of graphs are the same thing. We also consider some computational and combinatorial problems of the multiset dimension, or equivalently, the ID-number of graphs. We prove that the decision problem concerning finding the multiset dimension of graphs is NP-complete. We consider the multiset dimension of king grids and prove that it is bounded above by 4. We also give a characterization of the strong product graphs with one factor being a complete graph, and whose multiset dimension is not infinite.
2024-11-10
Salo, Ville, Törmä, Ilkka, Salo, Ville, Törmä, Ilkka
We apply automata theory and Karp's minimum mean weight cycle algorithm to minimum density problems in coding theory. Using this method, we find the new upper bound $53/126 \approx 0.4206$ for the minimum density of an identifying code on the infinite hexagonal grid, down from the previous record of $3/7 \approx 0.4286$.
2024-11-10
Hudry, Olivier, Junnila, Ville, Lobstein, Antoine, Hudry, Olivier, Junnila, Ville, Lobstein, Antoine
A set $C$ of vertices in a graph $G=(V,E)$ is an identifying code if it is dominating and any two vertices of $V$ are dominated by distinct sets of codewords. This paper presents a survey of Iiro Honkala's contributions to the study of identifying codes with respect to several aspects: complexity of computing an identifying code, combinatorics in binary Hamming spaces, infinite grids, relationships between identifying codes and usual parameters in graphs, structural properties of graphs admitting identifying codes, and number of optimal identifying codes.
2024-07-08
Golpek, Hande Tuncel, Aytac, Aysun, Golpek, Hande Tuncel, Aytac, Aysun
Analysis of a network in terms of vulnerability is one of the most significant problems. Graph theory serves as a valuable tool for solving complex network problems, and there exist numerous graph-theoretic parameters to analyze the system's stability. Among these parameters, the closeness parameter stands out as one of the most commonly used vulnerability metrics. Its definition has evolved to enhance the ease of formulation and applicability to disconnected structures. Furthermore, based on the closeness parameter, vertex residual closeness, which is a newer and more sensitive parameter compared to other existing parameters, has been introduced as a new graph vulnerability index by Dangalchev. In this study, the outcomes of the closeness and vertex residual closeness parameters in Harary Graphs have been examined. Harary Graphs are well-known constructs that are distinguished by having $n$ vertices that are $k$-connected with the least possible number of edges.
2024-02-12
van der Werf, Jan Martijn E. M., Rivkin, Andrey, Montali, Marco, Polyvyanyy, Artem, van der Werf, Jan Martijn E. M., Rivkin, Andrey, Montali, Marco, Polyvyanyy, Artem
A model of an information system describes its processes and how resources are involved in these processes to manipulate data objects. This paper presents an extension to the Petri nets formalism suitable for describing information systems in which states refer to object instances of predefined types and resources are identified as instances of special object types. Several correctness criteria for resource- and object-aware information systems models are proposed, supplemented with discussions on their decidability for interesting classes of systems. These new correctness criteria can be seen as generalizations of the classical soundness property of workflow models concerned with process control flow correctness.
2023-10-14
Koprowski, Przemysław, Koprowski, Przemysław
We present an explicit algorithmic method for computing square roots in quaternion algebras over global fields of characteristic different from 2.
2023-10-14
Musawi, Seyed Reza, Kiashi, Esameil Nazari, Musawi, Seyed Reza, Kiashi, Esameil Nazari
The Kn\"odel graph $W_{\Delta,n}$ is a $\Delta$-regular bipartition graph on $n\ge 2^{\Delta}$ vertices and $n$ is an even integer. The vertices of $W_{\Delta,n}$ are the pairs $(i,j)$ with $i=1,2$ and $0\le j\le n/2-1$. For every $j$, $0\le j\le n/2-1$, there is an edge between vertex $(1, j)$ and every vertex $(2,(j+2^k-1) \mod (n/2))$, for $k=0,1,\cdots,\Delta-1$. In this paper we obtain some formulas for evaluating the distance of vertices of the Kn\"odel graph and by them, we provide the formula $diam(W_{\Delta,n})=1+\lceil\frac{n-2}{2^{\Delta}-2}\rceil$ for the diameter of $W_{\Delta,n}$, where $n\ge (2\Delta-5)(2^{\Delta}-2)+4$.
2023-10-14
Sälzer, Marco, Lange, Martin, Sälzer, Marco, Lange, Martin
We investigate the complexity of the reachability problem for (deep) neural networks: does it compute valid output given some valid input? It was recently claimed that the problem is NP-complete for general neural networks and specifications over the input/output dimension given by conjunctions of linear inequalities. We recapitulate the proof and repair some flaws in the original upper and lower bound proofs. Motivated by the general result, we show that NP-hardness already holds for restricted classes of simple specifications and neural networks. Allowing for a single hidden layer and an output dimension of one as well as neural networks with just one negative, zero and one positive weight or bias is sufficient to ensure NP-hardness. Additionally, we give a thorough discussion and outlook of possible extensions for this direction of research on neural network verification.
2023-10-14
Mhaskar, Neerja, Smyth, W. F., Mhaskar, Neerja, Smyth, W. F.
The study of strings is an important combinatorial field that precedes the digital computer. Strings can be very long, trillions of letters, so it is important to find compact representations. Here we first survey various forms of one potential compaction methodology, the cover of a given string x, initially proposed in a simple form in 1990, but increasingly of interest as more sophisticated variants have been discovered. We then consider covering by a seed; that is, a cover of a superstring of x. We conclude with many proposals for research directions that could make significant contributions to string processing in future.
2023-09-21
Gerard, Yan, Gerard, Yan
We consider a class of problems of Discrete Tomography which has been deeply investigated in the past: the reconstruction of convex lattice sets from their horizontal and/or vertical X-rays, i.e. from the number of points in a sequence of consecutive horizontal and vertical lines. The reconstruction of the HV-convex polyominoes works usually in two steps, first the filling step consisting in filling operations, second the convex aggregation of the switching components. We prove three results about the convex aggregation step: (1) The convex aggregation step used for the reconstruction of HV-convex polyominoes does not always provide a solution. The example yielding to this result is called \textit{the bad guy} and disproves a conjecture of the domain. (2) The reconstruction of a digital convex lattice set from only one X-ray can be performed in polynomial time. We prove it by encoding the convex aggregation problem in a Directed Acyclic Graph. (3) With the same strategy, we prove that the reconstruction of fat digital convex sets from their horizontal and vertical X-rays can be solved in polynomial time. Fatness is a property of the digital convex sets regarding the relative position of the left, right, top and bottom points of the set. The complexity of the reconstruction of the lattice sets which are not fat remains an open question.
2023-09-21
Ceko, M., Hajdu, L., Tijdeman, R., Ceko, M., Hajdu, L., Tijdeman, R.
Discrete tomography focuses on the reconstruction of functions $f: A \to \mathbb{R}$ from their line sums in a finite number $d$ of directions, where $A$ is a finite subset of $\mathbb{Z}^2$. Consequently, the techniques of discrete tomography often find application in areas where only a small number of projections are available. In 1978 M.B. Katz gave a necessary and sufficient condition for the uniqueness of the solution. Since then, several reconstruction methods have been introduced. Recently Pagani and Tijdeman developed a fast method to reconstruct $f$ if it is uniquely determined. Subsequently Ceko, Pagani and Tijdeman extended the method to the reconstruction of a function with the same line sums of $f$ in the general case. Up to here we assumed that the line sums are exact. In this paper we investigate the case where a small number of line sums are incorrect as may happen when discrete tomography is applied for data storage or transmission. We show how less than $d/2$ errors can be corrected and that this bound is the best possible.