Monotonicity checking [Elektronische Ressource] / vorgelegt von Marina Kyureghyan

Sujets

• Informatik
• Mathematics

Informations

• Publié par: universitat_bielefeld
• Publié le: 01 janvier 2004
• Nombre de lectures: 18
• Langue: English

Extrait

Univ
MONOTONICITY
Marina
CHECKING
v
Dissertation
12.
zur
at
Erlangung
v
des
y
Doktorgrades
uar
der
ersit
F
Bielefeld
akult
orgelegt
at
on
f
Kyuregh

an
ur
Jan
Mathematik
2004
derto
Ac
Kyuregh
kno
of
wledgemen
Dr.
ts
I
I
and
w
of
ould

lik
to
e
ort.
to
and
express
are
m
for
y
impro
deep
Rehmann.
appreciation
andigem
to
sc
m
hno
y
Carstens
advisor
the
Professor
and
Ahlsw
their
ede
ort.
for
Aydin
all
Jan
the
the
things
corrections
I
Gutac
could
und
learn

from
kt
him.
ISO
My
for
gratitude
arship,
go
rau
es
from
also
and
to
their
Harout
thank
Aydin
b
y
group
an,
y",
Lev
t,
on
hospitalit
Khac
t
hatrian,
ecial
Alexander
to
Y
an,
udin
an
and
ey
Stefan
reading
Gr
v

thesis,
unew
suggestions
ald
emen
for
ter:
their
Ahlsw
in
Dr.
terest
der
and
hen
advises.
21.01.2004.
I
alterungsb
am
apier
grateful
i
to
apply
the
that
Univ
hol-
ersit
and
y
F
of
Sc
Bielefeld
or
for
Dezernat
supp
I
orting
Professor
me
for
with
supp
a
I
sc
all
holarship
mem
"Stip
ers
endium
the
zur
"Information
F
Complexit
orderung
former
des
presen
wissensc
for
haftlic
great
hen
y
und
constan
k
supp

Sp
unstlerisc
thanks
hen
due
Nac
Harout
h
y
wuc
Gohar
h-
y
ses"
and
during
W
the
er-Menkho
last
careful
y
of
ear
preliminary
of
ersion
m
this
y
for
w
and
ork
for
on
v
the
ts.
dissertation.
h
I
Prof.
w
R.
an
ede
t
Prof.
to
U.
express
Datum
m
m
y
undlic
sp
Pr
ecial
ufung:
thanks
Gedruc
to
auf
Professor
est
Dress
P
for
1
his
9706.
encouragemen
t.
Con
.
ten
.
ts
.
1
.
The
of
comparison
.
mo
.
del
.
5
.
1.1
linear
Basic
.
denitions
.
and
2.2
concepts
.
.
b
.
.
.
.
.
.
.
.
.
.
.
2.1
.
hec
.
.
.
.
.
.
.
.
.
v
.
.
.
.
.
2.3
.
.
.
.
.
2.4
.
.
.
.
5
.
1.2
complexit
General
.
observ
.
ations
.
.
2
.
del
.
in
.
y
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
from
.
geometry
.
.
.
.
.
.
.
.
.
.
.
olyhedral
.
problem
.
.
.
.
.
.
.
.
8
p
1.3
.
Prop
.
erties
.
of
.
monotonicit
.
y
.
c
2.5
hec
.
king
.
complexit
.
y
.
.
.
.
.
.
.
.
ii
.
The
.
mo
.
50
.
Geometric
.
terpretation
.
monotonicit
.
c
12
king
1.4
.
Sim
.
ultaneous
.
recognition
.
of
.
the
.
minim
.
um
.
and
.
the
.
maxim
.
um
.
.
.
.
.
.
.
37
.
1.5
50
The
Notions
Bo
con
olean
ex
lattice
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
52
.
P
.
mem
.
ership
.
(PMP)
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
53
.
Monotone
.
olyhedron
.
.
.
.
.
.
40
.
1.6
.
F
.
unctions
.
with
.
restricted
.
n
.
um
.
b
.
er
53
of
Linear
v
y
alues
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
55
.
48b
In
(
tro
f
duction
w
Imagine
i
that
Bo
y
f
ou
of
ha
terpreted
v
to
e
lo
a
n
ship
:
and
wn
w
to
an
p
t
assumptions.
to
on
distribute
C
some
The
go
coun
o
c
ds
olean
in
binary
sev
)
eral

coun-
g
tries
,
C
erations
1
alues
;
an
C
hec
2
b
;
can
:
alued
:
with
:
if
;
m
C
the
n
alid
passing
the
through
tak
eac
problem
h
the
coun
e
try
n
only
its
once.
n
Supp
:
ose,
(
there
)
are
ev
constrain
:
ts
b
on
function
y
an
our
is
route,
are
since
comparisons
for
at
some
course,
pairs
as
of
a
coun
function
tries
v
(
of
C
suggested
i
e
;
a
C
f
j
p
)
(
it
=
m
coun
ust
is
come
coun
to
according
a
osed
coun
is
try
the
C
monotone
j
oset
only
Let
after
a
passing
at
the
monotonicit
coun
king
try
of
C
lattice.
i
the
to
of
transp
y
ort
represen
some
ts
go
of
o
x
ds
1
from
x
C
y
i
1
to
y
C
x
j
i
.
i
Of
;
course,
;
there
Let
m
an
ust
v
b
B
e
e
no
to
con
this
tradictions
The
in
w
these
w
constrain
erform
ts
the
so
the
that
y
the
hoice.
mission
e
is
to
p
kly
ossible
One
to
to
p
whether
erform
monotone
visiting
comparing
eac
1
h
ecause
coun
our
try
The
once.
route
Supp
b
ose,
in
there
as
is
natural-v
already
function
an
dened
unkno
this
wn
oset,
route
f
suggested
C
and
)
y
m
ou
the
ha
try
v
i
e
the
to
-th
decide
try
whether
visit
this
to
route
prop
is
route.
satisfactory
route
for
v
y
if
our
function
purp
is
ose.
on
This
p
is
of
a
tries.
monotonicit
us
y
e
c
closer
hec
ok
king
the
problem:
of
Giv
y
en
hec
a
on
nite
example
p
a
oset
olean
P
W
and
denote
an
Bo
unkno
lattice
wn
order
real-v
b
alued
B
function
and
f
t
on
elemen
it,
as
nd
strings
out
length
whether
with
this
=
function
x
is
:
order
:
preserving
n
on

P
=
,
y
that
:
is,
:
whether
n
f
i
(
i
x
y
)
for

ery
f
2
(
1
y
:
)
:
for
n
an
.
y
f
x
e
<
unkno
y
real-
in
alued
P
on
.
n
Indeed,
w
let
w
the
t
coun
kno
tries
whether
b
function
e
monotone.
the
op
elemen
that
ts
e
of
allo
the
ed
p
p
oset
are
with
of
C
v
i
of
<
function
C
an
j
pair
if
c
the
Of
coun
w
try
w
C
t
i
nish
is
quic
to
as
b
ossible.
e
w
visited
y
b
c
efore
k<