---
OA_type: closed access
_id: '3873'
abstract:
- lang: eng
text: We study the controller synthesis problem under budget constraints. In this
problem, there is a cost associated with making an observation, and a controller
can make only a limited number of observations in each round so that the total
cost of the observations does not exceed a given fixed budget. The controller
must ensure some omega-regular requirement subject to the budget constraint. Budget
constraints arise in designing and implementing controllers for resource-constrained
embedded systems, where a controller may not have enough power, time, or bandwidth
to obtain data from all sensors in each round. They lead to games of imperfect
information, where the unknown information is not fixed a priori, but can vary
from round to round, based on the choices made by the controller how to allocate
its budget. We show that the budget-constrained synthesis problem for W-regular
objectives is complete for exponential time. In addition to studying synthesis
under a fixed budget constraint, we study the budget optimization problem, where
given a plant, an objective, and observation costs, we have to find a controller
that achieves the objective with minimal average accumulated cost (or minimal
peak cost). We show that this problem is reducible to a game of imperfect information
where the winning objective is a conjunction of an omega-regular condition and
a long-run average condition (or a least max-cost condition), and this again leads
to an exponential-time algorithm. Finally, we extend our results to games over
infinite state spaces, and show that the budget-constrained synthesis problem
is decidable for infinite state games with stable quotients of finite index. Consequently,
the discrete time budget-constrained synthesis problem is decidable for rectangular
hybrid automata.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Ritankar
full_name: Majumdar, Ritankar
last_name: Majumdar
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000−0002−2985−7724
citation:
ama: 'Chatterjee K, Majumdar R, Henzinger TA. Controller synthesis with budget constraints.
In: 11th Workshop on Hybrid Systems: Computation and Control. Vol 4981.
Springer Nature; 2008:72-86. doi:DOI:
10.1007/978-3-540-78929-1_6'
apa: 'Chatterjee, K., Majumdar, R., & Henzinger, T. A. (2008). Controller synthesis
with budget constraints. In 11th Workshop on Hybrid Systems: Computation and
Control (Vol. 4981, pp. 72–86). St. Louis, MO, United States: Springer Nature.
https://doi.org/DOI:
10.1007/978-3-540-78929-1_6'
chicago: 'Chatterjee, Krishnendu, Ritankar Majumdar, and Thomas A Henzinger. “Controller
Synthesis with Budget Constraints.” In 11th Workshop on Hybrid Systems: Computation
and Control, 4981:72–86. Springer Nature, 2008. https://doi.org/DOI: 10.1007/978-3-540-78929-1_6.'
ieee: 'K. Chatterjee, R. Majumdar, and T. A. Henzinger, “Controller synthesis with
budget constraints,” in 11th Workshop on Hybrid Systems: Computation and Control,
St. Louis, MO, United States, 2008, vol. 4981, pp. 72–86.'
ista: 'Chatterjee K, Majumdar R, Henzinger TA. 2008. Controller synthesis with budget
constraints. 11th Workshop on Hybrid Systems: Computation and Control. HSCC: Hybrid
Systems - Computation and Control, LNCS, vol. 4981, 72–86.'
mla: 'Chatterjee, Krishnendu, et al. “Controller Synthesis with Budget Constraints.”
11th Workshop on Hybrid Systems: Computation and Control, vol. 4981, Springer
Nature, 2008, pp. 72–86, doi:DOI:
10.1007/978-3-540-78929-1_6.'
short: 'K. Chatterjee, R. Majumdar, T.A. Henzinger, in:, 11th Workshop on Hybrid
Systems: Computation and Control, Springer Nature, 2008, pp. 72–86.'
conference:
end_date: 2008-04-24
location: St. Louis, MO, United States
name: 'HSCC: Hybrid Systems - Computation and Control'
start_date: 2008-04-22
date_created: 2018-12-11T12:05:38Z
date_published: 2008-04-03T00:00:00Z
date_updated: 2026-05-29T10:25:48Z
day: '03'
doi: 'DOI: 10.1007/978-3-540-78929-1_6'
extern: '1'
fulldoi: 'https://doi.org/DOI: 10.1007/978-3-540-78929-1_6'
intvolume: ' 4981'
language:
- iso: eng
month: '04'
oa_version: None
page: 72 - 86
publication: '11th Workshop on Hybrid Systems: Computation and Control'
publication_identifier:
eissn:
- 1611-3349
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
publist_id: '2296'
status: public
title: Controller synthesis with budget constraints
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 4981
year: '2008'
...
---
OA_type: closed access
_id: '3874'
abstract:
- lang: eng
text: We consider concurrent two-player timed automaton games with omega-regular
objectives specified as parity conditions. These games offer an appropriate model
for the synthesis of real-time controllers. Earlier works on timed games focused
on pure strategies for each player. We study, for the first time, the use of randomized
strategies in such games. While pure (i.e., nonrandomized) strategies in timed
games require infinite memory for winning even with respect to reachability objectives,
we show that randomized strategies can win with finite memory with respect to
all parity objectives. Also, the synthesized randomized real-time controllers
are much simpler in structure than the corresponding pure controllers, and therefore
easier to implement. For safety objectives we prove the existence of pure finite-memory
winning strategies. Finally, while randomization helps in simplifying the strategies
required for winning timed parity games, we prove that randomization does not
help in winning at more states.
acknowledgement: This research was supported in part by the NSF grants CCR-0208875,
CCR-0225610, CCR-0234690, by the Swiss National Science Foundation, and by the Artist2
European Network of Excellence.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000−0002−2985−7724
- first_name: Vinayak
full_name: Prabhu, Vinayak
last_name: Prabhu
citation:
ama: 'Chatterjee K, Henzinger TA, Prabhu V. Trading infinite memory for uniform
randomness in timed games. In: 11th Workshop on Hybrid Systems: Computation
and Control. Vol 4981. Springer Nature; 2008:87-100. doi:10.1007/978-3-540-78929-1_7'
apa: 'Chatterjee, K., Henzinger, T. A., & Prabhu, V. (2008). Trading infinite
memory for uniform randomness in timed games. In 11th Workshop on Hybrid Systems:
Computation and Control (Vol. 4981, pp. 87–100). St. Louis, MO, United States:
Springer Nature. https://doi.org/10.1007/978-3-540-78929-1_7'
chicago: 'Chatterjee, Krishnendu, Thomas A Henzinger, and Vinayak Prabhu. “Trading
Infinite Memory for Uniform Randomness in Timed Games.” In 11th Workshop on
Hybrid Systems: Computation and Control, 4981:87–100. Springer Nature, 2008.
https://doi.org/10.1007/978-3-540-78929-1_7.'
ieee: 'K. Chatterjee, T. A. Henzinger, and V. Prabhu, “Trading infinite memory for
uniform randomness in timed games,” in 11th Workshop on Hybrid Systems: Computation
and Control, St. Louis, MO, United States, 2008, vol. 4981, pp. 87–100.'
ista: 'Chatterjee K, Henzinger TA, Prabhu V. 2008. Trading infinite memory for uniform
randomness in timed games. 11th Workshop on Hybrid Systems: Computation and Control.
HSCC: Hybrid Systems - Computation and Control, LNCS, vol. 4981, 87–100.'
mla: 'Chatterjee, Krishnendu, et al. “Trading Infinite Memory for Uniform Randomness
in Timed Games.” 11th Workshop on Hybrid Systems: Computation and Control,
vol. 4981, Springer Nature, 2008, pp. 87–100, doi:10.1007/978-3-540-78929-1_7.'
short: 'K. Chatterjee, T.A. Henzinger, V. Prabhu, in:, 11th Workshop on Hybrid Systems:
Computation and Control, Springer Nature, 2008, pp. 87–100.'
conference:
end_date: 2008-04-24
location: St. Louis, MO, United States
name: 'HSCC: Hybrid Systems - Computation and Control'
start_date: 2008-04-22
date_created: 2018-12-11T12:05:38Z
date_published: 2008-04-03T00:00:00Z
date_updated: 2026-06-10T10:14:59Z
day: '03'
doi: 10.1007/978-3-540-78929-1_7
extern: '1'
fulldoi: https://doi.org/10.1007/978-3-540-78929-1_7
intvolume: ' 4981'
language:
- iso: eng
month: '04'
oa_version: None
page: 87 - 100
publication: '11th Workshop on Hybrid Systems: Computation and Control'
publication_identifier:
eissn:
- 1611-3349
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
publist_id: '2297'
status: public
title: Trading infinite memory for uniform randomness in timed games
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 4981
year: '2008'
...
---
OA_type: closed access
_id: '3875'
abstract:
- lang: eng
text: We study the problem of model checking Interval-valued Discrete-time Markov
Chains (IDTMC). IDTMCs are discrete-time finite Markov Chains for which the exact
transition probabilities are riot known. Instead in IDTMCs, each transition is
associated with an interval in which the actual transition probability must lie.
We consider two semantic interpretations for the uncertainty in the transition
probabilities of an IDTMC. In the first interpretation, we think of an IDTMC as
representing a (possibly uncountable) family of (classical) discrete-time Markov
Chains, where each member of the family is a Markov Chain whose transition probabilities
lie within the interval range given in the IDTMC. We call this semantic interpretation
Uncertain Markov Chains (UMC). In the second semantics for an IDTMC, which we
call Interval Markov Decision Process (IMDP), we view the uncertainty as being
resolved through non-determinism. In other words, each time a state is visited,
we adversarially pick a transition distribution that respects the interval constraints,
and take a probabilistic step according to the chosen distribution. We introduce
a logic omega-PCTL that can express liveness, strong fairness, and omega-regular
properties (such properties cannot be expressed in PCTL). We show that the omega-PCTL
model checking problem for Uncertain Markov Chain semantics is decidable in PSPACE
(same as the best known upper bound for PCTL) and for Interval Markov Decision
Process semantics is decidable in coNP (improving the previous known PSPACE bound
for PCTL). We also show that the qualitative fragment of the logic can lie solved
in coNP for the UMC interpretation, and can be solved in polynomial time for a
sub-class of UMCs. We also prove lower bounds for these model checking problems.
We show that the model checking problem of IDTMCs with LTL formulas can be solved
for both UMC and IMDP semantics by reduction to the model checking problem of
IDTMC with omega-PcTL formulas.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000−0002−2985−7724
- first_name: Koushik
full_name: Sen, Koushik
last_name: Sen
citation:
ama: 'Chatterjee K, Henzinger TA, Sen K. Model-checking omega-regular properties
of interval Markov chains. In: Foundations of Software Science and Computational
Structures - 11th International Conference. Vol 4962. Springer Nature; 2008:302-317.
doi:10.1007/978-3-540-78499-9_22'
apa: 'Chatterjee, K., Henzinger, T. A., & Sen, K. (2008). Model-checking omega-regular
properties of interval Markov chains. In Foundations of Software Science and
Computational Structures - 11th International Conference (Vol. 4962, pp. 302–317).
Budapest, Hungary: Springer Nature. https://doi.org/10.1007/978-3-540-78499-9_22'
chicago: Chatterjee, Krishnendu, Thomas A Henzinger, and Koushik Sen. “Model-Checking
Omega-Regular Properties of Interval Markov Chains.” In Foundations of Software
Science and Computational Structures - 11th International Conference, 4962:302–17.
Springer Nature, 2008. https://doi.org/10.1007/978-3-540-78499-9_22.
ieee: K. Chatterjee, T. A. Henzinger, and K. Sen, “Model-checking omega-regular
properties of interval Markov chains,” in Foundations of Software Science and
Computational Structures - 11th International Conference, Budapest, Hungary,
2008, vol. 4962, pp. 302–317.
ista: 'Chatterjee K, Henzinger TA, Sen K. 2008. Model-checking omega-regular properties
of interval Markov chains. Foundations of Software Science and Computational Structures
- 11th International Conference. FoSSaCS: Foundations of Software Science and
Computation Structures, LNCS, vol. 4962, 302–317.'
mla: Chatterjee, Krishnendu, et al. “Model-Checking Omega-Regular Properties of
Interval Markov Chains.” Foundations of Software Science and Computational
Structures - 11th International Conference, vol. 4962, Springer Nature, 2008,
pp. 302–17, doi:10.1007/978-3-540-78499-9_22.
short: K. Chatterjee, T.A. Henzinger, K. Sen, in:, Foundations of Software Science
and Computational Structures - 11th International Conference, Springer Nature,
2008, pp. 302–317.
conference:
end_date: 2008-04-06
location: Budapest, Hungary
name: 'FoSSaCS: Foundations of Software Science and Computation Structures'
start_date: 2008-03-29
date_created: 2018-12-11T12:05:39Z
date_published: 2008-03-01T00:00:00Z
date_updated: 2026-05-29T10:35:10Z
day: '01'
doi: 10.1007/978-3-540-78499-9_22
extern: '1'
fulldoi: https://doi.org/10.1007/978-3-540-78499-9_22
intvolume: ' 4962'
language:
- iso: eng
month: '03'
oa_version: None
page: 302 - 317
publication: Foundations of Software Science and Computational Structures - 11th International
Conference
publication_identifier:
eissn:
- 1611-3349
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
publist_id: '2298'
status: public
title: Model-checking omega-regular properties of interval Markov chains
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 4962
year: '2008'
...
---
OA_place: repository
OA_type: green
_id: '3877'
abstract:
- lang: eng
text: The synthesis problem asks to construct a reactive finite-state system from
an omega-regular specification. Initial specifications are often unrealizable,
which means that there is no system that implements the specification. A common
reason for unrealizability is that assumptions on the environment of the system
are incomplete. We study the problem of correcting an unrealizable specification
phi by computing an environment assumption psi such that the new specification
psi -> phi is realizable. Our aim is to construct an assumption psi that constrains
only the environment and is as weak as possible. We present a two-step algorithm
for computing assumptions. The algorithm operates on the game graph that is used
to answer the realizability question. First, we compute a safety assumption that
removes a minimal set of environment edges from the graph. Second, we compute
a liveness assumption that puts fairness conditions on some of the remaining environment
edges. We show that the problem of finding a minimal set of fair edges is computationally
hard, and we use probabilistic games to compute a locally minimal fairness assumption.
alternative_title:
- LNCS
article_processing_charge: No
arxiv: 1
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000−0002−2985−7724
- first_name: Barbara
full_name: Jobstmann, Barbara
last_name: Jobstmann
citation:
ama: 'Chatterjee K, Henzinger TA, Jobstmann B. Environment assumptions for synthesis.
In: 19th International Conference on Concurrency Theory. Vol 5201. Schloss
Dagstuhl - Leibniz-Zentrum für Informatik; 2008:147-161. doi:10.1007/978-3-540-85361-9_14'
apa: 'Chatterjee, K., Henzinger, T. A., & Jobstmann, B. (2008). Environment
assumptions for synthesis. In 19th International Conference on Concurrency
Theory (Vol. 5201, pp. 147–161). Toronto, Canada: Schloss Dagstuhl - Leibniz-Zentrum
für Informatik. https://doi.org/10.1007/978-3-540-85361-9_14'
chicago: Chatterjee, Krishnendu, Thomas A Henzinger, and Barbara Jobstmann. “Environment
Assumptions for Synthesis.” In 19th International Conference on Concurrency
Theory, 5201:147–61. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2008.
https://doi.org/10.1007/978-3-540-85361-9_14.
ieee: K. Chatterjee, T. A. Henzinger, and B. Jobstmann, “Environment assumptions
for synthesis,” in 19th International Conference on Concurrency Theory,
Toronto, Canada, 2008, vol. 5201, pp. 147–161.
ista: 'Chatterjee K, Henzinger TA, Jobstmann B. 2008. Environment assumptions for
synthesis. 19th International Conference on Concurrency Theory. CONCUR: Concurrency
Theory, LNCS, vol. 5201, 147–161.'
mla: Chatterjee, Krishnendu, et al. “Environment Assumptions for Synthesis.” 19th
International Conference on Concurrency Theory, vol. 5201, Schloss Dagstuhl
- Leibniz-Zentrum für Informatik, 2008, pp. 147–61, doi:10.1007/978-3-540-85361-9_14.
short: K. Chatterjee, T.A. Henzinger, B. Jobstmann, in:, 19th International Conference
on Concurrency Theory, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2008,
pp. 147–161.
conference:
end_date: 2008-08-22
location: Toronto, Canada
name: 'CONCUR: Concurrency Theory'
start_date: 2008-08-19
date_created: 2018-12-11T12:05:39Z
date_published: 2008-07-30T00:00:00Z
date_updated: 2026-05-29T10:20:36Z
day: '30'
doi: 10.1007/978-3-540-85361-9_14
extern: '1'
external_id:
arxiv:
- '0805.4167'
fulldoi: https://doi.org/10.1007/978-3-540-85361-9_14
intvolume: ' 5201'
language:
- iso: eng
month: '07'
oa_version: Preprint
page: 147 - 161
publication: 19th International Conference on Concurrency Theory
publication_identifier:
eissn:
- 1611-3349
issn:
- 0302-9743
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
publist_id: '2295'
status: public
title: Environment assumptions for synthesis
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 5201
year: '2008'
...
---
OA_type: closed access
_id: '3878'
abstract:
- lang: eng
text: We study the problem of generating a test sequence that achieves maximal coverage
for a reactive system under test. We formulate the problem as a repeated game
between the tester and the system, where the system state space is partitioned
according to some coverage criterion and the objective of the tester is to maximize
the set of partitions (or coverage goals) visited during the game. We show the
complexity of the maximal coverage problem for non-deterministic systems is PSPACE-complete,
but is NP-complete for deterministic systems. For the special case of non-deterministic
systems with a re-initializing “reset” action, which represent running a new test
input on a re-initialized system, we show that the complexity is coNP-complete.
Our proof technique for reset games uses randomized testing strategies that circumvent
the exponentially large memory requirement of deterministic testing strategies.
acknowledgement: This research was supported in part by the NSF grants CCR-0132780
and CNS-0720884.
alternative_title:
- LNCS
article_processing_charge: No
arxiv: 1
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Luca
full_name: De Alfaro, Luca
last_name: De Alfaro
- first_name: Ritankar
full_name: Majumdar, Ritankar
last_name: Majumdar
citation:
ama: 'Chatterjee K, De Alfaro L, Majumdar R. The complexity of coverage. In: 6th
Asian Symposium on Programming Language and Systems. Vol 5356. Springer Nature;
2008:91-106. doi:10.1007/978-3-540-89330-1_7'
apa: 'Chatterjee, K., De Alfaro, L., & Majumdar, R. (2008). The complexity of
coverage. In 6th Asian Symposium on Programming Language and Systems (Vol.
5356, pp. 91–106). Bangalore, India: Springer Nature. https://doi.org/10.1007/978-3-540-89330-1_7'
chicago: Chatterjee, Krishnendu, Luca De Alfaro, and Ritankar Majumdar. “The Complexity
of Coverage.” In 6th Asian Symposium on Programming Language and Systems,
5356:91–106. Springer Nature, 2008. https://doi.org/10.1007/978-3-540-89330-1_7.
ieee: K. Chatterjee, L. De Alfaro, and R. Majumdar, “The complexity of coverage,”
in 6th Asian Symposium on Programming Language and Systems, Bangalore,
India, 2008, vol. 5356, pp. 91–106.
ista: 'Chatterjee K, De Alfaro L, Majumdar R. 2008. The complexity of coverage.
6th Asian Symposium on Programming Language and Systems. APLAS: Asian Symposium
on Programming Languages and Systems, LNCS, vol. 5356, 91–106.'
mla: Chatterjee, Krishnendu, et al. “The Complexity of Coverage.” 6th Asian Symposium
on Programming Language and Systems, vol. 5356, Springer Nature, 2008, pp.
91–106, doi:10.1007/978-3-540-89330-1_7.
short: K. Chatterjee, L. De Alfaro, R. Majumdar, in:, 6th Asian Symposium on Programming
Language and Systems, Springer Nature, 2008, pp. 91–106.
conference:
end_date: 2008-12-11
location: Bangalore, India
name: 'APLAS: Asian Symposium on Programming Languages and Systems'
start_date: 2008-12-09
date_created: 2018-12-11T12:05:40Z
date_published: 2008-12-03T00:00:00Z
date_updated: 2026-05-29T09:59:46Z
day: '03'
doi: 10.1007/978-3-540-89330-1_7
extern: '1'
external_id:
arxiv:
- '0804.4525'
fulldoi: https://doi.org/10.1007/978-3-540-89330-1_7
intvolume: ' 5356'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/0804.4525
month: '12'
oa: 1
oa_version: None
page: 91 - 106
publication: 6th Asian Symposium on Programming Language and Systems
publication_identifier:
eissn:
- 1611-3349
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
publist_id: '2292'
status: public
title: The complexity of coverage
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 5356
year: '2008'
...
---
OA_type: closed access
_id: '3879'
abstract:
- lang: eng
text: Quantitative generalizations of classical languages, which assign to each
word a real number instead of a boolean value, have applications in modeling resource-constrained
computation. We use weighted automata (finite automata with transition weights)
to define several natural classes of quantitative languages over finite and infinite
words; in particular, the real value of an infinite run is computed as the maximum,
limsup, liminf, limit average, or discounted sum of the transition weights. We
define the classical decision problems of automata theory (emptiness, universality,
language inclusion, and language equivalence) in the quantitative setting and
study their computational complexity. As the decidability of language inclusion
remains open for some classes of weighted automata, we introduce a notion of quantitative
simulation that is decidable and implies language inclusion. We also give a complete
characterization of the expressive power of the various classes of weighted automata.
In particular, we show that most classes of weighted automata cannot be determinized.
acknowledgement: Research supported in part by the NSF grants CCR-0132780, CNS-0720884,
and CCR-0225610, by the Swiss National Science Foundation, and by the European COMBEST
project.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Laurent
full_name: Doyen, Laurent
last_name: Doyen
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000−0002−2985−7724
citation:
ama: 'Chatterjee K, Doyen L, Henzinger TA. Quantitative languages. In: 22nd International
Workshop on Computer Science Logic. Vol 5213. Springer Nature; 2008:385-400.
doi:10.1007/978-3-540-87531-4_28'
apa: 'Chatterjee, K., Doyen, L., & Henzinger, T. A. (2008). Quantitative languages.
In 22nd International Workshop on Computer Science Logic (Vol. 5213, pp.
385–400). Bertinoro, Italy: Springer Nature. https://doi.org/10.1007/978-3-540-87531-4_28'
chicago: Chatterjee, Krishnendu, Laurent Doyen, and Thomas A Henzinger. “Quantitative
Languages.” In 22nd International Workshop on Computer Science Logic, 5213:385–400.
Springer Nature, 2008. https://doi.org/10.1007/978-3-540-87531-4_28.
ieee: K. Chatterjee, L. Doyen, and T. A. Henzinger, “Quantitative languages,” in
22nd International Workshop on Computer Science Logic, Bertinoro, Italy,
2008, vol. 5213, pp. 385–400.
ista: 'Chatterjee K, Doyen L, Henzinger TA. 2008. Quantitative languages. 22nd International
Workshop on Computer Science Logic. CSL: Computer Science Logic, LNCS, vol. 5213,
385–400.'
mla: Chatterjee, Krishnendu, et al. “Quantitative Languages.” 22nd International
Workshop on Computer Science Logic, vol. 5213, Springer Nature, 2008, pp.
385–400, doi:10.1007/978-3-540-87531-4_28.
short: K. Chatterjee, L. Doyen, T.A. Henzinger, in:, 22nd International Workshop
on Computer Science Logic, Springer Nature, 2008, pp. 385–400.
conference:
end_date: 2008-09-19
location: Bertinoro, Italy
name: 'CSL: Computer Science Logic'
start_date: 2008-09-16
date_created: 2018-12-11T12:05:40Z
date_published: 2008-09-10T00:00:00Z
date_updated: 2026-05-29T10:05:43Z
day: '10'
doi: 10.1007/978-3-540-87531-4_28
extern: '1'
fulldoi: https://doi.org/10.1007/978-3-540-87531-4_28
intvolume: ' 5213'
language:
- iso: eng
month: '09'
oa_version: None
page: 385 - 400
publication: 22nd International Workshop on Computer Science Logic
publication_identifier:
eissn:
- 1611-3349
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
publist_id: '2293'
status: public
title: Quantitative languages
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 5213
year: '2008'
...
---
OA_type: closed access
_id: '3880'
abstract:
- lang: eng
text: We consider imperfect-information parity games in which strategies rely on
observations that provide imperfect information about the history of a play. To
solve such games, i.e., to determine the winning regions of players and corresponding
winning strategies, one can use the subset construction to build an equivalent
perfect-information game. Recently, an algorithm that avoids the inefficient subset
construction has been proposed. The algorithm performs a fixed-point computation
in a lattice of antichains, thus maintaining a succinct representation of state
sets. However, this representation does not allow to recover winning strategies.
In this paper, we build on the antichain approach to develop an algorithm for
constructing the winning strategies in parity games of imperfect information.
We have implemented this algorithm as a prototype. To our knowledge, this is the
first implementation of a procedure for solving imperfect-information parity games
on graphs.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Dietmar
full_name: Berwanger, Dietmar
last_name: Berwanger
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Laurent
full_name: Doyen, Laurent
last_name: Doyen
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000−0002−2985−7724
- first_name: Sangram
full_name: Raje, Sangram
last_name: Raje
citation:
ama: 'Berwanger D, Chatterjee K, Doyen L, Henzinger TA, Raje S. Strategy construction
for parity games with imperfect information. In: 19th International Conference,
CONCUR 2008. Vol 5201. Schloss Dagstuhl - Leibniz-Zentrum für Informatik;
2008:325-339. doi:10.1007/978-3-540-85361-9'
apa: 'Berwanger, D., Chatterjee, K., Doyen, L., Henzinger, T. A., & Raje, S.
(2008). Strategy construction for parity games with imperfect information. In
19th International Conference, CONCUR 2008 (Vol. 5201, pp. 325–339). Toronto,
Canada: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.1007/978-3-540-85361-9'
chicago: Berwanger, Dietmar, Krishnendu Chatterjee, Laurent Doyen, Thomas A Henzinger,
and Sangram Raje. “Strategy Construction for Parity Games with Imperfect Information.”
In 19th International Conference, CONCUR 2008, 5201:325–39. Schloss Dagstuhl
- Leibniz-Zentrum für Informatik, 2008. https://doi.org/10.1007/978-3-540-85361-9.
ieee: D. Berwanger, K. Chatterjee, L. Doyen, T. A. Henzinger, and S. Raje, “Strategy
construction for parity games with imperfect information,” in 19th International
Conference, CONCUR 2008, Toronto, Canada, 2008, vol. 5201, pp. 325–339.
ista: 'Berwanger D, Chatterjee K, Doyen L, Henzinger TA, Raje S. 2008. Strategy
construction for parity games with imperfect information. 19th International Conference,
CONCUR 2008. CONCUR: Concurrency Theory, LNCS, vol. 5201, 325–339.'
mla: Berwanger, Dietmar, et al. “Strategy Construction for Parity Games with Imperfect
Information.” 19th International Conference, CONCUR 2008, vol. 5201, Schloss
Dagstuhl - Leibniz-Zentrum für Informatik, 2008, pp. 325–39, doi:10.1007/978-3-540-85361-9.
short: D. Berwanger, K. Chatterjee, L. Doyen, T.A. Henzinger, S. Raje, in:, 19th
International Conference, CONCUR 2008, Schloss Dagstuhl - Leibniz-Zentrum für
Informatik, 2008, pp. 325–339.
conference:
end_date: 2008-08-22
location: Toronto, Canada
name: 'CONCUR: Concurrency Theory'
start_date: 2008-08-19
date_created: 2018-12-11T12:05:40Z
date_published: 2008-07-30T00:00:00Z
date_updated: 2026-05-29T09:53:33Z
day: '30'
doi: 10.1007/978-3-540-85361-9
extern: '1'
fulldoi: https://doi.org/10.1007/978-3-540-85361-9
intvolume: ' 5201'
language:
- iso: eng
month: '07'
oa_version: None
page: 325 - 339
publication: 19th International Conference, CONCUR 2008
publication_identifier:
eissn:
- 1611-3349
issn:
- 0302-9743
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
publist_id: '2291'
related_material:
record:
- id: '3863'
relation: later_version
status: public
status: public
title: Strategy construction for parity games with imperfect information
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 5201
year: '2008'
...
---
OA_place: repository
OA_type: green
_id: '3876'
abstract:
- lang: eng
text: We consider two-player games played in real time on game structures with clocks
and parity objectives. The games are concurrent in that at each turn, both players
independently propose a time delay and an action, and the action with the shorter
delay is chosen. To prevent a player from winning by blocking time, we restrict
each player to strategies that ensure that the player cannot be responsible for
causing a zeno run. First, we present an efficient reduction of these games to
turn-based (i.e., nonconcurrent) finite-state (i.e., untimed) parity games. The
states of the resulting game are pairs of clock regions of the original game.
Our reduction improves the best known complexity for solving timed parity games.
Moreover, the rich class of algorithms for classical parity games can now be applied
to timed parity games. Second, we consider two restricted classes of strategies
for the player that represents the controller in a real-time synthesis problem,
namely, limit-robust and bounded-robust strategies. Using a limit-robust strategy,
the controller cannot choose an exact real-valued time delay but must allow for
some nonzero jitter in each of its actions. If there is a given lower bound on
the jitter, then the strategy is bounded-robust. We show that exact strategies
are more powerful than limit-robust strategies, which are more powerful than bounded-robust
strategies for any bound. For both kinds of robust strategies, we present efficient
reductions to standard timed automaton games. These reductions provide algorithms
for the synthesis of robust real-time controllers.
acknowledgement: This research was supported in part by the NSF grants CCR-0132780,
CNS-0720884, and CCR-0225610, and by the European COMBEST project.
alternative_title:
- LNCS
article_processing_charge: No
arxiv: 1
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000−0002−2985−7724
- first_name: Vinayak
full_name: Prabhu, Vinayak
last_name: Prabhu
citation:
ama: 'Chatterjee K, Henzinger TA, Prabhu V. Timed parity games: complexity and robustness.
In: Proceedings of the 6th International Conference on Formal Modeling and
Analysis of Timed Systems. Vol 5215. Springer Nature; 2008:124-140. doi:10.1007/978-3-540-85778-5_10'
apa: 'Chatterjee, K., Henzinger, T. A., & Prabhu, V. (2008). Timed parity games:
complexity and robustness. In Proceedings of the 6th international conference
on Formal Modeling and Analysis of Timed Systems (Vol. 5215, pp. 124–140).
Saint Malo, France: Springer Nature. https://doi.org/10.1007/978-3-540-85778-5_10'
chicago: 'Chatterjee, Krishnendu, Thomas A Henzinger, and Vinayak Prabhu. “Timed
Parity Games: Complexity and Robustness.” In Proceedings of the 6th International
Conference on Formal Modeling and Analysis of Timed Systems, 5215:124–40.
Springer Nature, 2008. https://doi.org/10.1007/978-3-540-85778-5_10.'
ieee: 'K. Chatterjee, T. A. Henzinger, and V. Prabhu, “Timed parity games: complexity
and robustness,” in Proceedings of the 6th international conference on Formal
Modeling and Analysis of Timed Systems, Saint Malo, France, 2008, vol. 5215,
pp. 124–140.'
ista: 'Chatterjee K, Henzinger TA, Prabhu V. 2008. Timed parity games: complexity
and robustness. Proceedings of the 6th international conference on Formal Modeling
and Analysis of Timed Systems. FORMATS: Formal Modeling and Analysis of Timed
Systems, LNCS, vol. 5215, 124–140.'
mla: 'Chatterjee, Krishnendu, et al. “Timed Parity Games: Complexity and Robustness.”
Proceedings of the 6th International Conference on Formal Modeling and Analysis
of Timed Systems, vol. 5215, Springer Nature, 2008, pp. 124–40, doi:10.1007/978-3-540-85778-5_10.'
short: K. Chatterjee, T.A. Henzinger, V. Prabhu, in:, Proceedings of the 6th International
Conference on Formal Modeling and Analysis of Timed Systems, Springer Nature,
2008, pp. 124–140.
conference:
end_date: 2008-09-17
location: Saint Malo, France
name: 'FORMATS: Formal Modeling and Analysis of Timed Systems'
start_date: 2008-09-15
date_created: 2018-12-11T12:05:39Z
date_published: 2008-10-01T00:00:00Z
date_updated: 2026-07-06T13:25:38Z
day: '01'
doi: 10.1007/978-3-540-85778-5_10
extern: '1'
external_id:
arxiv:
- '0807.1165'
fulldoi: https://doi.org/10.1007/978-3-540-85778-5_10
intvolume: ' 5215'
language:
- iso: eng
month: '10'
oa_version: None
page: 124 - 140
publication: Proceedings of the 6th international conference on Formal Modeling and
Analysis of Timed Systems
publication_identifier:
eissn:
- 1611-3349
isbn:
- '9783540857778'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
publist_id: '2294'
related_material:
record:
- id: '3315'
relation: later_version
status: public
status: public
title: 'Timed parity games: complexity and robustness'
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 5215
year: '2008'
...
---
OA_type: closed access
_id: '18320'
abstract:
- lang: eng
text: Presented here is the problem of recovering a dynamic image superimposed on
a static background. Such a problem is ill-posed and may arise e.g. in imaging
through semireflective media, in separation of an illumination image from a reflectance
image, in imaging with diffraction phenomena, etc. In this work we study regularization
of this problem in spirit of Total Variation and general sparsifying transformations.
alternative_title:
- LNISA
article_processing_charge: No
author:
- first_name: Alexander
full_name: Bronstein, Alexander
id: 58f3726e-7cba-11ef-ad8b-e6e8cb3904e6
last_name: Bronstein
orcid: 0000-0001-9699-8730
- first_name: Michael M.
full_name: Bronstein, Michael M.
last_name: Bronstein
- first_name: Michael
full_name: Zibulevsky, Michael
last_name: Zibulevsky
citation:
ama: 'Bronstein AM, Bronstein MM, Zibulevsky M. On separation of semitransparent
dynamic images from static background. In: 6th International Conference on
Independent Component Analysis and Signal Separation. Vol 3889. Springer Nature;
2006:934-940. doi:10.1007/11679363_116'
apa: 'Bronstein, A. M., Bronstein, M. M., & Zibulevsky, M. (2006). On separation
of semitransparent dynamic images from static background. In 6th International
Conference on Independent Component Analysis and Signal Separation (Vol. 3889,
pp. 934–940). Charleston, SC, United States: Springer Nature. https://doi.org/10.1007/11679363_116'
chicago: Bronstein, Alex M., Michael M. Bronstein, and Michael Zibulevsky. “On Separation
of Semitransparent Dynamic Images from Static Background.” In 6th International
Conference on Independent Component Analysis and Signal Separation, 3889:934–40.
Springer Nature, 2006. https://doi.org/10.1007/11679363_116.
ieee: A. M. Bronstein, M. M. Bronstein, and M. Zibulevsky, “On separation of semitransparent
dynamic images from static background,” in 6th International Conference on
Independent Component Analysis and Signal Separation, Charleston, SC, United
States, 2006, vol. 3889, pp. 934–940.
ista: 'Bronstein AM, Bronstein MM, Zibulevsky M. 2006. On separation of semitransparent
dynamic images from static background. 6th International Conference on Independent
Component Analysis and Signal Separation. ICA: International Conference on Independent
Component Analysis and Signal Separation, LNISA, vol. 3889, 934–940.'
mla: Bronstein, Alex M., et al. “On Separation of Semitransparent Dynamic Images
from Static Background.” 6th International Conference on Independent Component
Analysis and Signal Separation, vol. 3889, Springer Nature, 2006, pp. 934–40,
doi:10.1007/11679363_116.
short: A.M. Bronstein, M.M. Bronstein, M. Zibulevsky, in:, 6th International Conference
on Independent Component Analysis and Signal Separation, Springer Nature, 2006,
pp. 934–940.
conference:
end_date: 2006-03-08
location: Charleston, SC, United States
name: 'ICA: International Conference on Independent Component Analysis and Signal
Separation'
start_date: 2006-03-05
date_created: 2024-10-15T11:20:53Z
date_published: 2006-02-13T00:00:00Z
date_updated: 2024-10-22T07:00:45Z
day: '13'
doi: 10.1007/11679363_116
extern: '1'
fulldoi: https://doi.org/10.1007/11679363_116
intvolume: ' 3889'
language:
- iso: eng
month: '02'
oa_version: None
page: 934-940
publication: 6th International Conference on Independent Component Analysis and Signal
Separation
publication_identifier:
eisbn:
- '9783540326311'
eissn:
- 1611-3349
isbn:
- '9783540326304'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: On separation of semitransparent dynamic images from static background
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 3889
year: '2006'
...
---
OA_type: closed access
_id: '18321'
abstract:
- lang: eng
text: Recent studies on three-dimensional face recognition proposed to model facial
expressions as isometries of the facial surface. Based on this model, expression-invariant
signatures of the face were constructed by means of approximate isometric embedding
into flat spaces. Here, we apply a new method for measuring isometry-invariant
similarity between faces by embedding one facial surface into another. We demonstrate
that our approach has several significant advantages, one of which is the ability
to handle partially missing data. Promising face recognition results are obtained
in numerical experiments even when the facial surfaces are severely occluded.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Alexander
full_name: Bronstein, Alexander
id: 58f3726e-7cba-11ef-ad8b-e6e8cb3904e6
last_name: Bronstein
orcid: 0000-0001-9699-8730
- first_name: Michael M.
full_name: Bronstein, Michael M.
last_name: Bronstein
- first_name: Ron
full_name: Kimmel, Ron
last_name: Kimmel
citation:
ama: 'Bronstein AM, Bronstein MM, Kimmel R. Robust expression-invariant face recognition
from partially missing data. In: 9th European Conference on Computer Vision.
Vol 3953. Springer Nature; 2006. doi:10.1007/11744078_31'
apa: 'Bronstein, A. M., Bronstein, M. M., & Kimmel, R. (2006). Robust expression-invariant
face recognition from partially missing data. In 9th European Conference on
Computer Vision (Vol. 3953). Graz, Austria: Springer Nature. https://doi.org/10.1007/11744078_31'
chicago: Bronstein, Alex M., Michael M. Bronstein, and Ron Kimmel. “Robust Expression-Invariant
Face Recognition from Partially Missing Data.” In 9th European Conference on
Computer Vision, Vol. 3953. Springer Nature, 2006. https://doi.org/10.1007/11744078_31.
ieee: A. M. Bronstein, M. M. Bronstein, and R. Kimmel, “Robust expression-invariant
face recognition from partially missing data,” in 9th European Conference on
Computer Vision, Graz, Austria, 2006, vol. 3953.
ista: 'Bronstein AM, Bronstein MM, Kimmel R. 2006. Robust expression-invariant face
recognition from partially missing data. 9th European Conference on Computer Vision.
ECCV: European Conference on Computer Vision, LNCS, vol. 3953.'
mla: Bronstein, Alex M., et al. “Robust Expression-Invariant Face Recognition from
Partially Missing Data.” 9th European Conference on Computer Vision, vol.
3953, Springer Nature, 2006, doi:10.1007/11744078_31.
short: A.M. Bronstein, M.M. Bronstein, R. Kimmel, in:, 9th European Conference on
Computer Vision, Springer Nature, 2006.
conference:
end_date: 2006-05-13
location: Graz, Austria
name: 'ECCV: European Conference on Computer Vision'
start_date: 2006-05-07
date_created: 2024-10-15T11:20:53Z
date_published: 2006-01-01T00:00:00Z
date_updated: 2024-10-22T06:46:14Z
doi: 10.1007/11744078_31
extern: '1'
fulldoi: https://doi.org/10.1007/11744078_31
intvolume: ' 3953'
language:
- iso: eng
month: '01'
oa_version: None
publication: 9th European Conference on Computer Vision
publication_identifier:
eisbn:
- '9783540338376'
eissn:
- 1611-3349
isbn:
- '9783540338369'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Robust expression-invariant face recognition from partially missing data
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 3953
year: '2006'
...
---
OA_type: closed access
_id: '18322'
abstract:
- lang: eng
text: A geometric framework for finding intrinsic correspondence between animated
3D faces is presented. We model facial expressions as isometries of the facial
surface and find the correspondence between two faces as the minimum-distortion
mapping. Generalized multidimensional scaling is used for this goal. We apply
our approach to texture mapping onto 3D video, expression exaggeration and morphing
between faces.
alternative_title:
- LNIP
article_processing_charge: No
author:
- first_name: Alexander
full_name: Bronstein, Alexander
id: 58f3726e-7cba-11ef-ad8b-e6e8cb3904e6
last_name: Bronstein
orcid: 0000-0001-9699-8730
- first_name: Michael M.
full_name: Bronstein, Michael M.
last_name: Bronstein
- first_name: Ron
full_name: Kimmel, Ron
last_name: Kimmel
citation:
ama: 'Bronstein AM, Bronstein MM, Kimmel R. Facetoface: An isometric model for facial
animation. In: 4th International Conference on Articulated Motion and Deformable
Objects. Vol 4069. Springer Nature; 2006:38-47. doi:10.1007/11789239_5'
apa: 'Bronstein, A. M., Bronstein, M. M., & Kimmel, R. (2006). Facetoface: An
isometric model for facial animation. In 4th International Conference on Articulated
Motion and Deformable Objects (Vol. 4069, pp. 38–47). Mallorca, Spain: Springer
Nature. https://doi.org/10.1007/11789239_5'
chicago: 'Bronstein, Alex M., Michael M. Bronstein, and Ron Kimmel. “Facetoface:
An Isometric Model for Facial Animation.” In 4th International Conference on
Articulated Motion and Deformable Objects, 4069:38–47. Springer Nature, 2006.
https://doi.org/10.1007/11789239_5.'
ieee: 'A. M. Bronstein, M. M. Bronstein, and R. Kimmel, “Facetoface: An isometric
model for facial animation,” in 4th International Conference on Articulated
Motion and Deformable Objects, Mallorca, Spain, 2006, vol. 4069, pp. 38–47.'
ista: 'Bronstein AM, Bronstein MM, Kimmel R. 2006. Facetoface: An isometric model
for facial animation. 4th International Conference on Articulated Motion and Deformable
Objects. AMDO: Conference on Articulated Motion and Deformable Objects, LNIP,
vol. 4069, 38–47.'
mla: 'Bronstein, Alex M., et al. “Facetoface: An Isometric Model for Facial Animation.”
4th International Conference on Articulated Motion and Deformable Objects,
vol. 4069, Springer Nature, 2006, pp. 38–47, doi:10.1007/11789239_5.'
short: A.M. Bronstein, M.M. Bronstein, R. Kimmel, in:, 4th International Conference
on Articulated Motion and Deformable Objects, Springer Nature, 2006, pp. 38–47.
conference:
end_date: 2006-07-14
location: Mallorca, Spain
name: 'AMDO: Conference on Articulated Motion and Deformable Objects'
start_date: 2006-07-11
date_created: 2024-10-15T11:20:53Z
date_published: 2006-07-18T00:00:00Z
date_updated: 2024-10-22T06:42:42Z
day: '18'
doi: 10.1007/11789239_5
extern: '1'
fulldoi: https://doi.org/10.1007/11789239_5
intvolume: ' 4069'
language:
- iso: eng
month: '07'
oa_version: None
page: 38-47
publication: 4th International Conference on Articulated Motion and Deformable Objects
publication_identifier:
eisbn:
- '9783540360322'
eissn:
- 1611-3349
isbn:
- '9783540360315'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Facetoface: An isometric model for facial animation'
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 4069
year: '2006'
...
---
OA_type: closed access
_id: '18323'
abstract:
- lang: eng
text: We present a theoretical and computational framework for matching of two-dimensional
articulated shapes. Assuming that articulations can be modeled as near-isometries,
we show an axiomatic construction of an articulation-invariant distance between
shapes, formulated as a generalized multidimensional scaling (GMDS) problem and
solved efficiently. Some numerical results demonstrating the accuracy of our method
are presented.
alternative_title:
- LNIP
article_processing_charge: No
author:
- first_name: Alexander
full_name: Bronstein, Alexander
id: 58f3726e-7cba-11ef-ad8b-e6e8cb3904e6
last_name: Bronstein
orcid: 0000-0001-9699-8730
- first_name: Michael M.
full_name: Bronstein, Michael M.
last_name: Bronstein
- first_name: Alfred M.
full_name: Bruckstein, Alfred M.
last_name: Bruckstein
- first_name: Ron
full_name: Kimmel, Ron
last_name: Kimmel
citation:
ama: 'Bronstein AM, Bronstein MM, Bruckstein AM, Kimmel R. Matching two-dimensional
articulated shapes using generalized multidimensional scaling. In: 4th International
Conference on Articulated Motion and Deformable Objects. Vol 4069. Springer
Nature; 2006:48-57. doi:10.1007/11789239_6'
apa: 'Bronstein, A. M., Bronstein, M. M., Bruckstein, A. M., & Kimmel, R. (2006).
Matching two-dimensional articulated shapes using generalized multidimensional
scaling. In 4th International Conference on Articulated Motion and Deformable
Objects (Vol. 4069, pp. 48–57). Mallorca, Spain: Springer Nature. https://doi.org/10.1007/11789239_6'
chicago: Bronstein, Alex M., Michael M. Bronstein, Alfred M. Bruckstein, and Ron
Kimmel. “Matching Two-Dimensional Articulated Shapes Using Generalized Multidimensional
Scaling.” In 4th International Conference on Articulated Motion and Deformable
Objects, 4069:48–57. Springer Nature, 2006. https://doi.org/10.1007/11789239_6.
ieee: A. M. Bronstein, M. M. Bronstein, A. M. Bruckstein, and R. Kimmel, “Matching
two-dimensional articulated shapes using generalized multidimensional scaling,”
in 4th International Conference on Articulated Motion and Deformable Objects,
Mallorca, Spain, 2006, vol. 4069, pp. 48–57.
ista: 'Bronstein AM, Bronstein MM, Bruckstein AM, Kimmel R. 2006. Matching two-dimensional
articulated shapes using generalized multidimensional scaling. 4th International
Conference on Articulated Motion and Deformable Objects. AMDO: Conference on Articulated
Motion and Deformable Objects, LNIP, vol. 4069, 48–57.'
mla: Bronstein, Alex M., et al. “Matching Two-Dimensional Articulated Shapes Using
Generalized Multidimensional Scaling.” 4th International Conference on Articulated
Motion and Deformable Objects, vol. 4069, Springer Nature, 2006, pp. 48–57,
doi:10.1007/11789239_6.
short: A.M. Bronstein, M.M. Bronstein, A.M. Bruckstein, R. Kimmel, in:, 4th International
Conference on Articulated Motion and Deformable Objects, Springer Nature, 2006,
pp. 48–57.
conference:
end_date: 2006-07-14
location: Mallorca, Spain
name: 'AMDO: Conference on Articulated Motion and Deformable Objects'
start_date: 2006-07-11
date_created: 2024-10-15T11:20:53Z
date_published: 2006-07-18T00:00:00Z
date_updated: 2024-10-22T06:35:45Z
day: '18'
doi: 10.1007/11789239_6
extern: '1'
fulldoi: https://doi.org/10.1007/11789239_6
intvolume: ' 4069'
language:
- iso: eng
month: '07'
oa_version: None
page: 48-57
publication: 4th International Conference on Articulated Motion and Deformable Objects
publication_identifier:
eisbn:
- '9783540360322'
eissn:
- 1611-3349
isbn:
- '9783540360315'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Matching two-dimensional articulated shapes using generalized multidimensional
scaling
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 4069
year: '2006'
...
---
OA_type: closed access
_id: '4551'
abstract:
- lang: eng
text: "We consider Markov decision processes (MDPs) with multiple discounted reward
objectives. Such MDPs occur in design problems where one wishes to simultaneously
optimize several criteria, for example, latency and power. The possible trade-offs
between the different objectives are characterized by the Pareto curve. We show
that every Pareto-optimal point can be achieved by a memoryless strategy; however,
unlike in the single-objective case, the memoryless strategy may require randomization.
Moreover, we show that the Pareto curve can be approximated in polynomial time
in the size of the MDP. Additionally, we study the problem if a given value vector
is realizable by any strategy, and show that it can be decided in polynomial time;
but the question whether it is realizable by a deterministic memoryless strategy
is NP-complete. These results provide efficient algorithms for design exploration
in MDP models with multiple objectives.\r\nThis research was supported in part
by the AFOSR MURI grant F49620-00-1-0327, and the NSF grants CCR-0225610, CCR-0234690,
and CCR-0427202. "
acknowledgement: This research was supported in part by the AFOSR MURI grant F49620-00-1-0327,
and the NSF grants CCR-0225610, CCR-0234690, and CCR-0427202.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Ritankar
full_name: Majumdar, Ritankar
last_name: Majumdar
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000−0002−2985−7724
citation:
ama: 'Chatterjee K, Majumdar R, Henzinger TA. Markov decision processes with multiple
objectives. In: Proceedings of the 23rd Annual Conference on Theoretical Aspects
of Computer Science. Vol 3884. Springer; 2006:325-336. doi:10.1007/11672142_26'
apa: 'Chatterjee, K., Majumdar, R., & Henzinger, T. A. (2006). Markov decision
processes with multiple objectives. In Proceedings of the 23rd Annual conference
on Theoretical Aspects of Computer Science (Vol. 3884, pp. 325–336). Marseille,
France: Springer. https://doi.org/10.1007/11672142_26'
chicago: Chatterjee, Krishnendu, Ritankar Majumdar, and Thomas A Henzinger. “Markov
Decision Processes with Multiple Objectives.” In Proceedings of the 23rd Annual
Conference on Theoretical Aspects of Computer Science, 3884:325–36. Springer,
2006. https://doi.org/10.1007/11672142_26.
ieee: K. Chatterjee, R. Majumdar, and T. A. Henzinger, “Markov decision processes
with multiple objectives,” in Proceedings of the 23rd Annual conference on
Theoretical Aspects of Computer Science, Marseille, France, 2006, vol. 3884,
pp. 325–336.
ista: 'Chatterjee K, Majumdar R, Henzinger TA. 2006. Markov decision processes with
multiple objectives. Proceedings of the 23rd Annual conference on Theoretical
Aspects of Computer Science. STACS: Theoretical Aspects of Computer Science, LNCS,
vol. 3884, 325–336.'
mla: Chatterjee, Krishnendu, et al. “Markov Decision Processes with Multiple Objectives.”
Proceedings of the 23rd Annual Conference on Theoretical Aspects of Computer
Science, vol. 3884, Springer, 2006, pp. 325–36, doi:10.1007/11672142_26.
short: K. Chatterjee, R. Majumdar, T.A. Henzinger, in:, Proceedings of the 23rd
Annual Conference on Theoretical Aspects of Computer Science, Springer, 2006,
pp. 325–336.
conference:
end_date: 2006-02-25
location: Marseille, France
name: 'STACS: Theoretical Aspects of Computer Science'
start_date: 2006-02-23
date_created: 2018-12-11T12:09:26Z
date_published: 2006-02-14T00:00:00Z
date_updated: 2026-08-21T09:46:06Z
day: '14'
doi: 10.1007/11672142_26
extern: '1'
fulldoi: https://doi.org/10.1007/11672142_26
intvolume: ' 3884'
language:
- iso: eng
month: '02'
oa_version: None
page: 325 - 336
publication: Proceedings of the 23rd Annual conference on Theoretical Aspects of Computer
Science
publication_identifier:
eisbn:
- '9783540322887'
isbn:
- '9783540323013'
issn:
- 0302-9743
publication_status: published
publisher: Springer
publist_id: '161'
status: public
title: Markov decision processes with multiple objectives
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 3884
year: '2006'
...
---
OA_type: closed access
_id: '4538'
abstract:
- lang: eng
text: A stochastic graph game is played by two players on a game graph with probabilistic
transitions. We consider stochastic graph games with ω-regular winning conditions
specified as parity objectives. These games lie in NP ∩ coNP. We present a strategy
improvement algorithm for stochastic parity games; this is the first non-brute-force
algorithm for solving these games. From the strategy improvement algorithm we
obtain a randomized subexponential-time algorithm to solve such games.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000−0002−2985−7724
citation:
ama: 'Chatterjee K, Henzinger TA. Strategy improvement and randomized subexponential
algorithms for stochastic parity games. In: Proceedings of the 23rd Annual
Conference on Theoretical Aspects of Computer Science. Vol 3884. Springer;
2006:512-523. doi:10.1007/11672142_42'
apa: 'Chatterjee, K., & Henzinger, T. A. (2006). Strategy improvement and randomized
subexponential algorithms for stochastic parity games. In Proceedings of the
23rd Annual conference on Theoretical Aspects of Computer Science (Vol. 3884,
pp. 512–523). Marseille, France: Springer. https://doi.org/10.1007/11672142_42'
chicago: Chatterjee, Krishnendu, and Thomas A Henzinger. “Strategy Improvement and
Randomized Subexponential Algorithms for Stochastic Parity Games.” In Proceedings
of the 23rd Annual Conference on Theoretical Aspects of Computer Science,
3884:512–23. Springer, 2006. https://doi.org/10.1007/11672142_42.
ieee: K. Chatterjee and T. A. Henzinger, “Strategy improvement and randomized subexponential
algorithms for stochastic parity games,” in Proceedings of the 23rd Annual
conference on Theoretical Aspects of Computer Science, Marseille, France,
2006, vol. 3884, pp. 512–523.
ista: 'Chatterjee K, Henzinger TA. 2006. Strategy improvement and randomized subexponential
algorithms for stochastic parity games. Proceedings of the 23rd Annual conference
on Theoretical Aspects of Computer Science. STACS: Theoretical Aspects of Computer
Science, LNCS, vol. 3884, 512–523.'
mla: Chatterjee, Krishnendu, and Thomas A. Henzinger. “Strategy Improvement and
Randomized Subexponential Algorithms for Stochastic Parity Games.” Proceedings
of the 23rd Annual Conference on Theoretical Aspects of Computer Science,
vol. 3884, Springer, 2006, pp. 512–23, doi:10.1007/11672142_42.
short: K. Chatterjee, T.A. Henzinger, in:, Proceedings of the 23rd Annual Conference
on Theoretical Aspects of Computer Science, Springer, 2006, pp. 512–523.
conference:
end_date: 2006-02-25
location: Marseille, France
name: 'STACS: Theoretical Aspects of Computer Science'
start_date: 2006-02-23
date_created: 2018-12-11T12:09:22Z
date_published: 2006-02-14T00:00:00Z
date_updated: 2026-08-21T10:42:04Z
day: '14'
doi: 10.1007/11672142_42
extern: '1'
fulldoi: https://doi.org/10.1007/11672142_42
intvolume: ' 3884'
language:
- iso: eng
month: '02'
oa_version: None
page: 512 - 523
publication: Proceedings of the 23rd Annual conference on Theoretical Aspects of Computer
Science
publication_identifier:
eisbn:
- '9783540322887'
eissn:
- 1611-3349
isbn:
- '9783540323013'
issn:
- 0302-9743
publication_status: published
publisher: Springer
publist_id: '184'
status: public
title: Strategy improvement and randomized subexponential algorithms for stochastic
parity games
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 3884
year: '2006'
...
---
OA_type: closed access
_id: '4437'
abstract:
- lang: eng
text: The synthesis of reactive systems requires the solution of two-player games
on graphs with ω-regular objectives. When the objective is specified by a linear
temporal logic formula or nondeterministic Büchi automaton, then previous algorithms
for solving the game require the construction of an equivalent deterministic automaton.
However, determinization for automata on infinite words is extremely complicated,
and current implementations fail to produce deterministic automata even for relatively
small inputs. We show how to construct, from a given nondeterministic Büchi automaton,
an equivalent nondeterministic parity automaton that is good for solving games
with objective . The main insight is that a nondeterministic automaton is good
for solving games if it fairly simulates the equivalent deterministic automaton.
In this way, we omit the determinization step in game solving and reactive synthesis.
The fact that our automata are nondeterministic makes them surprisingly simple,
amenable to symbolic implementation, and allows an incremental search for winning
strategies.
acknowledgement: This research was supported in part by the Swiss National Science
Foundation.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000−0002−2985−7724
- first_name: Nir
full_name: Piterman, Nir
last_name: Piterman
citation:
ama: 'Henzinger TA, Piterman N. Solving games without determinization. In: Proceedings
of the 20th International Conference on Computer Science Logic. Vol 4207.
Springer; 2006:395-410. doi:10.1007/11874683_26'
apa: 'Henzinger, T. A., & Piterman, N. (2006). Solving games without determinization.
In Proceedings of the 20th international conference on Computer Science Logic
(Vol. 4207, pp. 395–410). Szeged, Hungary: Springer. https://doi.org/10.1007/11874683_26'
chicago: Henzinger, Thomas A, and Nir Piterman. “Solving Games without Determinization.”
In Proceedings of the 20th International Conference on Computer Science Logic,
4207:395–410. Springer, 2006. https://doi.org/10.1007/11874683_26.
ieee: T. A. Henzinger and N. Piterman, “Solving games without determinization,”
in Proceedings of the 20th international conference on Computer Science Logic,
Szeged, Hungary, 2006, vol. 4207, pp. 395–410.
ista: 'Henzinger TA, Piterman N. 2006. Solving games without determinization. Proceedings
of the 20th international conference on Computer Science Logic. CSL: Computer
Science Logic, LNCS, vol. 4207, 395–410.'
mla: Henzinger, Thomas A., and Nir Piterman. “Solving Games without Determinization.”
Proceedings of the 20th International Conference on Computer Science Logic,
vol. 4207, Springer, 2006, pp. 395–410, doi:10.1007/11874683_26.
short: T.A. Henzinger, N. Piterman, in:, Proceedings of the 20th International Conference
on Computer Science Logic, Springer, 2006, pp. 395–410.
conference:
end_date: 2006-09-29
location: Szeged, Hungary
name: 'CSL: Computer Science Logic'
start_date: 2006-09-25
date_created: 2018-12-11T12:08:51Z
date_published: 2006-09-20T00:00:00Z
date_updated: 2026-08-21T11:30:47Z
day: '20'
doi: 10.1007/11874683_26
extern: '1'
fulldoi: https://doi.org/10.1007/11874683_26
intvolume: ' 4207'
language:
- iso: eng
month: '09'
oa_version: None
page: 395 - 410
publication: Proceedings of the 20th international conference on Computer Science
Logic
publication_identifier:
eisbn:
- '9783540454595'
eissn:
- 1611-3349
isbn:
- '9783540454588'
issn:
- 0302-9743
publication_status: published
publisher: Springer
publist_id: '295'
status: public
title: Solving games without determinization
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 4207
year: '2006'
...
---
OA_type: closed access
_id: '4406'
abstract:
- lang: eng
text: We propose and evaluate a new algorithm for checking the universality of nondeterministic
finite automata. In contrast to the standard algorithm, which uses the subset
construction to explicitly determinize the automaton, we keep the determinization
step implicit. Our algorithm computes the least fixed point of a monotone function
on the lattice of antichains of state sets. We evaluate the performance of our
algorithm experimentally using the random automaton model recently proposed by
Tabakov and Vardi. We show that on the difficult instances of this probabilistic
model, the antichain algorithm outperforms the standard one by several orders
of magnitude. We also show how variations of the antichain method can be used
for solving the language-inclusion problem for nondeterministic finite automata,
and the emptiness problem for alternating finite automata.
acknowledgement: This research was supported in part by the NSF grants CCR-0234690
and CCR-0225610, and the Belgian FNRS grant 2.4530.02 of the FRFC project “Centre
Fédéré en Vérification.”
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Martin
full_name: De Wulf, Martin
last_name: De Wulf
- first_name: Laurent
full_name: Doyen, Laurent
last_name: Doyen
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000−0002−2985−7724
- first_name: Jean
full_name: Raskin, Jean
last_name: Raskin
citation:
ama: 'De Wulf M, Doyen L, Henzinger TA, Raskin J. Antichains: A new algorithm for
checking universality of finite automata. In: Proceedings of the 18th International
Conference on Computer Aided Verification. Vol 4144. Springer Nature; 2006:17-30.
doi:10.1007/11817963_5'
apa: 'De Wulf, M., Doyen, L., Henzinger, T. A., & Raskin, J. (2006). Antichains:
A new algorithm for checking universality of finite automata. In Proceedings
of the 18th international conference on Computer Aided Verification (Vol.
4144, pp. 17–30). Seattle, WA, United States: Springer Nature. https://doi.org/10.1007/11817963_5'
chicago: 'De Wulf, Martin, Laurent Doyen, Thomas A Henzinger, and Jean Raskin. “Antichains:
A New Algorithm for Checking Universality of Finite Automata.” In Proceedings
of the 18th International Conference on Computer Aided Verification, 4144:17–30.
Springer Nature, 2006. https://doi.org/10.1007/11817963_5.'
ieee: 'M. De Wulf, L. Doyen, T. A. Henzinger, and J. Raskin, “Antichains: A new
algorithm for checking universality of finite automata,” in Proceedings of
the 18th international conference on Computer Aided Verification, Seattle,
WA, United States, 2006, vol. 4144, pp. 17–30.'
ista: 'De Wulf M, Doyen L, Henzinger TA, Raskin J. 2006. Antichains: A new algorithm
for checking universality of finite automata. Proceedings of the 18th international
conference on Computer Aided Verification. CAV: Computer Aided Verification, LNCS,
vol. 4144, 17–30.'
mla: 'De Wulf, Martin, et al. “Antichains: A New Algorithm for Checking Universality
of Finite Automata.” Proceedings of the 18th International Conference on Computer
Aided Verification, vol. 4144, Springer Nature, 2006, pp. 17–30, doi:10.1007/11817963_5.'
short: M. De Wulf, L. Doyen, T.A. Henzinger, J. Raskin, in:, Proceedings of the
18th International Conference on Computer Aided Verification, Springer Nature,
2006, pp. 17–30.
conference:
end_date: 2006-08-20
location: Seattle, WA, United States
name: 'CAV: Computer Aided Verification'
start_date: 2006-08-17
date_created: 2018-12-11T12:08:41Z
date_published: 2006-08-08T00:00:00Z
date_updated: 2026-08-21T11:47:59Z
day: '08'
doi: 10.1007/11817963_5
extern: '1'
fulldoi: https://doi.org/10.1007/11817963_5
intvolume: ' 4144'
language:
- iso: eng
month: '08'
oa_version: None
page: 17 - 30
publication: Proceedings of the 18th international conference on Computer Aided Verification
publication_identifier:
eisbn:
- '9783540374114'
eissn:
- 1611-3349
isbn:
- '9783540374060'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
publist_id: '326'
status: public
title: 'Antichains: A new algorithm for checking universality of finite automata'
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 4144
year: '2006'
...
---
OA_type: closed access
_id: '4432'
abstract:
- lang: eng
text: We add freeze quantifiers to the game logic ATL in order to specify real-time
objectives for games played on timed structures. We define the semantics of the
resulting logic TATL by restricting the players to physically meaningful strategies,
which do not prevent time from diverging. We show that TATL can be model checked
over timed automaton games. We also specify timed optimization problems for physically
meaningful strategies, and we show that for timed automaton games, the optimal
answers can be approximated to within any degree of precision.
acknowledgement: This research was supported in part by the NSF grants CCR-0208875,
CCR-0225610, and CCR-0234690.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000−0002−2985−7724
- first_name: Vinayak
full_name: Prabhu, Vinayak
last_name: Prabhu
citation:
ama: 'Henzinger TA, Prabhu V. Timed alternating-time temporal logic. In: Proceedings
of the 4th International Conference on Formal Modeling and Analysis of Timed Systems.
Vol 4202. Springer Nature; 2006:1-17. doi:10.1007/11867340_1'
apa: 'Henzinger, T. A., & Prabhu, V. (2006). Timed alternating-time temporal
logic. In Proceedings of the 4th international conference on Formal Modeling
and Analysis of Timed Systems (Vol. 4202, pp. 1–17). Paris, France: Springer
Nature. https://doi.org/10.1007/11867340_1'
chicago: Henzinger, Thomas A, and Vinayak Prabhu. “Timed Alternating-Time Temporal
Logic.” In Proceedings of the 4th International Conference on Formal Modeling
and Analysis of Timed Systems, 4202:1–17. Springer Nature, 2006. https://doi.org/10.1007/11867340_1.
ieee: T. A. Henzinger and V. Prabhu, “Timed alternating-time temporal logic,” in
Proceedings of the 4th international conference on Formal Modeling and Analysis
of Timed Systems, Paris, France, 2006, vol. 4202, pp. 1–17.
ista: 'Henzinger TA, Prabhu V. 2006. Timed alternating-time temporal logic. Proceedings
of the 4th international conference on Formal Modeling and Analysis of Timed Systems.
FORMATS: Formal Modeling and Analysis of Timed Systems, LNCS, vol. 4202, 1–17.'
mla: Henzinger, Thomas A., and Vinayak Prabhu. “Timed Alternating-Time Temporal
Logic.” Proceedings of the 4th International Conference on Formal Modeling
and Analysis of Timed Systems, vol. 4202, Springer Nature, 2006, pp. 1–17,
doi:10.1007/11867340_1.
short: T.A. Henzinger, V. Prabhu, in:, Proceedings of the 4th International Conference
on Formal Modeling and Analysis of Timed Systems, Springer Nature, 2006, pp. 1–17.
conference:
end_date: 2006-09-27
location: Paris, France
name: 'FORMATS: Formal Modeling and Analysis of Timed Systems'
start_date: 2006-09-25
date_created: 2018-12-11T12:08:49Z
date_published: 2006-09-19T00:00:00Z
date_updated: 2026-08-21T11:39:08Z
day: '19'
doi: 10.1007/11867340_1
extern: '1'
fulldoi: https://doi.org/10.1007/11867340_1
intvolume: ' 4202'
language:
- iso: eng
month: '09'
oa_version: None
page: 1 - 17
publication: Proceedings of the 4th international conference on Formal Modeling and
Analysis of Timed Systems
publication_identifier:
eisbn:
- '9783540450313'
eissn:
- 1611-3349
isbn:
- '9783540450269'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
publist_id: '296'
status: public
title: Timed alternating-time temporal logic
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 4202
year: '2006'
...
---
OA_type: closed access
_id: '4431'
abstract:
- lang: eng
text: 'We summarize some current trends in embedded systems design and point out
some of their characteristics, such as the chasm between analytical and computational
models, and the gap between safety-critical and best-effort engineering practices.
We call for a coherent scientific foundation for embedded systems design, and
we discuss a few key demands on such a foundation: the need for encompassing several
manifestations of heterogeneity, and the need for constructivity in design. We
believe that the development of a satisfactory Embedded Systems Design Science
provides a timely challenge and opportunity for reinvigorating computer science.'
acknowledgement: Supported in part by the ARTIST2 European Network of Excellence on
Embedded Systems Design, by the NSF ITR Center on Hybrid and Embedded Software Systems
(CHESS), and by the SNSF NCCR on Mobile Information and Communication Systems (MICS).
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000−0002−2985−7724
- first_name: Joseph
full_name: Sifakis, Joseph
last_name: Sifakis
citation:
ama: 'Henzinger TA, Sifakis J. The embedded systems design challenge. In: Proceedings
of the 14th International Conference on Formal Methods. Vol 4085. Springer
Nature; 2006:1-15. doi:10.1007/11813040_1'
apa: 'Henzinger, T. A., & Sifakis, J. (2006). The embedded systems design challenge.
In Proceedings of the 14th international conference on Formal Methods (Vol.
4085, pp. 1–15). Hamilton, Canada: Springer Nature. https://doi.org/10.1007/11813040_1'
chicago: Henzinger, Thomas A, and Joseph Sifakis. “The Embedded Systems Design Challenge.”
In Proceedings of the 14th International Conference on Formal Methods,
4085:1–15. Springer Nature, 2006. https://doi.org/10.1007/11813040_1.
ieee: T. A. Henzinger and J. Sifakis, “The embedded systems design challenge,” in
Proceedings of the 14th international conference on Formal Methods, Hamilton,
Canada, 2006, vol. 4085, pp. 1–15.
ista: 'Henzinger TA, Sifakis J. 2006. The embedded systems design challenge. Proceedings
of the 14th international conference on Formal Methods. FM: Formal Methods, LNCS,
vol. 4085, 1–15.'
mla: Henzinger, Thomas A., and Joseph Sifakis. “The Embedded Systems Design Challenge.”
Proceedings of the 14th International Conference on Formal Methods, vol.
4085, Springer Nature, 2006, pp. 1–15, doi:10.1007/11813040_1.
short: T.A. Henzinger, J. Sifakis, in:, Proceedings of the 14th International Conference
on Formal Methods, Springer Nature, 2006, pp. 1–15.
conference:
end_date: 2006-08-27
location: Hamilton, Canada
name: 'FM: Formal Methods'
start_date: 2006-08-21
date_created: 2018-12-11T12:08:49Z
date_published: 2006-08-10T00:00:00Z
date_updated: 2026-08-21T11:43:39Z
day: '10'
doi: 10.1007/11813040_1
extern: '1'
fulldoi: https://doi.org/10.1007/11813040_1
intvolume: ' 4085'
language:
- iso: eng
month: '08'
oa_version: None
page: 1 - 15
publication: Proceedings of the 14th international conference on Formal Methods
publication_identifier:
eisbn:
- '9783540372165'
eissn:
- 1611-3349
isbn:
- '9783540372158'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
publist_id: '301'
status: public
title: The embedded systems design challenge
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 4085
year: '2006'
...
---
OA_type: closed access
_id: '3889'
abstract:
- lang: eng
text: We study observation-based strategies for two-player turn-based games on graphs
with omega-regular objectives. An observation-based strategy relies on imperfect
information about the history of a play, namely, on the past sequence of observations.
Such games occur in the synthesis of a controller that does not see the private
state of the plant. Our main results are twofold. First, we give a fixed-point
algorithm for computing the set of states from which a player can win with a deterministic
observation-based strategy for any omega-regular objective. The fixed point is
computed in the lattice of antichains of state sets. This algorithm has the advantages
of being directed by the objective and of avoiding an explicit subset construction
on the game graph. Second, we give an algorithm for computing the set of states
from which a player can win with probability 1 with a randomized observation-based
strategy for a Buchi objective. This set is of interest because in the absence
of perfect information, randomized strategies are more powerful than deterministic
ones. We show that our algorithms are optimal by proving matching lower bounds.
acknowledgement: This research was supported in part by the NSF grants CCR-0225610
and CCR-0234690, by the SNSF under the Indo-Swiss Joint Research Programme, and
by the FRFC project “Centre Fédéré en Vérification” funded by the FNRS under grant
2.4530.02.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Laurent
full_name: Doyen, Laurent
last_name: Doyen
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000−0002−2985−7724
- first_name: Jean
full_name: Raskin, Jean
last_name: Raskin
citation:
ama: 'Chatterjee K, Doyen L, Henzinger TA, Raskin J. Algorithms for omega-regular
games with imperfect information. In: Proceedings of the 20th International
Conference on Computer Science Logic. Vol 4207. Springer Nature; 2006:287-302.
doi:10.1007/11874683_19'
apa: 'Chatterjee, K., Doyen, L., Henzinger, T. A., & Raskin, J. (2006). Algorithms
for omega-regular games with imperfect information. In Proceedings of the 20th
international conference on Computer Science Logic (Vol. 4207, pp. 287–302).
Szeged, Hungary: Springer Nature. https://doi.org/10.1007/11874683_19'
chicago: Chatterjee, Krishnendu, Laurent Doyen, Thomas A Henzinger, and Jean Raskin.
“Algorithms for Omega-Regular Games with Imperfect Information.” In Proceedings
of the 20th International Conference on Computer Science Logic, 4207:287–302.
Springer Nature, 2006. https://doi.org/10.1007/11874683_19.
ieee: K. Chatterjee, L. Doyen, T. A. Henzinger, and J. Raskin, “Algorithms for omega-regular
games with imperfect information,” in Proceedings of the 20th international
conference on Computer Science Logic, Szeged, Hungary, 2006, vol. 4207, pp.
287–302.
ista: 'Chatterjee K, Doyen L, Henzinger TA, Raskin J. 2006. Algorithms for omega-regular
games with imperfect information. Proceedings of the 20th international conference
on Computer Science Logic. CSL: Computer Science Logic, LNCS, vol. 4207, 287–302.'
mla: Chatterjee, Krishnendu, et al. “Algorithms for Omega-Regular Games with Imperfect
Information.” Proceedings of the 20th International Conference on Computer
Science Logic, vol. 4207, Springer Nature, 2006, pp. 287–302, doi:10.1007/11874683_19.
short: K. Chatterjee, L. Doyen, T.A. Henzinger, J. Raskin, in:, Proceedings of the
20th International Conference on Computer Science Logic, Springer Nature, 2006,
pp. 287–302.
conference:
end_date: 2006-09-29
location: Szeged, Hungary
name: 'CSL: Computer Science Logic'
start_date: 2006-09-25
date_created: 2018-12-11T12:05:43Z
date_published: 2006-11-13T00:00:00Z
date_updated: 2026-08-27T08:04:08Z
day: '13'
doi: 10.1007/11874683_19
extern: '1'
fulldoi: https://doi.org/10.1007/11874683_19
intvolume: ' 4207'
language:
- iso: eng
month: '11'
oa_version: None
page: 287 - 302
publication: Proceedings of the 20th international conference on Computer Science
Logic
publication_identifier:
eisbn:
- '9783540454595'
eissn:
- 1611-3349
isbn:
- '9783540454588'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
publist_id: '2276'
status: public
title: Algorithms for omega-regular games with imperfect information
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 4207
year: '2006'
...
---
OA_type: closed access
_id: '3679'
abstract:
- lang: eng
text: This paper describes a new system for "Finding Satellite Tracks” in astronomical
images based on the modern geometric approach. There is an increasing need of
using methods with solid mathematical and statistical foundation in astronomical
image processing. Where the computational methods are serving in all disciplines
of science, they are becoming popular in the field of astronomy as well. Currently
different computational systems are required to be numerically optimized before
to get applied on astronomical images. So at present there is no single system
which solves the problems of astronomers using computational methods based on
modern approaches. The system "Finding Satellite Tracks” is based on geometric
matching method "Recognition by Adaptive Subdivision of Transformation Space
(RAST)".
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Haider
full_name: Ali, Haider
last_name: Ali
- first_name: Christoph
full_name: Lampert, Christoph
id: 40C20FD2-F248-11E8-B48F-1D18A9856A87
last_name: Lampert
orcid: 0000-0001-8622-7887
- first_name: Thomas
full_name: Breuel, Thomas
last_name: Breuel
citation:
ama: 'Ali H, Lampert C, Breuel T. Satellite tracks removal in astronomical images.
In: Proceedings of the 11th Iberoamerican Conference on Progress in Pattern
Recognition, Image Analysis and Applications. Vol 4225. Springer Nature; 2006:892-901.
doi:10.1007/11892755_92'
apa: 'Ali, H., Lampert, C., & Breuel, T. (2006). Satellite tracks removal in
astronomical images. In Proceedings of the 11th Iberoamerican conference on
Progress in Pattern Recognition, Image Analysis and Applications (Vol. 4225,
pp. 892–901). Cancún, Mexico: Springer Nature. https://doi.org/10.1007/11892755_92'
chicago: Ali, Haider, Christoph Lampert, and Thomas Breuel. “Satellite Tracks Removal
in Astronomical Images.” In Proceedings of the 11th Iberoamerican Conference
on Progress in Pattern Recognition, Image Analysis and Applications, 4225:892–901.
Springer Nature, 2006. https://doi.org/10.1007/11892755_92.
ieee: H. Ali, C. Lampert, and T. Breuel, “Satellite tracks removal in astronomical
images,” in Proceedings of the 11th Iberoamerican conference on Progress in
Pattern Recognition, Image Analysis and Applications, Cancún, Mexico, 2006,
vol. 4225, pp. 892–901.
ista: 'Ali H, Lampert C, Breuel T. 2006. Satellite tracks removal in astronomical
images. Proceedings of the 11th Iberoamerican conference on Progress in Pattern
Recognition, Image Analysis and Applications. CIARP: Iberoamerican Congress in
Pattern Recognition, LNCS, vol. 4225, 892–901.'
mla: Ali, Haider, et al. “Satellite Tracks Removal in Astronomical Images.” Proceedings
of the 11th Iberoamerican Conference on Progress in Pattern Recognition, Image
Analysis and Applications, vol. 4225, Springer Nature, 2006, pp. 892–901,
doi:10.1007/11892755_92.
short: H. Ali, C. Lampert, T. Breuel, in:, Proceedings of the 11th Iberoamerican
Conference on Progress in Pattern Recognition, Image Analysis and Applications,
Springer Nature, 2006, pp. 892–901.
conference:
end_date: 2006-11-17
location: Cancún, Mexico
name: 'CIARP: Iberoamerican Congress in Pattern Recognition'
start_date: 2006-11-14
date_created: 2018-12-11T12:04:35Z
date_published: 2006-10-31T00:00:00Z
date_updated: 2026-08-27T13:27:42Z
day: '31'
doi: 10.1007/11892755_92
extern: '1'
fulldoi: https://doi.org/10.1007/11892755_92
intvolume: ' 4225'
language:
- iso: eng
main_file_link:
- url: http://pub.ist.ac.at/~chl/papers/ali-ciarp2006.pdf
month: '10'
oa_version: None
page: 892 - 901
publication: Proceedings of the 11th Iberoamerican conference on Progress in Pattern
Recognition, Image Analysis and Applications
publication_identifier:
eisbn:
- '9783540465577'
eissn:
- 1611-3349
isbn:
- '9783540465560'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
publist_id: '2700'
status: public
title: Satellite tracks removal in astronomical images
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 4225
year: '2006'
...