## Samy Zafrany: Research Papers

The papers are in PostScript format. Download by clicking on the paper name. Following the list of papers is a short description of the contents of each paper (including publishing date, journal, and co-authors).

## Abstracts of these papers

These are the short abstracts of the papers, in TeX format (for those that can read it this way). Some control sequences are defined at the local macros files, so it is hard to read them this way. So you may need to download the full PostScript files anyway.
PAPER 1

Title: On Triangular Norm-Based Propositional Fuzzy Logics

Authors:
Dan Butnariu
Department of Mathematics and Computer Science,
University of Haifa, 31905 Haifa, Israel

Erich Peter Klement
Institut f\"ur Mathematik,
Johannes Kepler Universit\"at, A-4040 Linz, Austria

Samy Zafrany
Department of Mathematics
Technion city, 32000 Haifa, Israel
samy@techunix.technion.ac.il

Journal: Fuzzy Sets and Systems 69 (1995), 241-255.

\begin{abstract}
Fuzzy logics based on triangular norms and their corresponding conorms
are investigated. An affirmative answer to the question whether in such logics a
specific level of satisfiability of a set of formulas can be characterized by
the same level of satisfiability of its finite subsets is given. Tautologies,
contradictions and contingencies with respect to such fuzzy logics are studied,
in particular for the important cases of min-max and Lukasiewicz logics.
Finally, fundamental t-norm-based fuzzy logics are shown to provide a gradual
transition between min-max and Lukasiewicz logics.
\end{abstract}
Key words: Fuzzy Logics, Min-max logic, Lukasiewicz Logic, Triangular
Key words: Norms,  Satisfiability.
AMS-Classification: 03B52, 03B50, 03B05

==============================================================================
==============================================================================

PAPER 2

Title:  Topological Complexity of Graphs and their Spanning Trees

Authors:
Ronny Nahum
Department of Mathematics and Computer Science
Haifa University, 31905 Haifa, Israel

Samy Zafrany
Department of Mathematics
Technion city, 32000 Haifa, Israel
e-mail:samy@techunix.technion.ac.il

Journal: Acta Mathematica Hungarica 66 (1) (1995), 1-10.

\begin{abstract}
Let $X$ be a perfect separable complete metric space.
Let $G=(V,E)$ be a simple graph such that $V\subseteq X$.
Let $\vec{E}=\setn{(x,y)}{\{x,y\}\in E}$.
We call $G$ {\em analytic} if $\vec{E}$ is an analytic subset of $X^2$.
Similarly, $G$ is {\em $\sigma$-analytic}
if $\vec{E}$ belongs to the $\sigma$-algebra
generated by all the analytic subsets of $X^2$.
We call $G$ a {\em weighted graph} if an ordinal is assigned to every edge.
Let $G$ be an analytic connected weighted graph. We prove that
under some restrictions $G$ has a $\sigma$-analytic minimal
spanning tree $T$ (i.e, if we replace one edge in $T$ by a lighter edge,
then $T$ stops being a spanning tree).
We also give examples that show that this result is optimal.
\end{abstract}
Key words:
weighted graphs, minimal spanning tree, analytic set,
uniformization, projective hierarchy.
AMS-Classification: 03B52, 03B50, 03B05

==============================================================================
==============================================================================

PAPER 3:

A Topological Linking Theorem in Simple Graphs

Ronny Nahum and Samy Zafrany
Department of Mathematics and Computer Science
Haifa University, 31905 Haifa, Israel
e-mail:{samy@techunix.technion.ac.il}

June 14, 1994

\begin{abstract}
We prove a topological version of a combinatorial theorem due to
R.~A.~Brualdi and J.~S.~Pym. Their theorem is a generalization
of the well known Cantor-Bernstein Theorem as well as of
other reformulations of it
(Banach's mapping theorem and \Konig's matching theorem).
Let $G=(V,E)$ be a simple graph such that $V$
is a perfect separable complete metric space.
Let $A,B\subseteq V$ be disjoint,
and let $A{*}B$ be the set of all paths $p=(x_1,x_2,\ldots,x_n)$ in $G$,
such that $x_1\in A$ and $x_n\in B$.
A {\em linking} $f:A\leadsto B$ is a subset $f\subseteq A{*}B$
such that for each $a\in A$ there exists exactly one path $p\in f$
whose initial vertex is $a$.
We call $f$ {\em injective} if every distinct
$p,q\in f$ are vertex-disjoint,
and we call $f$ {\em bijective} if, in addition, for every $b\in B$
there is a path in $f$ that ends with $b$.
The topological version states: if $f:A\leadsto B$ and $g:B\leadsto A$
are Borel injective linkings, then there exists a Borel
bijective linking $h:A\leadsto B$.
We also consider possible extensions
of this result in various directions.
\end{abstract}
Key words: topological graph, Borel set, linking, perfect matching
AMS-Classification: 04A15, 05C10, 03E15

