---
_id: '2414'
author:
- first_name: Uli
full_name: Uli Wagner
id: 36690CA2-F248-11E8-B48F-1D18A9856A87
last_name: Wagner
orcid: 0000-0002-1494-0568
citation:
ama: Wagner U. *On K-Sets and Their Applications*. ETH Zurich; 2003. doi:10.3929/ethz-a-004708408
apa: Wagner, U. (2003). *On k-Sets and Their Applications*. ETH Zurich. https://doi.org/10.3929/ethz-a-004708408
chicago: Wagner, Uli. *On K-Sets and Their Applications*. ETH Zurich, 2003.
https://doi.org/10.3929/ethz-a-004708408.
ieee: U. Wagner, *On k-Sets and Their Applications*. ETH Zurich, 2003.
ista: Wagner U. 2003. On k-Sets and Their Applications, ETH Zurich,p.
mla: Wagner, Uli. *On K-Sets and Their Applications*. ETH Zurich, 2003, doi:10.3929/ethz-a-004708408.
short: U. Wagner, On K-Sets and Their Applications, ETH Zurich, 2003.
date_created: 2018-12-11T11:57:31Z
date_published: 2003-01-01T00:00:00Z
date_updated: 2019-04-26T07:22:12Z
day: '01'
doi: 10.3929/ethz-a-004708408
extern: 1
month: '01'
publication_status: published
publisher: ETH Zurich
publist_id: '4511'
quality_controlled: 0
status: public
title: On k-Sets and Their Applications
type: dissertation
year: '2003'
...
---
_id: '3678'
author:
- first_name: Christoph
full_name: Christoph Lampert
id: 40C20FD2-F248-11E8-B48F-1D18A9856A87
last_name: Lampert
orcid: 0000-0001-8622-7887
citation:
ama: Lampert C. *The Neumann Operator in Strictly Pseudoconvex Domains with Weighted
Bergman Metric *. Vol 356. Universität Bonn, Fachbibliothek Mathematik; 2003:1-165.
apa: Lampert, C. (2003). *The Neumann operator in strictly pseudoconvex domains
with weighted Bergman metric *. *Bonner Mathematische Schriften* (Vol.
356, pp. 1–165). Universität Bonn, Fachbibliothek Mathematik.
chicago: Lampert, Christoph. *The Neumann Operator in Strictly Pseudoconvex Domains
with Weighted Bergman Metric *. *Bonner Mathematische Schriften*. Vol.
356. Universität Bonn, Fachbibliothek Mathematik, 2003.
ieee: C. Lampert, *The Neumann operator in strictly pseudoconvex domains with
weighted Bergman metric *, vol. 356. Universität Bonn, Fachbibliothek Mathematik,
2003, pp. 1–165.
ista: Lampert C. 2003. The Neumann operator in strictly pseudoconvex domains with
weighted Bergman metric , Universität Bonn, Fachbibliothek Mathematik,p.
mla: Lampert, Christoph. “The Neumann Operator in Strictly Pseudoconvex Domains
with Weighted Bergman Metric .” *Bonner Mathematische Schriften*, vol. 356,
Universität Bonn, Fachbibliothek Mathematik, 2003, pp. 1–165.
short: C. Lampert, The Neumann Operator in Strictly Pseudoconvex Domains with Weighted
Bergman Metric , Universität Bonn, Fachbibliothek Mathematik, 2003.
date_created: 2018-12-11T12:04:34Z
date_published: 2003-03-31T00:00:00Z
date_updated: 2019-04-26T07:22:33Z
day: '31'
extern: 1
intvolume: ' 356'
main_file_link:
- open_access: '0'
url: http://pub.ist.ac.at/~chl/papers/lampert-phd2003.pdf
month: '03'
page: 1 - 165
publication: Bonner Mathematische Schriften
publication_status: published
publisher: Universität Bonn, Fachbibliothek Mathematik
publist_id: '2704'
quality_controlled: 0
status: public
title: 'The Neumann operator in strictly pseudoconvex domains with weighted Bergman
metric '
type: dissertation
volume: 356
year: '2003'
...
---
_id: '4416'
abstract:
- lang: eng
text: "Methods for the formal specification and verification of systems are indispensible
for the development of complex yet correct systems. In formal verification, the
designer describes the system in a modeling language with a well-defined semantics,
and this system description is analyzed against a set of correctness requirements.
Model checking is an algorithmic technique to check that a system description
indeed satisfies correctness requirements given as logical specifications. While
successful in hardware verification, the potential for model checking for software
and embedded systems has not yet been realized. This is because traditional model
checking focuses on systems modeled as finite state-transition graphs. While a
natural model for hardware (especially synchronous hardware), state-transition
graphs often do not capture software and embedded systems at an appropriate level
of granularity. This dissertation considers two orthogonal extensions to finite
state-transition graphs making model checking techniques applicable to both a
wider class of systems and a wider class of properties.\r\n\r\nThe first direction
is an extension to infinite-state structures finitely represented using constraints
and operations on constraints. Infinite state arises when we wish to model variables
with unbounded range (e.g., integers), or data structures, or real time. We provide
a uniform framework of symbolic region algebras to study model checking of infinite-state
systems. We also provide sufficient language-independent termination conditions
for symbolic model checking algorithms on infinite state systems.\r\n\r\nThe second
direction supplements verification with game theoretic reasoning. Games are natural
models for interactions between components. We study game theoretic behavior with
winning conditions given by temporal logic objectives both in the deterministic
and in the probabilistic context. For deterministic games, we provide an extremal
model characterization of fixpoint algorithms that link solutions of verification
problems to solutions for games. For probabilistic games we study fixpoint characterization
of winning probabilities for games with omega-regular winning objectives, and
construct (epsilon-)optimal winning strategies."
article_processing_charge: No
author:
- first_name: Ritankar
full_name: Majumdar, Ritankar
last_name: Majumdar
citation:
ama: Majumdar R. *Symbolic Algorithms for Verification and Control*. University
of California, Berkeley; 2003:1-201.
apa: Majumdar, R. (2003). *Symbolic algorithms for verification and control*
(pp. 1–201). University of California, Berkeley.
chicago: Majumdar, Ritankar. *Symbolic Algorithms for Verification and Control*.
University of California, Berkeley, 2003.
ieee: R. Majumdar, *Symbolic algorithms for verification and control*. University
of California, Berkeley, 2003, pp. 1–201.
ista: Majumdar R. 2003. Symbolic algorithms for verification and control, University
of California, Berkeley,p.
mla: Majumdar, Ritankar. *Symbolic Algorithms for Verification and Control*.
University of California, Berkeley, 2003, pp. 1–201.
short: R. Majumdar, Symbolic Algorithms for Verification and Control, University
of California, Berkeley, 2003.
date_created: 2018-12-11T12:08:44Z
date_published: 2003-12-01T00:00:00Z
date_updated: 2020-10-07T09:14:07Z
day: '01'
extern: '1'
language:
- iso: eng
month: '12'
oa_version: None
page: 1 - 201
publication_status: published
publisher: University of California, Berkeley
publist_id: '313'
status: public
supervisor:
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000-0002-2985-7724
title: Symbolic algorithms for verification and control
type: dissertation
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2003'
...
---
_id: '4425'
abstract:
- lang: eng
text: "Giotto provides a time-triggered programmer’s model for the implementation
of embedded control systems with hard real-time constraints. Giotto’s precise
semantics and predictabil- ity make it suitable for safety-critical applications.\r\nGiotto
is based around the idea that time-triggered task invocation together with time-triggered
mode switching can form a useful programming model for real-time systems. To substantiate
this claim, we describe the use of Giotto to refactor the software of a small,
autonomous helicopter. The ease with which Giotto expresses the existing software
provides evidence that Giotto is an appropriate programming language for control
systems.\r\nSince Giotto is a real-time programming language, ensuring that Giotto
programs meet their deadlines is crucial. To study precedence-constrained Giotto
scheduling, we first examine single-mode, single-processor scheduling. We extend
to an infinite, periodic setting the classical problem of meeting deadlines for
a set of tasks with release times, deadlines, precedence constraints, and preemption.
We then develop an algorithm for scheduling Giotto programs on a single processor
by representing Giotto programs as instances of the extended scheduling problem.\r\nNext,
we study multi-mode, single-processor Giotto scheduling. This problem is different
from classical scheduling problems, since in our precedence-constrained approach,
the deadlines of tasks may vary depending on the mode switching behavior of the
program. We present conditional scheduling models which capture this varying-deadline
behavior. We develop polynomial-time algorithms for some conditional scheduling
models, and prove oth- ers to be computationally hard. We show how to represent
multi-mode Giotto programs as instances of the model, resulting in an algorithm
for scheduling multi-mode Giotto programs on a single processor.\r\nFinally, we
show that the problem of scheduling Giotto programs for multiple net- worked processors
is strongly NP-hard."
article_processing_charge: No
author:
- first_name: Benjamin
full_name: Horowitz, Benjamin
last_name: Horowitz
citation:
ama: 'Horowitz B. *Giotto: A Time-Triggered Language for Embedded Programming*.
University of California, Berkeley; 2003:1-237.'
apa: 'Horowitz, B. (2003). *Giotto: A time-triggered language for embedded programming*
(pp. 1–237). University of California, Berkeley.'
chicago: 'Horowitz, Benjamin. *Giotto: A Time-Triggered Language for Embedded
Programming*. University of California, Berkeley, 2003.'
ieee: 'B. Horowitz, *Giotto: A time-triggered language for embedded programming*.
University of California, Berkeley, 2003, pp. 1–237.'
ista: 'Horowitz B. 2003. Giotto: A time-triggered language for embedded programming,
University of California, Berkeley,p.'
mla: 'Horowitz, Benjamin. *Giotto: A Time-Triggered Language for Embedded Programming*.
University of California, Berkeley, 2003, pp. 1–237.'
short: 'B. Horowitz, Giotto: A Time-Triggered Language for Embedded Programming,
University of California, Berkeley, 2003.'
date_created: 2018-12-11T12:08:47Z
date_published: 2003-10-01T00:00:00Z
date_updated: 2020-10-07T09:21:03Z
day: '01'
extern: '1'
language:
- iso: eng
month: '10'
oa_version: None
page: 1 - 237
publication_status: published
publisher: University of California, Berkeley
publist_id: '305'
status: public
supervisor:
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000-0002-2985-7724
title: 'Giotto: A time-triggered language for embedded programming'
type: dissertation
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2003'
...
---
_id: '4414'
abstract:
- lang: eng
text: "This dissertation investigates game-theoretic approaches to the algorithmic
analysis of concurrent, reactive systems. A concurrent system comprises a number
of components working concurrently; a reactive system maintains an ongoing interaction
with its environment. Traditional approaches to the formal analysis of concurrent
reactive systems usually view the system as an unstructured state-transition graphs;
instead, we view them as collections of interacting components, where each one
is an open system which accepts inputs from the other components. The interactions
among the components are naturally modeled as games.\r\n\r\nAdopting this game-theoretic
view, we study three related problems pertaining to the verification and synthesis
of systems. Firstly, we propose two novel game-theoretic techniques for the model-checking
of concurrent reactive systems, and improve the performance of model-checking.
The first technique discovers an error as soon as it cannot be prevented, which
can be long before it actually occurs. This technique is based on the key observation
that "unpreventability" is a local property to a module: an error is
unpreventable in a module state if no environment can prevent it. The second technique
attempts to decompose a model-checking proof into smaller proof obligations by
constructing abstract modules automatically, using reachability and "unpreventability"
information about the concrete modules. Three increasingly powerful proof decomposition
rules are proposed and we show that in practice, the resulting abstract modules
are often significantly smaller than the concrete modules and can drastically
reduce the space and time requirements for verification. Both techniques fall
into the category of compositional reasoning.\r\n\r\nSecondly, we investigate
the composition and control of synchronous systems. An essential property of synchronous
systems for compositional reasoning is non-blocking. In the composition of synchronous
systems, however, due to circular causal dependency of input and output signals,
non-blocking is not always guaranteed. Blocking compositions of systems can be
ruled out semantically, by insisting on the existence of certain fixed points,
or syntactically, by equipping systems with types, which make the dependencies
between input and output signals transparent. We characterize various typing mechanisms
in game-theoretic terms, and study their effects on the controller synthesis problem.
We show that our typing systems are general enough to capture interesting real-life
synchronous systems such as all delay-insensitive digital circuits. We then study
their corresponding single-step control problems --a restricted form of controller
synthesis problem whose solutions can be iterated in appropriate manners to solve
all LTL controller synthesis problems. We also consider versions of the controller
synthesis problem in which the type of the controller is given. We show that the
solution of these fixed-type control problems requires the evaluation of partially
ordered (Henkin) quantifiers on boolean formulas, and is therefore harder (nondeterministic
exponential time) than more traditional control questions.\r\n\r\nThirdly, we
study the synthesis of a class of open systems, namely, uninitialized state machines.
The sequential synthesis problem, which is closely related to Church's solvability
problem, asks, given a specification in the form of a binary relation between
input and output streams, for the construction of a finite-state stream transducer
that converts inputs to appropriate outputs. For efficiency reasons, practical
sequential hardware is often designed to operate without prior initialization.
Such hardware designs can be modeled by uninitialized state machines, which are
required to satisfy their specification if started from any state. We solve the
sequential synthesis problem for uninitialized systems, that is, we construct
uninitialized finite-state stream transducers. We consider specifications given
by LTL formulas, deterministic, nondeterministic, universal, and alternating Buechi
automata. We solve this uninitialized synthesis problem by reducing it to the
well-understood initialized synthesis problem. While our solution is straightforward,
it leads, for some specification formalisms, to upper bounds that are exponentially
worse than the complexity of the corresponding initialized problems. However,
we prove lower bounds to show that our simple solutions are optimal for all considered
specification formalisms. The lower bound proofs require nontrivial generic reductions."
article_processing_charge: No
author:
- first_name: Freddy
full_name: Mang, Freddy
last_name: Mang
citation:
ama: Mang F. *Games in Open Systems Verification and Synthesis*. University
of California, Berkeley; 2002:1-116.
apa: Mang, F. (2002). *Games in open systems verification and synthesis* (pp.
1–116). University of California, Berkeley.
chicago: Mang, Freddy. *Games in Open Systems Verification and Synthesis*.
University of California, Berkeley, 2002.
ieee: F. Mang, *Games in open systems verification and synthesis*. University
of California, Berkeley, 2002, pp. 1–116.
ista: Mang F. 2002. Games in open systems verification and synthesis, University
of California, Berkeley,p.
mla: Mang, Freddy. *Games in Open Systems Verification and Synthesis*. University
of California, Berkeley, 2002, pp. 1–116.
short: F. Mang, Games in Open Systems Verification and Synthesis, University of
California, Berkeley, 2002.
date_created: 2018-12-11T12:08:44Z
date_published: 2002-05-01T00:00:00Z
date_updated: 2020-10-07T07:00:47Z
day: '01'
extern: '1'
language:
- iso: eng
month: '05'
oa_version: None
page: 1 - 116
publication_status: published
publisher: University of California, Berkeley
publist_id: '315'
status: public
supervisor:
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000-0002-2985-7724
title: Games in open systems verification and synthesis
type: dissertation
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2002'
...