International Journal of Foundations of Computer Science

We introduce the affine OBDD model and show that zero-error affine OBDDs can be exponentially narrower than bounded-error unitary and probabilistic OBDDs on certain problems. Moreover, we show that Las-Vegas unitary and probabilistic OBDDs can be quadratically narrower than deterministic OBDDs. We also obtain the same results for the automata counterparts of these models.

In this paper, we present a new interconnection topology, called the$(n,k)$-modified-bubble-sort graph, which is a generalization of the modified-bubble-sort graph. Additionally, we show many of its properties, such as its hierarchical structure, vertex transitivity, connectivity, edge-connectivity, super connectivity and super edge-connectivity. The $(n,k)$-modified-bubble-sort graph presents more flexibility than the modified-bubble-sort graph in terms of its major design properties.

Multiply constant-weight codes (MCWCs) were introduced recently to improve the reliability of certain physically unclonable function response. In this paper, two methods of constructing MCWCs are presented following the concatenation methodology. In other words, MCWCs are constructed by concatenating approximate outer codes and inner codes. Besides, several classes of optimal MCWCs are derived from these methods. In the first method, the outer codes are $q$-ary codes and the inner codes are constant-weight codes over $GF(2)$. Furthermore, if the outer code achieves the Plotkin bound and the inner code achieves Johnson bound, then the resulting MCWC is optimal. In the second method, the outer codes are $q$-ary codes and the inner codes are MCWCs. Furthermore, if the outer code achieves the Plotkin bound and the inner code achieves the Johnson bound, then the resulting MCWC is optimal.

We introduce alternate Lucas cubes, a new family of graphs designed as an alternative for the well known Lucas cubes. These interconnection networks are subgraphs of Fibonacci cubes and have a useful fundamental decomposition similar to the one for Fibonacci cubes. The vertices of alternate Lucas cubes are constructed from binary strings that are encodings of Lucas representation of integers. As well as ordinary hypercubes, Fibonacci cubes and Lucas cubes, alternate Lucas cubes have several interesting structural and enumerative properties. In this paper we study some of these properties. Specifically, we give the fundamental decomposition giving the recursive structure, determine the number of edges, number of vertices by weight, the distribution of the degrees; as well as the properties of induced hypercubes, $q$-cube polynomials and maximal hypercube polynomials. We also obtain the irregularity polynomials of this family of graphs, determine the conditions for Hamiltonicity, and calculate metric properties such as the radius, diameter, and the center.

We prove two new effective properties of rational functions over infinite words which are realized by finite state Büchi transducers. Firstly, for each such function $F:{\mathrm{\Sigma }}^{\omega }\to {\mathrm{\Gamma }}^{\omega }$, one can construct a deterministic Büchi automaton ${𝒜}$ accepting a dense ${\mathrm{\Pi }}_2^0$-subset of ${\mathrm{\Sigma }}^{\omega }$ such that the restriction of $F$ to $L({𝒜})$ is continuous. Secondly, we give a new proof of the decidability of the first Baire class for synchronous $\omega$-rational functions from which we get an extension of this result involving the notion of Wadge classes of regular $\omega$-languages.