---
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'
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_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'
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: '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'
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_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'
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_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'
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: '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'
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: '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'
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'
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'
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'
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: '18319'
abstract:
- lang: eng
text: "The problem of isometry-invariant representation and comparison of surfaces
is of cardinal importance in pattern recognition applications dealing with deformable
objects. Particularly, in three-dimensional face recognition treating facial expressions
as isometries of the facial surface allows to perform robust recognition insensitive
to expressions.\r\nIsometry-invariant representation of surfaces can be constructed
by isometrically embedding them into some convenient space, and carrying out the
comparison in that space. Presented here is a discussion on isometric embedding
into S3, which appears to be superior over the previously used Euclidean space
in sense of the representation accuracy."
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. Isometric embedding of facial surfaces
into S3. In: 5th International Conference on Scale-Space Theories in Computer
Vision. Vol 3459. Springer Berlin Heidelberg; 2005:622-631. doi:10.1007/11408031_53'
apa: 'Bronstein, A. M., Bronstein, M. M., & Kimmel, R. (2005). Isometric embedding
of facial surfaces into S3. In 5th International Conference on Scale-Space
Theories in Computer Vision (Vol. 3459, pp. 622–631). Hofgeismar, Germany:
Springer Berlin Heidelberg. https://doi.org/10.1007/11408031_53'
chicago: Bronstein, Alex M., Michael M. Bronstein, and Ron Kimmel. “Isometric Embedding
of Facial Surfaces into S3.” In 5th International Conference on Scale-Space
Theories in Computer Vision, 3459:622–31. Springer Berlin Heidelberg, 2005.
https://doi.org/10.1007/11408031_53.
ieee: A. M. Bronstein, M. M. Bronstein, and R. Kimmel, “Isometric embedding of facial
surfaces into S3,” in 5th International Conference on Scale-Space Theories
in Computer Vision, Hofgeismar, Germany, 2005, vol. 3459, pp. 622–631.
ista: 'Bronstein AM, Bronstein MM, Kimmel R. 2005. Isometric embedding of facial
surfaces into S3. 5th International Conference on Scale-Space Theories in Computer
Vision. Scale Space: Conference on Scale-Space Theories in Computer Vision, LNIP,
vol. 3459, 622–631.'
mla: Bronstein, Alex M., et al. “Isometric Embedding of Facial Surfaces into S3.”
5th International Conference on Scale-Space Theories in Computer Vision,
vol. 3459, Springer Berlin Heidelberg, 2005, pp. 622–31, doi:10.1007/11408031_53.
short: A.M. Bronstein, M.M. Bronstein, R. Kimmel, in:, 5th International Conference
on Scale-Space Theories in Computer Vision, Springer Berlin Heidelberg, 2005,
pp. 622–631.
conference:
end_date: 2005-04-09
location: Hofgeismar, Germany
name: 'Scale Space: Conference on Scale-Space Theories in Computer Vision'
start_date: 2005-04-07
date_created: 2024-10-15T11:12:06Z
date_published: 2005-03-31T00:00:00Z
date_updated: 2024-10-22T06:29:06Z
day: '31'
doi: 10.1007/11408031_53
extern: '1'
intvolume: ' 3459'
language:
- iso: eng
month: '03'
oa_version: None
page: 622-631
publication: 5th International Conference on Scale-Space Theories in Computer Vision
publication_identifier:
eisbn:
- '9783540320128'
eissn:
- 1611-3349
isbn:
- '9783540255475'
issn:
- 0302-9743
publication_status: published
publisher: Springer Berlin Heidelberg
quality_controlled: '1'
scopus_import: '1'
status: public
title: Isometric embedding of facial surfaces into S3
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 3459
year: '2005'
...
---
_id: '11800'
abstract:
- lang: eng
text: "Web search engines have emerged as one of the central applications on the
Internet. In fact, search has become one of the most important activities that
people engage in on the the Internet. Even beyond becoming the number one source
of information, a growing number of businesses are depending on web search engines
for customer acquisition.\r\n\r\nThe first generation of web search engines used
text-only retrieval techniques. Google revolutionized the field by deploying the
PageRank technology – an eigenvector-based analysis of the hyperlink structure
– to analyze the web in order to produce relevant results. Moving forward, our
goal is to achieve a better understanding of a page with a view towards producing
even more relevant results."
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Monika H
full_name: Henzinger, Monika H
id: 540c9bbd-f2de-11ec-812d-d04a5be85630
last_name: Henzinger
orcid: 0000-0002-5008-6530
citation:
ama: 'Henzinger M. The past, present, and future of web search engines. In: 31st
International Colloquium on Automata, Languages and Programming. Vol 3142.
Springer Nature; 2004:3. doi:10.1007/978-3-540-27836-8_2'
apa: 'Henzinger, M. (2004). The past, present, and future of web search engines.
In 31st International Colloquium on Automata, Languages and Programming
(Vol. 3142, p. 3). Turku, Finland: Springer Nature. https://doi.org/10.1007/978-3-540-27836-8_2'
chicago: Henzinger, Monika. “The Past, Present, and Future of Web Search Engines.”
In 31st International Colloquium on Automata, Languages and Programming,
3142:3. Springer Nature, 2004. https://doi.org/10.1007/978-3-540-27836-8_2.
ieee: M. Henzinger, “The past, present, and future of web search engines,” in 31st
International Colloquium on Automata, Languages and Programming, Turku, Finland,
2004, vol. 3142, p. 3.
ista: 'Henzinger M. 2004. The past, present, and future of web search engines. 31st
International Colloquium on Automata, Languages and Programming. ICALP: International
Colloquium on Automata, Languages, and Programming, LNCS, vol. 3142, 3.'
mla: Henzinger, Monika. “The Past, Present, and Future of Web Search Engines.” 31st
International Colloquium on Automata, Languages and Programming, vol. 3142,
Springer Nature, 2004, p. 3, doi:10.1007/978-3-540-27836-8_2.
short: M. Henzinger, in:, 31st International Colloquium on Automata, Languages and
Programming, Springer Nature, 2004, p. 3.
conference:
end_date: 2004-07-16
location: Turku, Finland
name: 'ICALP: International Colloquium on Automata, Languages, and Programming'
start_date: 2004-07-12
date_created: 2022-08-11T12:38:58Z
date_published: 2004-07-01T00:00:00Z
date_updated: 2024-11-06T08:14:51Z
day: '01'
doi: 10.1007/978-3-540-27836-8_2
extern: '1'
intvolume: ' 3142'
language:
- iso: eng
month: '07'
oa_version: None
page: '3'
publication: 31st International Colloquium on Automata, Languages and Programming
publication_identifier:
eissn:
- 1611-3349
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: The past, present, and future of web search engines
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 3142
year: '2004'
...
---
_id: '11801'
abstract:
- lang: eng
text: "Web search engines have emerged as one of the central applications on the
internet. In fact, search has become one of the most important activities that
people engage in on the Internet. Even beyond becoming the number one source of
information, a growing number of businesses are depending on web search engines
for customer acquisition. In this talk I will brief review the history of web
search engines: The first generation of web search engines used text-only retrieval
techniques. Google revolutionized the field by deploying the PageRank technology
– an eigenvector-based analysis of the hyperlink structure- to analyze the web
in order to produce relevant results. Moving forward, our goal is to achieve a
better understanding of a page with a view towards producing even more relevant
results.\r\n\r\nGoogle is powered by a large number of PCs. Using this infrastructure
and striving to be as efficient as possible poses challenging systems problems
but also various algorithmic challenges. I will discuss some of them in my talk."
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Monika H
full_name: Henzinger, Monika H
id: 540c9bbd-f2de-11ec-812d-d04a5be85630
last_name: Henzinger
orcid: 0000-0002-5008-6530
citation:
ama: 'Henzinger M. Algorithmic aspects of web search engines. In: 2th Annual
European Symposium on Algorithms. Vol 3221. Springer Nature; 2004:3. doi:10.1007/978-3-540-30140-0_2'
apa: 'Henzinger, M. (2004). Algorithmic aspects of web search engines. In 2th
Annual European Symposium on Algorithms (Vol. 3221, p. 3). Bergen, Norway:
Springer Nature. https://doi.org/10.1007/978-3-540-30140-0_2'
chicago: Henzinger, Monika. “Algorithmic Aspects of Web Search Engines.” In 2th
Annual European Symposium on Algorithms, 3221:3. Springer Nature, 2004. https://doi.org/10.1007/978-3-540-30140-0_2.
ieee: M. Henzinger, “Algorithmic aspects of web search engines,” in 2th Annual
European Symposium on Algorithms, Bergen, Norway, 2004, vol. 3221, p. 3.
ista: 'Henzinger M. 2004. Algorithmic aspects of web search engines. 2th Annual
European Symposium on Algorithms. ESA: European Symposium on Algorithms, LNCS,
vol. 3221, 3.'
mla: Henzinger, Monika. “Algorithmic Aspects of Web Search Engines.” 2th Annual
European Symposium on Algorithms, vol. 3221, Springer Nature, 2004, p. 3,
doi:10.1007/978-3-540-30140-0_2.
short: M. Henzinger, in:, 2th Annual European Symposium on Algorithms, Springer
Nature, 2004, p. 3.
conference:
end_date: 2004-09-17
location: Bergen, Norway
name: 'ESA: European Symposium on Algorithms'
start_date: 2004-09-14
date_created: 2022-08-11T13:18:05Z
date_published: 2004-09-01T00:00:00Z
date_updated: 2024-11-06T11:55:33Z
day: '01'
doi: 10.1007/978-3-540-30140-0_2
extern: '1'
intvolume: ' 3221'
language:
- iso: eng
month: '09'
oa_version: None
page: '3'
publication: 2th Annual European Symposium on Algorithms
publication_identifier:
eissn:
- 1611-3349
isbn:
- ' 3540230254'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Algorithmic aspects of web search engines
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 3221
year: '2004'
...
---
_id: '18331'
abstract:
- lang: eng
text: "Recently, a 3D face recognition approach based on geometric invariant signatures,
has been proposed. The key idea is a representation of the facial surface, invariant
to isometric deformations, such as those resulting from facial expressions. One
important stage in the construction of the geometric invariants involves in measuring
geodesic distances on triangulated surfaces, which is carried out by the fast
marching on triangulated domains algorithm.\r\n\r\nProposed here is a method that
uses only the metric tensor of the surface for geodesic distance computation.
That is, the explicit integration of the surface in 3D from its gradients is not
needed for the recognition task. It enables the use of simple and cost-efficient
3D acquisition techniques such as photometric stereo. Avoiding the explicit surface
reconstruction stage saves computational time and reduces numerical errors."
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: Alon
full_name: Spira, Alon
last_name: Spira
- first_name: Ron
full_name: Kimmel, Ron
last_name: Kimmel
citation:
ama: 'Bronstein AM, Bronstein MM, Spira A, Kimmel R. Face recognition from facial
surface metric. In: 8th European Conference on Computer Vision. Vol 3022.
Springer Nature; 2004:225–237. doi:10.1007/978-3-540-24671-8_18'
apa: 'Bronstein, A. M., Bronstein, M. M., Spira, A., & Kimmel, R. (2004). Face
recognition from facial surface metric. In 8th European Conference on Computer
Vision (Vol. 3022, pp. 225–237). Prageu, Czech Republic: Springer Nature.
https://doi.org/10.1007/978-3-540-24671-8_18'
chicago: Bronstein, Alex M., Michael M. Bronstein, Alon Spira, and Ron Kimmel. “Face
Recognition from Facial Surface Metric.” In 8th European Conference on Computer
Vision, 3022:225–237. Springer Nature, 2004. https://doi.org/10.1007/978-3-540-24671-8_18.
ieee: A. M. Bronstein, M. M. Bronstein, A. Spira, and R. Kimmel, “Face recognition
from facial surface metric,” in 8th European Conference on Computer Vision,
Prageu, Czech Republic, 2004, vol. 3022, pp. 225–237.
ista: 'Bronstein AM, Bronstein MM, Spira A, Kimmel R. 2004. Face recognition from
facial surface metric. 8th European Conference on Computer Vision. ECCV: European
Conference on Computer Vision, LNCS, vol. 3022, 225–237.'
mla: Bronstein, Alex M., et al. “Face Recognition from Facial Surface Metric.” 8th
European Conference on Computer Vision, vol. 3022, Springer Nature, 2004,
pp. 225–237, doi:10.1007/978-3-540-24671-8_18.
short: A.M. Bronstein, M.M. Bronstein, A. Spira, R. Kimmel, in:, 8th European Conference
on Computer Vision, Springer Nature, 2004, pp. 225–237.
conference:
end_date: 2004-05-14
location: Prageu, Czech Republic
name: 'ECCV: European Conference on Computer Vision'
start_date: 2004-05-11
date_created: 2024-10-15T11:20:54Z
date_published: 2004-01-01T00:00:00Z
date_updated: 2024-12-02T14:51:08Z
doi: 10.1007/978-3-540-24671-8_18
extern: '1'
intvolume: ' 3022'
language:
- iso: eng
month: '01'
oa_version: None
page: 225–237
publication: 8th European Conference on Computer Vision
publication_identifier:
eissn:
- 1611-3349
- '9783540246718'
isbn:
- '9783540219835'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Face recognition from facial surface metric
type: conference
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 3022
year: '2004'
...
---
_id: '18332'
abstract:
- lang: eng
text: Presented here is a generalization of the modified relative Newton method,
recently proposed in [1] for quasi-maximum likelihood blind source separation.
Special structure of the Hessian matrix allows to perform block-coordinate Newton
descent, which significantly reduces the algorithm computational complexity and
boosts its performance. Simulations based on artificial and real data show that
the separation quality using the proposed algorithm outperforms other accepted
blind source separation methods.
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: Michael
full_name: Zibulevsky, Michael
last_name: Zibulevsky
citation:
ama: 'Bronstein AM, Bronstein MM, Zibulevsky M. Blind source separation using the
block-coordinate relative Newton method. In: 5th International Conference on
Independent Component Analysis and Blind Signal Separation. Vol 3195. Springer
Nature; 2004:406–413. doi:10.1007/978-3-540-30110-3_52'
apa: 'Bronstein, A. M., Bronstein, M. M., & Zibulevsky, M. (2004). Blind source
separation using the block-coordinate relative Newton method. In 5th International
Conference on Independent Component Analysis and Blind Signal Separation (Vol.
3195, pp. 406–413). Granada, Spain: Springer Nature. https://doi.org/10.1007/978-3-540-30110-3_52'
chicago: Bronstein, Alex M., Michael M. Bronstein, and Michael Zibulevsky. “Blind
Source Separation Using the Block-Coordinate Relative Newton Method.” In 5th
International Conference on Independent Component Analysis and Blind Signal Separation,
3195:406–413. Springer Nature, 2004. https://doi.org/10.1007/978-3-540-30110-3_52.
ieee: A. M. Bronstein, M. M. Bronstein, and M. Zibulevsky, “Blind source separation
using the block-coordinate relative Newton method,” in 5th International Conference
on Independent Component Analysis and Blind Signal Separation, Granada, Spain,
2004, vol. 3195, pp. 406–413.
ista: 'Bronstein AM, Bronstein MM, Zibulevsky M. 2004. Blind source separation using
the block-coordinate relative Newton method. 5th International Conference on Independent
Component Analysis and Blind Signal Separation. ICA: Independent Component Analysis
and Blind Signal Separation, LNCS, vol. 3195, 406–413.'
mla: Bronstein, Alex M., et al. “Blind Source Separation Using the Block-Coordinate
Relative Newton Method.” 5th International Conference on Independent Component
Analysis and Blind Signal Separation, vol. 3195, Springer Nature, 2004, pp.
406–413, doi:10.1007/978-3-540-30110-3_52.
short: A.M. Bronstein, M.M. Bronstein, M. Zibulevsky, in:, 5th International Conference
on Independent Component Analysis and Blind Signal Separation, Springer Nature,
2004, pp. 406–413.
conference:
end_date: 2004-09-24
location: Granada, Spain
name: 'ICA: Independent Component Analysis and Blind Signal Separation'
start_date: 2004-09-22
date_created: 2024-10-15T11:20:54Z
date_published: 2004-10-27T00:00:00Z
date_updated: 2024-12-02T14:30:47Z
day: '27'
doi: 10.1007/978-3-540-30110-3_52
extern: '1'
intvolume: ' 3195'
language:
- iso: eng
month: '10'
oa_version: None
page: 406–413
publication: 5th International Conference on Independent Component Analysis and Blind
Signal Separation
publication_identifier:
eisbn:
- '9783540301103'
eissn:
- 1611-3349
isbn:
- '9783540230564'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Blind source separation using the block-coordinate relative Newton method
type: conference
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 3195
year: '2004'
...
---
_id: '18333'
abstract:
- lang: eng
text: The relative Newton algorithm, previously proposed for quasi maximum likelihood
blind source separation and blind deconvolution of one-dimensional signals is
generalized for blind deconvolution of images. Smooth approximation of the absolute
value is used in modelling the log probability density function, which is suitable
for sparse sources. We propose a method of sparsification, which allows blind
deconvolution of sources with arbitrary distribution, and show how to find optimal
sparsifying transformations by training.
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: Michael
full_name: Zibulevsky, Michael
last_name: Zibulevsky
- first_name: Yehoshua Y.
full_name: Zeevi, Yehoshua Y.
last_name: Zeevi
citation:
ama: 'Bronstein AM, Bronstein MM, Zibulevsky M, Zeevi YY. Optimal sparse representations
for blind deconvolution of images. In: 5th International Conference on Independent
Component Analysis and Blind Signal Separation. Vol 3195. Springer Nature;
2004:500-507. doi:10.1007/978-3-540-30110-3_64'
apa: 'Bronstein, A. M., Bronstein, M. M., Zibulevsky, M., & Zeevi, Y. Y. (2004).
Optimal sparse representations for blind deconvolution of images. In 5th International
Conference on Independent Component Analysis and Blind Signal Separation (Vol.
3195, pp. 500–507). Granada, Spain: Springer Nature. https://doi.org/10.1007/978-3-540-30110-3_64'
chicago: Bronstein, Alex M., Michael M. Bronstein, Michael Zibulevsky, and Yehoshua
Y. Zeevi. “Optimal Sparse Representations for Blind Deconvolution of Images.”
In 5th International Conference on Independent Component Analysis and Blind
Signal Separation, 3195:500–507. Springer Nature, 2004. https://doi.org/10.1007/978-3-540-30110-3_64.
ieee: A. M. Bronstein, M. M. Bronstein, M. Zibulevsky, and Y. Y. Zeevi, “Optimal
sparse representations for blind deconvolution of images,” in 5th International
Conference on Independent Component Analysis and Blind Signal Separation,
Granada, Spain, 2004, vol. 3195, pp. 500–507.
ista: 'Bronstein AM, Bronstein MM, Zibulevsky M, Zeevi YY. 2004. Optimal sparse
representations for blind deconvolution of images. 5th International Conference
on Independent Component Analysis and Blind Signal Separation. ICA: Independent
Component Analysis and Blind Signal Separation, LNCS, vol. 3195, 500–507.'
mla: Bronstein, Alex M., et al. “Optimal Sparse Representations for Blind Deconvolution
of Images.” 5th International Conference on Independent Component Analysis
and Blind Signal Separation, vol. 3195, Springer Nature, 2004, pp. 500–07,
doi:10.1007/978-3-540-30110-3_64.
short: A.M. Bronstein, M.M. Bronstein, M. Zibulevsky, Y.Y. Zeevi, in:, 5th International
Conference on Independent Component Analysis and Blind Signal Separation, Springer
Nature, 2004, pp. 500–507.
conference:
end_date: 2004-09-24
location: Granada, Spain
name: 'ICA: Independent Component Analysis and Blind Signal Separation'
start_date: 2004-09-22
date_created: 2024-10-15T11:20:54Z
date_published: 2004-10-27T00:00:00Z
date_updated: 2024-11-19T14:12:31Z
day: '27'
doi: 10.1007/978-3-540-30110-3_64
extern: '1'
intvolume: ' 3195'
language:
- iso: eng
month: '10'
oa_version: None
page: 500-507
publication: 5th International Conference on Independent Component Analysis and Blind
Signal Separation
publication_identifier:
eisbn:
- '9783540301103'
eissn:
- 1611-3349
isbn:
- '9783540230564'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Optimal sparse representations for blind deconvolution of images
type: conference
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 3195
year: '2004'
...
---
_id: '18334'
abstract:
- lang: eng
text: We propose a relative optimization framework for quasi maximum likelihood
blind deconvolution and the relative Newton method as its particular instance.
Special Hessian structure allows its fast approximate construction and inversion
with complexity comparable to that of gradient methods. The use of rational IIR
restoration kernels provides a richer family of filters than the traditionally
used FIR kernels. Smoothed absolute value and the smoothed deadzone functions
allow accurate and robust deconvolution of super- and sub-Gaussian sources, respectively.
Simulation results demonstrate the efficiency of the proposed methods.
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: Michael
full_name: Zibulevsky, Michael
last_name: Zibulevsky
citation:
ama: 'Bronstein AM, Bronstein MM, Zibulevsky M. Blind deconvolution using the relative
Newton method. In: 5th International Conference on Independent Component Analysis
and Blind Signal Separation. Vol 3195. Berlin, Heidelberg: Springer Nature;
2004:554–561. doi:10.1007/978-3-540-30110-3_71'
apa: 'Bronstein, A. M., Bronstein, M. M., & Zibulevsky, M. (2004). Blind deconvolution
using the relative Newton method. In 5th International Conference on Independent
Component Analysis and Blind Signal Separation (Vol. 3195, pp. 554–561). Berlin,
Heidelberg: Springer Nature. https://doi.org/10.1007/978-3-540-30110-3_71'
chicago: 'Bronstein, Alex M., Michael M. Bronstein, and Michael Zibulevsky. “Blind
Deconvolution Using the Relative Newton Method.” In 5th International Conference
on Independent Component Analysis and Blind Signal Separation, 3195:554–561.
Berlin, Heidelberg: Springer Nature, 2004. https://doi.org/10.1007/978-3-540-30110-3_71.'
ieee: A. M. Bronstein, M. M. Bronstein, and M. Zibulevsky, “Blind deconvolution
using the relative Newton method,” in 5th International Conference on Independent
Component Analysis and Blind Signal Separation, Granada, Spain, 2004, vol.
3195, pp. 554–561.
ista: 'Bronstein AM, Bronstein MM, Zibulevsky M. 2004. Blind deconvolution using
the relative Newton method. 5th International Conference on Independent Component
Analysis and Blind Signal Separation. ICA: Independent Component Analysis and
Blind Signal Separation, LNCS, vol. 3195, 554–561.'
mla: Bronstein, Alex M., et al. “Blind Deconvolution Using the Relative Newton Method.”
5th International Conference on Independent Component Analysis and Blind Signal
Separation, vol. 3195, Springer Nature, 2004, pp. 554–561, doi:10.1007/978-3-540-30110-3_71.
short: A.M. Bronstein, M.M. Bronstein, M. Zibulevsky, in:, 5th International Conference
on Independent Component Analysis and Blind Signal Separation, Springer Nature,
Berlin, Heidelberg, 2004, pp. 554–561.
conference:
end_date: 2004-09-24
location: Granada, Spain
name: 'ICA: Independent Component Analysis and Blind Signal Separation'
start_date: 2004-09-22
date_created: 2024-10-15T11:20:54Z
date_published: 2004-10-24T00:00:00Z
date_updated: 2024-12-02T14:15:23Z
day: '24'
doi: 10.1007/978-3-540-30110-3_71
extern: '1'
intvolume: ' 3195'
language:
- iso: eng
month: '10'
oa_version: None
page: 554–561
place: Berlin, Heidelberg
publication: 5th International Conference on Independent Component Analysis and Blind
Signal Separation
publication_identifier:
eissn:
- 1611-3349
isbn:
- '9783540230564'
- '9783540301103'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Blind deconvolution using the relative Newton method
type: conference
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 3195
year: '2004'
...
---
OA_type: closed access
_id: '18324'
abstract:
- lang: eng
text: We present a novel 3D face recognition approach based on geometric invariants
introduced by Elad and Kimmel. The key idea of the proposed algorithm is a representation
of the facial surface, invariant to isometric deformations, such as those resulting
from different expressions and postures of the face. The obtained geometric invariants
allow mapping 2D facial texture images into special images that incorporate the
3D geometry of the face. These signature images are then decomposed into their
principal components. The result is an efficient and accurate face recognition
algorithm that is robust to facial expressions. We demonstrate the results of
our method and compare it to existing 2D and 3D face recognition algorithms.
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. Expression-invariant 3D face recognition.
In: 4th International Conference on Audio- and Video-Based Biometric Person
Authentication. Vol 2688. Springer Nature; 2003:62-70. doi:10.1007/3-540-44887-x_8'
apa: 'Bronstein, A. M., Bronstein, M. M., & Kimmel, R. (2003). Expression-invariant
3D face recognition. In 4th International Conference on Audio- and Video-Based
Biometric Person Authentication (Vol. 2688, pp. 62–70). Guildford, United
Kingdom: Springer Nature. https://doi.org/10.1007/3-540-44887-x_8'
chicago: Bronstein, Alex M., Michael M. Bronstein, and Ron Kimmel. “Expression-Invariant
3D Face Recognition.” In 4th International Conference on Audio- and Video-Based
Biometric Person Authentication, 2688:62–70. Springer Nature, 2003. https://doi.org/10.1007/3-540-44887-x_8.
ieee: A. M. Bronstein, M. M. Bronstein, and R. Kimmel, “Expression-invariant 3D
face recognition,” in 4th International Conference on Audio- and Video-Based
Biometric Person Authentication, Guildford, United Kingdom, 2003, vol. 2688,
pp. 62–70.
ista: 'Bronstein AM, Bronstein MM, Kimmel R. 2003. Expression-invariant 3D face
recognition. 4th International Conference on Audio- and Video-Based Biometric
Person Authentication. AVBPA: Conference on Audio- and Video-Based Biometric Person
Authentication, LNCS, vol. 2688, 62–70.'
mla: Bronstein, Alex M., et al. “Expression-Invariant 3D Face Recognition.” 4th
International Conference on Audio- and Video-Based Biometric Person Authentication,
vol. 2688, Springer Nature, 2003, pp. 62–70, doi:10.1007/3-540-44887-x_8.
short: A.M. Bronstein, M.M. Bronstein, R. Kimmel, in:, 4th International Conference
on Audio- and Video-Based Biometric Person Authentication, Springer Nature, 2003,
pp. 62–70.
conference:
end_date: 2003-06-11
location: Guildford, United Kingdom
name: 'AVBPA: Conference on Audio- and Video-Based Biometric Person Authentication'
start_date: 2003-06-09
date_created: 2024-10-15T11:20:53Z
date_published: 2003-01-01T00:00:00Z
date_updated: 2024-10-22T07:20:09Z
day: '01'
doi: 10.1007/3-540-44887-x_8
extern: '1'
intvolume: ' 2688'
language:
- iso: eng
month: '01'
oa_version: None
page: 62-70
publication: 4th International Conference on Audio- and Video-Based Biometric Person
Authentication
publication_identifier:
eisbn:
- '9783540448877'
eissn:
- 1611-3349
isbn:
- '9783540403029'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Expression-invariant 3D face recognition
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 2688
year: '2003'
...
---
_id: '11802'
abstract:
- lang: eng
text: In this paper we survey algorithmic aspects of Web information retrieval.
As an example, we discuss ranking of search engine results using connectivity
analysis.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Monika H
full_name: Henzinger, Monika H
id: 540c9bbd-f2de-11ec-812d-d04a5be85630
last_name: Henzinger
orcid: 0000-0002-5008-6530
citation:
ama: 'Henzinger M. Web information retrieval - an algorithmic perspective. In: 8th
Annual European Symposium on Algorithms. Vol 1879. Springer Nature; 2000:1–8.
doi:10.1007/3-540-45253-2_1'
apa: 'Henzinger, M. (2000). Web information retrieval - an algorithmic perspective.
In 8th Annual European Symposium on Algorithms (Vol. 1879, pp. 1–8). Saarbrücken,
Germany: Springer Nature. https://doi.org/10.1007/3-540-45253-2_1'
chicago: Henzinger, Monika. “Web Information Retrieval - an Algorithmic Perspective.”
In 8th Annual European Symposium on Algorithms, 1879:1–8. Springer Nature,
2000. https://doi.org/10.1007/3-540-45253-2_1.
ieee: M. Henzinger, “Web information retrieval - an algorithmic perspective,” in
8th Annual European Symposium on Algorithms, Saarbrücken, Germany, 2000,
vol. 1879, pp. 1–8.
ista: 'Henzinger M. 2000. Web information retrieval - an algorithmic perspective.
8th Annual European Symposium on Algorithms. ESA: European Symposium on Algorithms,
LNCS, vol. 1879, 1–8.'
mla: Henzinger, Monika. “Web Information Retrieval - an Algorithmic Perspective.”
8th Annual European Symposium on Algorithms, vol. 1879, Springer Nature,
2000, pp. 1–8, doi:10.1007/3-540-45253-2_1.
short: M. Henzinger, in:, 8th Annual European Symposium on Algorithms, Springer
Nature, 2000, pp. 1–8.
conference:
end_date: 2000-09-08
location: Saarbrücken, Germany
name: 'ESA: European Symposium on Algorithms'
start_date: 2000-09-05
date_created: 2022-08-11T13:25:07Z
date_published: 2000-09-01T00:00:00Z
date_updated: 2024-11-06T11:55:46Z
day: '01'
doi: 10.1007/3-540-45253-2_1
extern: '1'
intvolume: ' 1879'
language:
- iso: eng
month: '09'
oa_version: None
page: 1–8
publication: 8th Annual European Symposium on Algorithms
publication_identifier:
eisbn:
- '9783540452539'
eissn:
- 1611-3349
isbn:
- '9783540410041'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Web information retrieval - an algorithmic perspective
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 1879
year: '2000'
...
---
_id: '11803'
abstract:
- lang: eng
text: We present the first fully dynamic algorithm for maintaining a minimum spanning
tree in time o(√n) per operation. To be precise, the algorithm uses O(n 1/3 log
n) amortized time per update operation. The algorithm is fairly simple and deterministic.
An immediate consequence is the first fully dynamic deterministic algorithm for
maintaining connectivity and, bipartiteness in amortized time O(n 1/3 log n) per
update, with O(1) worst case time per query.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Monika H
full_name: Henzinger, Monika H
id: 540c9bbd-f2de-11ec-812d-d04a5be85630
last_name: Henzinger
orcid: 0000-0002-5008-6530
- first_name: Valerie
full_name: King, Valerie
last_name: King
citation:
ama: 'Henzinger M, King V. Maintaining minimum spanning trees in dynamic graphs.
In: 24th International Colloquium on Automata, Languages and Programming.
Vol 1256. Springer Nature; 1997:594–604. doi:10.1007/3-540-63165-8_214'
apa: 'Henzinger, M., & King, V. (1997). Maintaining minimum spanning trees in
dynamic graphs. In 24th International Colloquium on Automata, Languages and
Programming (Vol. 1256, pp. 594–604). Bologna, Italy: Springer Nature. https://doi.org/10.1007/3-540-63165-8_214'
chicago: Henzinger, Monika, and Valerie King. “Maintaining Minimum Spanning Trees
in Dynamic Graphs.” In 24th International Colloquium on Automata, Languages
and Programming, 1256:594–604. Springer Nature, 1997. https://doi.org/10.1007/3-540-63165-8_214.
ieee: M. Henzinger and V. King, “Maintaining minimum spanning trees in dynamic graphs,”
in 24th International Colloquium on Automata, Languages and Programming,
Bologna, Italy, 1997, vol. 1256, pp. 594–604.
ista: 'Henzinger M, King V. 1997. Maintaining minimum spanning trees in dynamic
graphs. 24th International Colloquium on Automata, Languages and Programming.
ICALP: International Colloquium on Automata, Languages, and Programming, LNCS,
vol. 1256, 594–604.'
mla: Henzinger, Monika, and Valerie King. “Maintaining Minimum Spanning Trees in
Dynamic Graphs.” 24th International Colloquium on Automata, Languages and Programming,
vol. 1256, Springer Nature, 1997, pp. 594–604, doi:10.1007/3-540-63165-8_214.
short: M. Henzinger, V. King, in:, 24th International Colloquium on Automata, Languages
and Programming, Springer Nature, 1997, pp. 594–604.
conference:
end_date: 1997-07-11
location: Bologna, Italy
name: 'ICALP: International Colloquium on Automata, Languages, and Programming'
start_date: 1997-07-07
date_created: 2022-08-11T13:35:06Z
date_published: 1997-07-01T00:00:00Z
date_updated: 2024-11-06T12:13:35Z
day: '01'
doi: 10.1007/3-540-63165-8_214
extern: '1'
intvolume: ' 1256'
language:
- iso: eng
month: '07'
oa_version: None
page: 594–604
publication: 24th International Colloquium on Automata, Languages and Programming
publication_identifier:
eisbn:
- '9783540691945'
eissn:
- 1611-3349
isbn:
- '9783540631651'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Maintaining minimum spanning trees in dynamic graphs
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 1256
year: '1997'
...