==============================================================================
==============================================================================

PAPER 4

Title:    Borel Ideals vs. Borel Sets of Countable Relations and Trees

Author:   Samy Zafrany

Journal:  Annals of Pure and Applied Logic 43 (1989)

This paper is a revised version of Chapter 3 of the author's
Ph.D. dissertation which was written in the University of California
at Berkeley, under the supervision of Professor John W. Addison.

\begin{abstract}
For every $\mu<\w_1$, let $I_\mu$ be the ideal of all sets
$S\subseteq\w^\mu$ whose order type is $<\w^\mu$.
If $\mu=1$ then $I_1$ is simply the ideal of all finite subsets of
$\w$, which is known to be $\BS{2}$-complete.
We show that for every $\mu<\w_1$, $I_\mu$ is $\BS{2\mu}$-complete.
As corollaries to this theorem, we prove that the set
$\WO_{\w^\mu}$ of well orderings
$R\subseteq\wxw$ of order type $<\w^\mu$ is $\BS{2\mu}$-complete,
the set $\LP_\mu$ of linear orderings
$R\subseteq\wxw$ that have a $\mu$-limit point is $\BS{2\mu+1}$-complete.
Similarly, we determine the exact complexity of
the set $\LT_\mu$ of trees $T\subseteq\wpwc$ of Luzin height $<\mu$,
the set $\WR_\mu$ of well-founded partial orderings of height $<\mu$,
the set $\LR_\mu$ of partial orderings of Luzin height $<\mu$,
the set $\WF_\mu$ of well-founded trees $T\subseteq\wpwc$ of height $<\mu$
(the latter is an old theorem of Luzin).
We also present a short proof to a theorem of Luzin and Garland about
the relation between the height of the shortest tree'' representing a
Borel set and the complexity of the set.
\end{abstract}

==================================================================
==================================================================

PAPER 5

Title:  On Analytic Filters and Pre-filters

Author: Samy Zafrany

Department of Mathematics and Computer Science
Ben Gurion University of the Negev
Beer Sheva, Israel

Journal: Journal of Symbolic Logic, Vol. 55, Num. 1 March 1990

\begin{abstract}
We show that every analytic filter is generated by a
$\BP{2}$ pre-filter,
every $\BS{2}$ filter is generated by a $\BP{1}$ pre-filter, and
if $P\subseteq\pw$ is a $\BS{2}$ pre-filter then the
filter generated by it is also $\BS{2}$. The last result is unique for
the Borel classes as
there is a $\BP{2}$-complete pre-filter $P$ such that the filter
generated by it is $\boldSigma^1_1$-complete.
Also, every complete co-analytic filter
does not have an analytic pre-filter.
The proofs use \Konig's infinity Lemma, a normal form theorem
for monotone analytic sets,
\end{abstract}

==================================================================
==================================================================

PAPER 6

Title:  On the Topological Strength of Boolean Set Operations

This paper is an extended version of Chapter 1 of the author's
Ph.D. dissertation which was written in the University of California
at Berkeley, under the supervision of Professor John W. Addison.

Author: Samy Zafrany

July 30, 1989
Draft 1

\begin{abstract}
We review the basic facts of the theory of Boolean set operations.
A measure of strength is assigned to every Boolean set operation
by relating it to a subset of the Cantor space and using the usual
topological complexity of that set.
Composition of two or countably many Boolean set operations is
defined and its properties are studied. We focus our attention
on the compositions of the $\liminf$ and $\limsup$ operations and
generalize (in various directions)
an old theorem of Sier\'pinski on the strength of those operations.
\end{abstract}

Samy Zafrany                 School of Computer Science and Mathematics