The well-known 1-2-3 Conjecture addressed by Karoński, Luczak and Thomason asks whether the edges of every undirected graph G with no isolated edge can be assigned weights from {1, 2, 3} so that the sum of incident weights at each vertex yields a proper vertex-colouring of G. In this work, we consider a similar problem for oriented graphs. We show that the arcs of every oriented graph −G⃗ can be assigned weights from {1, 2, 3} so that every two adjacent vertices of −G⃗ receive distinct sums of outgoing...

This work presents the main features of XFL3, a language for fuzzy system specification, which has been defined as the common description languaje for the tools forming the Xfuzzy 3.0 development environment. Its main advantages are its capability to admit user-defined membership functions, parametric operators, and linguistic hedges. A brief summary of the tools included in Xfuzzy 3.0 and an example illustrating the use of XFL3 are also included.

This paper describes a modification of the power set construction for the transformation of self-verifying nondeterministic finite automata to deterministic ones. Using a set counting argument, the upper bound for this transformation can be lowered from $2^n$ to $O\left(\frac{2^n}{\sqrt{n}}\right).$

We prove that, with high probability, the space complexity of refuting a random unsatisfiable Boolean formula in $k$-CNF on $n$ variables and $m=\Delta n$ clauses is $O\left(n·{\Delta }^{-\frac{1}{k-2}}\right)$.

We prove that, with high probability, the space complexity of refuting a random unsatisfiable Boolean formula in k-CNF on n variables and m = Δn clauses is $O\left(n·{\Delta }^{-\frac{1}{k-2}}\right)$.

To model the dynamics of discrete deterministic systems, we extend the Petri nets framework by a priority relation between conflicting transitions, which is encoded by orienting the edges of a transition conflict graph. The aim of this paper is to gain some insight into the structure of this conflict graph and to characterize a class of suitable orientations by an analysis in the context of hypergraph theory.

Given a groupoid $\langle G,☆\rangle$, and $k\ge 3$, we say that $G$ is antiassociative if an only if for all $x_1,x_2,x_3\in G$, $(x_1☆x_2)☆x_3$ and $x_1☆(x_2☆x_3)$ are never equal. Generalizing this, $\langle G,☆\rangle$ is $k$-antiassociative if and only if for all $x_1,x_2,...,x_k\in G$, any two distinct expressions made by putting parentheses in $x_1☆x_2☆x_3☆\cdots ☆x_k$ are never equal. We prove that for every $k\ge 3$, there exist finite groupoids that are $k$-antiassociative. We then generalize this, investigating when other pairs of groupoid terms can be made never equal.

The paper discusses the application of a similarity metric based on compression to the measurement of the distance among Bulgarian dia- lects. The similarity metric is de ned on the basis of the notion of Kolmo- gorov complexity of a le (or binary string). The application of Kolmogorov complexity in practice is not possible because its calculation over a le is an undecidable problem. Thus, the actual similarity metric is based on a real life compressor which only approximates the Kolmogorov complexity....

Real-time systems are usually modelled with timed automata and real-time requirements relating to the state durations of the system are often specifiable using Linear Duration Invariants, which is a decidable subclass of Duration Calculus formulas. Various algorithms have been developed to check timed automata or real-time automata for linear duration invariants, but each needs complicated preprocessing and exponential calculation. To the best of our knowledge, these algorithms have not been implemented....