A string \alpha\in\Sigma^n is called {\it p-periodic},
if for every i,j \in \{1,\dots,n\}, such that i\equiv j \bmod p,
\alpha_i = \alpha_{j}, where \alpha_i is the i-th place of \alpha.
A string \alpha\in\Sigma^n is said to be period(\leq g),
if there exists p\in \{1,\dots,g\} such that \alpha ... more >>>

Combinatorial property testing deals with the following relaxation of
decision problems: Given a fixed property and an input f, one wants
to decide whether f satisfies the property or is `far' from satisfying
the property.
It has been shown that regular languages are testable,
and that there exist context free ... more >>>

We propose a new model for studying graph related problems
that we call the \emph{orientation model}. In this model, an undirected
graph G is fixed, and the input is any possible edge orientation
of G. A property is now a property of the directed graph that is
obtained by a ... more >>>

Combinatorial property testing deals with the following relaxation
of decision problems: Given a fixed property and an input x, one
wants to decide whether x satisfies the property or is ``far''
from satisfying it. The main focus of property testing is in
identifying large families of properties that can be ... more >>>

We study a model of graph related formulae that we call
the \emph{Constraint-Graph model}. A
constraint-graph is a labeled multi-graph (a graph where loops
and parallel edges are allowed), where each edge e is labeled
by a distinct Boolean variable and every vertex is
associate with a Boolean function over ... more >>>