In this paper, we deal with hamiltonicity in planar cubic graphs G having a
facial 2-factor Q via (quasi) spanning trees of faces in G/Q and study the
algorithmic complexity of finding such (quasi) spanning trees of faces.
Moreover, we show that if Barnette's Conjecture is false, then hamiltonicity in
3-connected planar cubic bipartite graphs is an NP-complete problem.
Given a subset of $X\subseteq \mathbb{R}^{n}$ we can associate with every
point $x\in \mathbb{R}^{n}$ a vector space $V$ of maximal dimension with the
property that for some ball centered at $x$, the subset $X$ coincides inside
the ball with a union of lines parallel with $V$. A point is singular if $V$
has dimension $0$. In an earlier paper we proved that a $(\mathbb{R}, +,<
,\mathbb{Z})$-definable relation $X$ is actually definable in $(\mathbb{R}, +,<
,1)$ if and only if the number of singular points is finite and every rational
section of $X$ is $(\mathbb{R}, +,< ,1)$-definable, where a rational section is
a set obtained from $X$ by fixing some component to a rational value. Here we
show that we can dispense with the hypothesis of $X$ being $(\mathbb{R}, +,<
,\mathbb{Z})$-definable by assuming that the components of the singular points
are rational numbers. This provides a topological characterization of
first-order definability in the structure $(\mathbb{R}, +,< ,1)$. It also
allows us to deliver a self-definable criterion (in Muchnik's terminology) of
$(\mathbb{R}, +,< ,1)$- and $(\mathbb{R}, +,< ,\mathbb{Z})$-definability for a
wide class of relations, which turns into an effective criterion provided that
the corresponding theory is decidable. In particular these results apply to the
class of $k-$recognizable relations on reals, and allow us to prove that it is
decidable whether a $k-$recognizable relation (of any arity) is
$l-$recognizable for […]
This paper presents the universal address sequence generator (UASG) for
memory built-in-self-test. The studies are based on the proposed universal
method for generating address sequences with the desired properties for
multirun march memory tests. As a mathematical model, a modification of the
recursive relation for quasi-random sequence generation is used. For this
model, a structural diagram of the hardware implementation is given, of which
the basis is a storage device for storing so-called direction numbers of the
generation matrix. The form of the generation matrix determines the basic
properties of the generated address sequences. The proposed UASG generates a
wide spectrum of different address sequences, including the standard ones, such
as linear, address complement, gray code, worst-case gate delay, $2^i$, next
address, and pseudorandom. Examples of the use of the proposed methods are
considered. The result of the practical implementation of the UASG is
presented, and the main characteristics are evaluated.