ๆ312๑คu๏Jรฤเ
มสu๏
ๅรFdq๎๑สMw๏kx
ครFkๅwRs
[^TCGXค๏
๎๑w๏kx
utผF@Professor Hsu-Chun Yen
utฎF@Dept. of Electrical Engineering
@@@@National Taiwan University
u๏^CgFSemilinear Sets and Their Applications
Jร๚FQOOTNPQS๚ijPRFOO|PSFOO
Jร๊FkๅwHwdC๎๑nQูSORบ
TvF Semilinear sets are exactly those that can be expressed by
Presburger Arithmetic. As many interesting problems concerning
Presburger Arithmetic (including membership, equivalence
and containment) are decidable, semilinear sets have
found interesting applications in a variety of areas in
computer sciences. In this talk, we first survey some of the
properties and results concerning semilinear sets, and
then see how they can be applied to the analysis of concurrent
systems. In the second part of this talk, we focus on a
restricted class called upward-closed sets. Although it is
known that any upward-closed set exhibits a finite number of
minimal elements, such elements, however, may not be
computable in general. We demonstrate conditions under which
the set of minimal elements of an upward-closed set
is not only computable, but more importantly, a bound for
the size of the minimal elements can also be deduced.
Some applications regarding this characterization
of upward-closed sets are given.
โขํนๆF@ผึฒvi
)