---
_id: '3832'
abstract:
- lang: eng
text: A recent paper by von Engelhardt et al. identifies a novel auxiliary subunit
of native AMPARs, termedCKAMP44. Unlike other auxiliary subunits, CKAMP44 accelerates
desensitization and prolongs recovery from desensitization. CKAMP44 is highly
expressed in hippocampal dentate gyrus granule cells and decreases the paired-pulse
ratio at perforant path input synapses. Thus, both principal and auxiliary AMPAR
subunits control the time course of signaling at glutamatergic synapses.
article_processing_charge: No
author:
- first_name: José
full_name: Guzmán, José
id: 30CC5506-F248-11E8-B48F-1D18A9856A87
last_name: Guzmán
- first_name: Peter M
full_name: Jonas, Peter M
id: 353C1B58-F248-11E8-B48F-1D18A9856A87
last_name: Jonas
orcid: 0000-0001-5001-4804
citation:
ama: 'Guzmán J, Jonas PM. Beyond TARPs: The growing list of auxiliary AMPAR subunits.
Neuron. 2010;66(1):8-10. doi:10.1016/j.neuron.2010.04.003'
apa: 'Guzmán, J., & Jonas, P. M. (2010). Beyond TARPs: The growing list of auxiliary
AMPAR subunits. Neuron. Elsevier. https://doi.org/10.1016/j.neuron.2010.04.003'
chicago: 'Guzmán, José, and Peter M Jonas. “Beyond TARPs: The Growing List of Auxiliary
AMPAR Subunits.” Neuron. Elsevier, 2010. https://doi.org/10.1016/j.neuron.2010.04.003.'
ieee: 'J. Guzmán and P. M. Jonas, “Beyond TARPs: The growing list of auxiliary AMPAR
subunits,” Neuron, vol. 66, no. 1. Elsevier, pp. 8–10, 2010.'
ista: 'Guzmán J, Jonas PM. 2010. Beyond TARPs: The growing list of auxiliary AMPAR
subunits. Neuron. 66(1), 8–10.'
mla: 'Guzmán, José, and Peter M. Jonas. “Beyond TARPs: The Growing List of Auxiliary
AMPAR Subunits.” Neuron, vol. 66, no. 1, Elsevier, 2010, pp. 8–10, doi:10.1016/j.neuron.2010.04.003.'
short: J. Guzmán, P.M. Jonas, Neuron 66 (2010) 8–10.
date_created: 2018-12-11T12:05:25Z
date_published: 2010-04-15T00:00:00Z
date_updated: 2021-01-12T07:52:31Z
day: '15'
department:
- _id: PeJo
doi: 10.1016/j.neuron.2010.04.003
external_id:
pmid:
- '20399724'
intvolume: ' 66'
issue: '1'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://www.ncbi.nlm.nih.gov/pubmed/20399724
month: '04'
oa: 1
oa_version: Published Version
page: 8 - 10
pmid: 1
publication: Neuron
publication_status: published
publisher: Elsevier
publist_id: '2377'
quality_controlled: '1'
scopus_import: 1
status: public
title: 'Beyond TARPs: The growing list of auxiliary AMPAR subunits'
type: journal_article
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 66
year: '2010'
...
---
_id: '3833'
article_processing_charge: No
author:
- first_name: Peter M
full_name: Jonas, Peter M
id: 353C1B58-F248-11E8-B48F-1D18A9856A87
last_name: Jonas
orcid: 0000-0001-5001-4804
- first_name: Stefan
full_name: Hefft, Stefan
last_name: Hefft
citation:
ama: 'Jonas PM, Hefft S. GABA release at terminals of CCK-interneurons: synchrony,
asynchrony and modulation by cannabinoid receptors (commentary on Ali &
Todorova). The European Journal of Neuroscience. 2010;31(7):1194-1195.
doi:10.1111/j.1460-9568.2010.07189.x'
apa: 'Jonas, P. M., & Hefft, S. (2010). GABA release at terminals of CCK-interneurons:
synchrony, asynchrony and modulation by cannabinoid receptors (commentary on Ali
& Todorova). The European Journal of Neuroscience. Wiley-Blackwell.
https://doi.org/10.1111/j.1460-9568.2010.07189.x'
chicago: 'Jonas, Peter M, and Stefan Hefft. “GABA Release at Terminals of CCK-Interneurons:
Synchrony, Asynchrony and Modulation by Cannabinoid Receptors (Commentary on Ali
& Todorova).” The European Journal of Neuroscience. Wiley-Blackwell,
2010. https://doi.org/10.1111/j.1460-9568.2010.07189.x.'
ieee: 'P. M. Jonas and S. Hefft, “GABA release at terminals of CCK-interneurons:
synchrony, asynchrony and modulation by cannabinoid receptors (commentary on Ali
& Todorova),” The European Journal of Neuroscience, vol. 31, no.
7. Wiley-Blackwell, pp. 1194–1195, 2010.'
ista: 'Jonas PM, Hefft S. 2010. GABA release at terminals of CCK-interneurons: synchrony,
asynchrony and modulation by cannabinoid receptors (commentary on Ali &
Todorova). The European Journal of Neuroscience. 31(7), 1194–1195.'
mla: 'Jonas, Peter M., and Stefan Hefft. “GABA Release at Terminals of CCK-Interneurons:
Synchrony, Asynchrony and Modulation by Cannabinoid Receptors (Commentary on Ali
& Todorova).” The European Journal of Neuroscience, vol. 31, no.
7, Wiley-Blackwell, 2010, pp. 1194–95, doi:10.1111/j.1460-9568.2010.07189.x.'
short: P.M. Jonas, S. Hefft, The European Journal of Neuroscience 31 (2010) 1194–1195.
date_created: 2018-12-11T12:05:25Z
date_published: 2010-03-19T00:00:00Z
date_updated: 2021-01-12T07:52:31Z
day: '19'
department:
- _id: PeJo
doi: 10.1111/j.1460-9568.2010.07189.x
intvolume: ' 31'
issue: '7'
language:
- iso: eng
month: '03'
oa_version: None
page: 1194 - 1195
publication: The European Journal of Neuroscience
publication_status: published
publisher: Wiley-Blackwell
publist_id: '2378'
quality_controlled: '1'
scopus_import: 1
status: public
title: 'GABA release at terminals of CCK-interneurons: synchrony, asynchrony and modulation
by cannabinoid receptors (commentary on Ali & Todorova)'
type: journal_article
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 31
year: '2010'
...
---
_id: '3834'
abstract:
- lang: eng
text: "Background\r\n\r\nThe chemical master equation (CME) is a system of ordinary
differential equations that describes the evolution of a network of chemical reactions
as a stochastic process. Its solution yields the probability density vector of
the system at each point in time. Solving the CME numerically is in many cases
computationally expensive or even infeasible as the number of reachable states
can be very large or infinite. We introduce the sliding window method, which computes
an approximate solution of the CME by performing a sequence of local analysis
steps. In each step, only a manageable subset of states is considered, representing
a "window" into the state space. In subsequent steps, the window follows
the direction in which the probability mass moves, until the time period of interest
has elapsed. We construct the window based on a deterministic approximation of
the future behavior of the system by estimating upper and lower bounds on the
populations of the chemical species.\r\nResults\r\n\r\nIn order to show the effectiveness
of our approach, we apply it to several examples previously described in the literature.
The experimental results show that the proposed method speeds up the analysis
considerably, compared to a global analysis, while still providing high accuracy.\r\n\r\n\r\nConclusions\r\n\r\nThe
sliding window method is a novel approach to address the performance problems
of numerical algorithms for the solution of the chemical master equation. The
method efficiently approximates the probability distributions at the time points
of interest for a variety of chemically reacting systems, including systems for
which no upper bound on the population sizes of the chemical species is known
a priori."
acknowledgement: This research has been partially funded by the Swiss National Science
Foundation under grant 205321-111840 and by the Cluster of Excellence on Multimodal
Computing and Interaction at Saarland University.
author:
- first_name: Verena
full_name: Wolf, Verena
last_name: Wolf
- first_name: Rushil
full_name: Goel, Rushil
last_name: Goel
- first_name: Maria
full_name: Mateescu, Maria
id: 3B43276C-F248-11E8-B48F-1D18A9856A87
last_name: Mateescu
- 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: Wolf V, Goel R, Mateescu M, Henzinger TA. Solving the chemical master equation
using sliding windows. BMC Systems Biology. 2010;4(42):1-19. doi:10.1186/1752-0509-4-42
apa: Wolf, V., Goel, R., Mateescu, M., & Henzinger, T. A. (2010). Solving the
chemical master equation using sliding windows. BMC Systems Biology. BioMed
Central. https://doi.org/10.1186/1752-0509-4-42
chicago: Wolf, Verena, Rushil Goel, Maria Mateescu, and Thomas A Henzinger. “Solving
the Chemical Master Equation Using Sliding Windows.” BMC Systems Biology.
BioMed Central, 2010. https://doi.org/10.1186/1752-0509-4-42.
ieee: V. Wolf, R. Goel, M. Mateescu, and T. A. Henzinger, “Solving the chemical
master equation using sliding windows,” BMC Systems Biology, vol. 4, no.
42. BioMed Central, pp. 1–19, 2010.
ista: Wolf V, Goel R, Mateescu M, Henzinger TA. 2010. Solving the chemical master
equation using sliding windows. BMC Systems Biology. 4(42), 1–19.
mla: Wolf, Verena, et al. “Solving the Chemical Master Equation Using Sliding Windows.”
BMC Systems Biology, vol. 4, no. 42, BioMed Central, 2010, pp. 1–19, doi:10.1186/1752-0509-4-42.
short: V. Wolf, R. Goel, M. Mateescu, T.A. Henzinger, BMC Systems Biology 4 (2010)
1–19.
date_created: 2018-12-11T12:05:25Z
date_published: 2010-04-08T00:00:00Z
date_updated: 2021-01-12T07:52:32Z
day: '08'
ddc:
- '005'
department:
- _id: ToHe
doi: 10.1186/1752-0509-4-42
file:
- access_level: open_access
checksum: 220239fae76f7b03c4d7f05d74ef426f
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:16:29Z
date_updated: 2020-07-14T12:46:16Z
file_id: '5217'
file_name: IST-2012-72-v1+1_Solving_the_chemical_master_equation_using_sliding_windows.pdf
file_size: 1919130
relation: main_file
file_date_updated: 2020-07-14T12:46:16Z
has_accepted_license: '1'
intvolume: ' 4'
issue: '42'
language:
- iso: eng
month: '04'
oa: 1
oa_version: Published Version
page: 1 - 19
publication: BMC Systems Biology
publication_status: published
publisher: BioMed Central
publist_id: '2374'
pubrep_id: '72'
quality_controlled: '1'
scopus_import: 1
status: public
title: Solving the chemical master equation using sliding windows
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 4
year: '2010'
...
---
_id: '3838'
abstract:
- lang: eng
text: We present a numerical approximation technique for the analysis of continuous-time
Markov chains that describe net- works of biochemical reactions and play an important
role in the stochastic modeling of biological systems. Our approach is based on
the construction of a stochastic hybrid model in which certain discrete random
variables of the original Markov chain are approximated by continuous deterministic
variables. We compute the solution of the stochastic hybrid model using a numerical
algorithm that discretizes time and in each step performs a mutual update of the
transient prob- ability distribution of the discrete stochastic variables and
the values of the continuous deterministic variables. We im- plemented the algorithm
and we demonstrate its usefulness and efficiency on several case studies from
systems biology.
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: Maria
full_name: Mateescu, Maria
last_name: Mateescu
- first_name: Linar
full_name: Mikeev, Linar
last_name: Mikeev
- first_name: Verena
full_name: Wolf, Verena
last_name: Wolf
citation:
ama: 'Henzinger TA, Mateescu M, Mikeev L, Wolf V. Hybrid numerical solution of the
chemical master equation. In: Springer; 2010:55-65. doi:10.1145/1839764.1839772'
apa: 'Henzinger, T. A., Mateescu, M., Mikeev, L., & Wolf, V. (2010). Hybrid
numerical solution of the chemical master equation (pp. 55–65). Presented at the
CMSB: Computational Methods in Systems Biology, Trento, Italy: Springer. https://doi.org/10.1145/1839764.1839772'
chicago: Henzinger, Thomas A, Maria Mateescu, Linar Mikeev, and Verena Wolf. “Hybrid
Numerical Solution of the Chemical Master Equation,” 55–65. Springer, 2010. https://doi.org/10.1145/1839764.1839772.
ieee: 'T. A. Henzinger, M. Mateescu, L. Mikeev, and V. Wolf, “Hybrid numerical solution
of the chemical master equation,” presented at the CMSB: Computational Methods
in Systems Biology, Trento, Italy, 2010, pp. 55–65.'
ista: 'Henzinger TA, Mateescu M, Mikeev L, Wolf V. 2010. Hybrid numerical solution
of the chemical master equation. CMSB: Computational Methods in Systems Biology,
55–65.'
mla: Henzinger, Thomas A., et al. Hybrid Numerical Solution of the Chemical Master
Equation. Springer, 2010, pp. 55–65, doi:10.1145/1839764.1839772.
short: T.A. Henzinger, M. Mateescu, L. Mikeev, V. Wolf, in:, Springer, 2010, pp.
55–65.
conference:
end_date: 2010-10-01
location: Trento, Italy
name: 'CMSB: Computational Methods in Systems Biology'
start_date: 2010-09-29
date_created: 2018-12-11T12:05:27Z
date_published: 2010-09-29T00:00:00Z
date_updated: 2021-01-12T07:52:33Z
day: '29'
ddc:
- '004'
department:
- _id: ToHe
doi: 10.1145/1839764.1839772
file:
- access_level: open_access
checksum: 81cb6f0babd97151b171d1ce86582831
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:15:55Z
date_updated: 2020-07-14T12:46:16Z
file_id: '5179'
file_name: IST-2012-68-v1+1_Hybrid_Numerical_Solution_of_the_Chemical_Master_Equation.pdf
file_size: 671790
relation: main_file
file_date_updated: 2020-07-14T12:46:16Z
has_accepted_license: '1'
language:
- iso: eng
month: '09'
oa: 1
oa_version: Submitted Version
page: 55 - 65
publication_status: published
publisher: Springer
publist_id: '2356'
pubrep_id: '68'
quality_controlled: '1'
scopus_import: 1
status: public
title: Hybrid numerical solution of the chemical master equation
type: conference
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
year: '2010'
...
---
_id: '3839'
abstract:
- lang: eng
text: We present a loop property generation method for loops iterating over multi-dimensional
arrays. When used on matrices, our method is able to infer their shapes (also
called types), such as upper-triangular, diagonal, etc. To gen- erate loop properties,
we first transform a nested loop iterating over a multi- dimensional array into
an equivalent collection of unnested loops. Then, we in- fer quantified loop invariants
for each unnested loop using a generalization of a recurrence-based invariant
generation technique. These loop invariants give us conditions on matrices from
which we can derive matrix types automatically us- ing theorem provers. Invariant
generation is implemented in the software package Aligator and types are derived
by theorem provers and SMT solvers, including Vampire and Z3. When run on the
Java matrix package JAMA, our tool was able to infer automatically all matrix
types describing the matrix shapes guaranteed by JAMA’s API.
acknowledgement: The research was supported by the Swiss NSF.
alternative_title:
- LNCS
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: Thibaud
full_name: Hottelier, Thibaud
last_name: Hottelier
- first_name: Laura
full_name: Kovács, Laura
last_name: Kovács
- first_name: Andrei
full_name: Voronkov, Andrei
last_name: Voronkov
citation:
ama: 'Henzinger TA, Hottelier T, Kovács L, Voronkov A. Invariant and type inference
for matrices. In: Vol 5944. Springer; 2010:163-179. doi:10.1007/978-3-642-11319-2_14'
apa: 'Henzinger, T. A., Hottelier, T., Kovács, L., & Voronkov, A. (2010). Invariant
and type inference for matrices (Vol. 5944, pp. 163–179). Presented at the VMCAI:
Verification, Model Checking and Abstract Interpretation, Madrid, Spain: Springer.
https://doi.org/10.1007/978-3-642-11319-2_14'
chicago: Henzinger, Thomas A, Thibaud Hottelier, Laura Kovács, and Andrei Voronkov.
“Invariant and Type Inference for Matrices,” 5944:163–79. Springer, 2010. https://doi.org/10.1007/978-3-642-11319-2_14.
ieee: 'T. A. Henzinger, T. Hottelier, L. Kovács, and A. Voronkov, “Invariant and
type inference for matrices,” presented at the VMCAI: Verification, Model Checking
and Abstract Interpretation, Madrid, Spain, 2010, vol. 5944, pp. 163–179.'
ista: 'Henzinger TA, Hottelier T, Kovács L, Voronkov A. 2010. Invariant and type
inference for matrices. VMCAI: Verification, Model Checking and Abstract Interpretation,
LNCS, vol. 5944, 163–179.'
mla: Henzinger, Thomas A., et al. Invariant and Type Inference for Matrices.
Vol. 5944, Springer, 2010, pp. 163–79, doi:10.1007/978-3-642-11319-2_14.
short: T.A. Henzinger, T. Hottelier, L. Kovács, A. Voronkov, in:, Springer, 2010,
pp. 163–179.
conference:
end_date: 2010-01-19
location: Madrid, Spain
name: 'VMCAI: Verification, Model Checking and Abstract Interpretation'
start_date: 2010-01-17
date_created: 2018-12-11T12:05:27Z
date_published: 2010-01-01T00:00:00Z
date_updated: 2021-01-12T07:52:33Z
day: '01'
ddc:
- '005'
department:
- _id: ToHe
doi: 10.1007/978-3-642-11319-2_14
file:
- access_level: open_access
checksum: da69b13a2d9a7a316c909e09c1090cef
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:13:09Z
date_updated: 2020-07-14T12:46:16Z
file_id: '4989'
file_name: IST-2012-69-v1+1_Invariant_and_type_inference_for_matrices.pdf
file_size: 251265
relation: main_file
file_date_updated: 2020-07-14T12:46:16Z
has_accepted_license: '1'
intvolume: ' 5944'
language:
- iso: eng
month: '01'
oa: 1
oa_version: Submitted Version
page: 163 - 179
publication_status: published
publisher: Springer
publist_id: '2357'
pubrep_id: '69'
quality_controlled: '1'
scopus_import: 1
status: public
title: Invariant and type inference for matrices
type: conference
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 5944
year: '2010'
...
---
_id: '3840'
abstract:
- lang: eng
text: 'Classical formalizations of systems and properties are boolean: given a system
and a property, the property is either true or false of the system. Correspondingly,
classical methods for system analysis determine the truth value of a property,
preferably giving a proof if the property is true, and a counterexample if the
property is false; classical methods for system synthesis construct a system for
which a property is true; classical methods for system transformation, composition,
and abstraction aim to preserve the truth of properties. The boolean view is prevalent
even if the system, the property, or both refer to numerical quantities, such
as the times or probabilities of events. For example, a timed automaton either
satisfies or violates a formula of a real-time logic; a stochastic process either
satisfies or violates a formula of a probabilistic logic. The classical black-and-white
view partitions the world into "correct" and "incorrect" systems, offering few
nuances. In reality, of several systems that satisfy a property in the boolean
sense, often some are more desirable than others, and of the many systems that
violate a property, usually some are less objectionable than others. For instance,
among the systems that satisfy the response property that every request be granted,
we may prefer systems that grant requests quickly (the quicker, the better), or
we may prefer systems that issue few unnecessary grants (the fewer, the better);
and among the systems that violate the response property, we may prefer systems
that serve many initial requests (the more, the better), or we may prefer systems
that serve many requests in the long run (the greater the fraction of served to
unserved requests, the better). Formally, while a boolean notion of correctness
is given by a preorder on systems and properties, a quantitative notion of correctness
is defined by a directed metric on systems and properties, where the distance
between a system and a property provides a measure of "fit" or "desirability."
There are many ways how such distances can be defined. In a linear-time framework,
one assigns numerical values to individual behaviors before assigning values to
systems and properties, which are sets of behaviors. For example, the value of
a single behavior may be a discounted value, which is largely determined by a
prefix of the behavior, e.g., by the number of requests that are granted before
the first request that is not granted; or a limit value, which is independent
of any finite prefix. A limit value may be an average, such as the average response
time over an infinite sequence of requests and grants, or a supremum, such as
the worst-case response time. Similarly, the value of a set of behaviors may be
an extremum or an average across the values of all behaviors in the set: in this
way one can measure the worst of all possible average-case response times, or
the average of all possible worst-case response times, etc. Accordingly, the distance
between two sets of behaviors may be defined as the worst or average difference
between the values of corresponding behaviors. In summary, we propagate replacing
boolean specifications for the correctness of systems with quantitative measures
for the desirability of systems. In quantitative analysis, the aim is to compute
the distance between a system and a property (or between two systems, or two properties);
in quantitative synthesis, the objective is to construct a system that has minimal
distance from a given property. Multiple quantitative measures can be prioritized
(e.g., combined lexicographically into a single measure) or studied along the
Pareto curve. Quantitative transformations, compositions, and abstractions of
systems are useful if they allow us to bound the induced change in distance from
a property. We present some initial results in some of these directions. We also
give some potential applications, which not only generalize tradiditional correctness
concerns in the functional, timed, and probabilistic domains, but also capture
such system measures as resource use, performance, cost, reliability, and robustness.'
acknowledgement: This talk surveys joint work with Roderick Bloem, Krishnendu Chatterjee,
Laurent Doyen, and Barbara Jobstmann.
author:
- 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: 'Henzinger TA. From boolean to quantitative notions of correctness. In: Vol
45. ACM; 2010:157-158. doi:10.1145/1706299.1706319'
apa: 'Henzinger, T. A. (2010). From boolean to quantitative notions of correctness
(Vol. 45, pp. 157–158). Presented at the POPL: Principles of Programming Languages,
Madrid, Spain: ACM. https://doi.org/10.1145/1706299.1706319'
chicago: Henzinger, Thomas A. “From Boolean to Quantitative Notions of Correctness,”
45:157–58. ACM, 2010. https://doi.org/10.1145/1706299.1706319.
ieee: 'T. A. Henzinger, “From boolean to quantitative notions of correctness,” presented
at the POPL: Principles of Programming Languages, Madrid, Spain, 2010, vol. 45,
no. 1, pp. 157–158.'
ista: 'Henzinger TA. 2010. From boolean to quantitative notions of correctness.
POPL: Principles of Programming Languages vol. 45, 157–158.'
mla: Henzinger, Thomas A. From Boolean to Quantitative Notions of Correctness.
Vol. 45, no. 1, ACM, 2010, pp. 157–58, doi:10.1145/1706299.1706319.
short: T.A. Henzinger, in:, ACM, 2010, pp. 157–158.
conference:
end_date: 2010-01-23
location: Madrid, Spain
name: 'POPL: Principles of Programming Languages'
start_date: 2010-01-17
date_created: 2018-12-11T12:05:27Z
date_published: 2010-01-17T00:00:00Z
date_updated: 2021-01-12T07:52:34Z
day: '17'
department:
- _id: ToHe
doi: 10.1145/1706299.1706319
intvolume: ' 45'
issue: '1'
language:
- iso: eng
month: '01'
oa_version: None
page: 157 - 158
publication_status: published
publisher: ACM
publist_id: '2354'
quality_controlled: '1'
scopus_import: 1
status: public
title: From boolean to quantitative notions of correctness
type: conference
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
volume: 45
year: '2010'
...
---
_id: '3842'
abstract:
- lang: eng
text: Within systems biology there is an increasing interest in the stochastic behavior
of biochemical reaction networks. An appropriate stochastic description is provided
by the chemical master equation, which represents a continuous-time Markov chain
(CTMC). The uniformization technique is an efficient method to compute probability
distributions of a CTMC if the number of states is manageable. However, the size
of a CTMC that represents a biochemical reaction network is usually far beyond
what is feasible. In this paper we present an on-the-fly variant of uniformization,
where we improve the original algorithm at the cost of a small approximation error.
By means of several examples, we show that our approach is particularly well-suited
for biochemical reaction networks.
author:
- first_name: Frédéric
full_name: Didier, Frédéric
last_name: Didier
- 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: Maria
full_name: Mateescu, Maria
last_name: Mateescu
- first_name: Verena
full_name: Wolf, Verena
last_name: Wolf
citation:
ama: Didier F, Henzinger TA, Mateescu M, Wolf V. Fast adaptive uniformization of
the chemical master equation. IET Systems Biology. 2010;4(6):441-452. doi:10.1049/iet-syb.2010.0005
apa: Didier, F., Henzinger, T. A., Mateescu, M., & Wolf, V. (2010). Fast adaptive
uniformization of the chemical master equation. IET Systems Biology. Institution
of Engineering and Technology. https://doi.org/10.1049/iet-syb.2010.0005
chicago: Didier, Frédéric, Thomas A Henzinger, Maria Mateescu, and Verena Wolf.
“Fast Adaptive Uniformization of the Chemical Master Equation.” IET Systems
Biology. Institution of Engineering and Technology, 2010. https://doi.org/10.1049/iet-syb.2010.0005.
ieee: F. Didier, T. A. Henzinger, M. Mateescu, and V. Wolf, “Fast adaptive uniformization
of the chemical master equation,” IET Systems Biology, vol. 4, no. 6. Institution
of Engineering and Technology, pp. 441–452, 2010.
ista: Didier F, Henzinger TA, Mateescu M, Wolf V. 2010. Fast adaptive uniformization
of the chemical master equation. IET Systems Biology. 4(6), 441–452.
mla: Didier, Frédéric, et al. “Fast Adaptive Uniformization of the Chemical Master
Equation.” IET Systems Biology, vol. 4, no. 6, Institution of Engineering
and Technology, 2010, pp. 441–52, doi:10.1049/iet-syb.2010.0005.
short: F. Didier, T.A. Henzinger, M. Mateescu, V. Wolf, IET Systems Biology 4 (2010)
441–452.
date_created: 2018-12-11T12:05:28Z
date_published: 2010-11-15T00:00:00Z
date_updated: 2023-02-23T11:45:08Z
day: '15'
ddc:
- '570'
department:
- _id: ToHe
doi: 10.1049/iet-syb.2010.0005
file:
- access_level: open_access
checksum: 9a3bde48f43203991a0b3c6a277c2f5b
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:17:02Z
date_updated: 2020-07-14T12:46:16Z
file_id: '5254'
file_name: IST-2012-66-v1+1_Fast_adaptive_uniformization_of_the_chemical_master_equation.pdf
file_size: 222890
relation: main_file
file_date_updated: 2020-07-14T12:46:16Z
has_accepted_license: '1'
intvolume: ' 4'
issue: '6'
language:
- iso: eng
month: '11'
oa: 1
oa_version: Submitted Version
page: 441 - 452
publication: IET Systems Biology
publication_status: published
publisher: Institution of Engineering and Technology
publist_id: '2349'
pubrep_id: '66'
quality_controlled: '1'
related_material:
record:
- id: '3843'
relation: earlier_version
status: public
scopus_import: 1
status: public
title: Fast adaptive uniformization of the chemical master equation
type: journal_article
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
volume: 4
year: '2010'
...
---
_id: '3845'
abstract:
- lang: eng
text: This paper presents Aligators, a tool for the generation of universally quantified
array invariants. Aligators leverages recurrence solving and algebraic techniques
to carry out inductive reasoning over array content. The Aligators’ loop extraction
module allows treatment of multi-path loops by exploiting their commutativity
and serializability properties. Our experience in applying Aligators on a collection
of loops from open source software projects indicates the applicability of recurrence
and algebraic solving techniques for reasoning about arrays.
alternative_title:
- LNCS
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: Thibaud
full_name: Hottelier, Thibaud
last_name: Hottelier
- first_name: Laura
full_name: Kovács, Laura
last_name: Kovács
- first_name: Andrey
full_name: Rybalchenko, Andrey
last_name: Rybalchenko
citation:
ama: 'Henzinger TA, Hottelier T, Kovács L, Rybalchenko A. Aligators for arrays.
In: Vol 6397. Springer; 2010:348-356. doi:10.1007/978-3-642-16242-8_25'
apa: 'Henzinger, T. A., Hottelier, T., Kovács, L., & Rybalchenko, A. (2010).
Aligators for arrays (Vol. 6397, pp. 348–356). Presented at the LPAR: Logic for
Programming, Artificial Intelligence, and Reasoning, Yogyakarta, Indonesia: Springer.
https://doi.org/10.1007/978-3-642-16242-8_25'
chicago: Henzinger, Thomas A, Thibaud Hottelier, Laura Kovács, and Andrey Rybalchenko.
“Aligators for Arrays,” 6397:348–56. Springer, 2010. https://doi.org/10.1007/978-3-642-16242-8_25.
ieee: 'T. A. Henzinger, T. Hottelier, L. Kovács, and A. Rybalchenko, “Aligators
for arrays,” presented at the LPAR: Logic for Programming, Artificial Intelligence,
and Reasoning, Yogyakarta, Indonesia, 2010, vol. 6397, pp. 348–356.'
ista: 'Henzinger TA, Hottelier T, Kovács L, Rybalchenko A. 2010. Aligators for arrays.
LPAR: Logic for Programming, Artificial Intelligence, and Reasoning, LNCS, vol.
6397, 348–356.'
mla: Henzinger, Thomas A., et al. Aligators for Arrays. Vol. 6397, Springer,
2010, pp. 348–56, doi:10.1007/978-3-642-16242-8_25.
short: T.A. Henzinger, T. Hottelier, L. Kovács, A. Rybalchenko, in:, Springer, 2010,
pp. 348–356.
conference:
end_date: 2010-10-15
location: Yogyakarta, Indonesia
name: 'LPAR: Logic for Programming, Artificial Intelligence, and Reasoning'
start_date: 2010-10-10
date_created: 2018-12-11T12:05:29Z
date_published: 2010-10-01T00:00:00Z
date_updated: 2021-01-12T07:52:37Z
day: '01'
ddc:
- '005'
department:
- _id: ToHe
doi: 10.1007/978-3-642-16242-8_25
file:
- access_level: open_access
checksum: 913af269da6710f2174f470b48ab7a82
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:10:05Z
date_updated: 2020-07-14T12:46:17Z
file_id: '4790'
file_name: IST-2012-64-v1+1_Aligators_for_arrays.pdf
file_size: 186143
relation: main_file
file_date_updated: 2020-07-14T12:46:17Z
has_accepted_license: '1'
intvolume: ' 6397'
language:
- iso: eng
month: '10'
oa: 1
oa_version: Submitted Version
page: 348 - 356
publication_status: published
publisher: Springer
publist_id: '2342'
pubrep_id: '64'
quality_controlled: '1'
scopus_import: 1
status: public
title: Aligators for arrays
type: conference
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
volume: 6397
year: '2010'
...
---
_id: '3847'
abstract:
- lang: eng
text: The importance of stochasticity within biological systems has been shown repeatedly
during the last years and has raised the need for efficient stochastic tools.
We present SABRE, a tool for stochastic analysis of biochemical reaction networks.
SABRE implements fast adaptive uniformization (FAU), a direct numerical approximation
algorithm for computing transient solutions of biochemical reaction networks.
Biochemical reactions networks represent biological systems studied at a molecular
level and these reactions can be modeled as transitions of a Markov chain. SABRE
accepts as input the formalism of guarded commands, which it interprets either
as continuous-time or as discrete-time Markov chains. Besides operating in a stochastic
mode, SABRE may also perform a deterministic analysis by directly computing a
mean-field approximation of the system under study. We illustrate the different
functionalities of SABRE by means of biological case studies.
author:
- first_name: Frédéric
full_name: Didier, Frédéric
last_name: Didier
- 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: Maria
full_name: Mateescu, Maria
last_name: Mateescu
- first_name: Verena
full_name: Wolf, Verena
last_name: Wolf
citation:
ama: 'Didier F, Henzinger TA, Mateescu M, Wolf V. SABRE: A tool for the stochastic
analysis of biochemical reaction networks. In: IEEE; 2010:193-194. doi:10.1109/QEST.2010.33'
apa: 'Didier, F., Henzinger, T. A., Mateescu, M., & Wolf, V. (2010). SABRE:
A tool for the stochastic analysis of biochemical reaction networks (pp. 193–194).
Presented at the QEST: Quantitative Evaluation of Systems, Williamsburg, USA:
IEEE. https://doi.org/10.1109/QEST.2010.33'
chicago: 'Didier, Frédéric, Thomas A Henzinger, Maria Mateescu, and Verena Wolf.
“SABRE: A Tool for the Stochastic Analysis of Biochemical Reaction Networks,”
193–94. IEEE, 2010. https://doi.org/10.1109/QEST.2010.33.'
ieee: 'F. Didier, T. A. Henzinger, M. Mateescu, and V. Wolf, “SABRE: A tool for
the stochastic analysis of biochemical reaction networks,” presented at the QEST:
Quantitative Evaluation of Systems, Williamsburg, USA, 2010, pp. 193–194.'
ista: 'Didier F, Henzinger TA, Mateescu M, Wolf V. 2010. SABRE: A tool for the stochastic
analysis of biochemical reaction networks. QEST: Quantitative Evaluation of Systems,
193–194.'
mla: 'Didier, Frédéric, et al. SABRE: A Tool for the Stochastic Analysis of Biochemical
Reaction Networks. IEEE, 2010, pp. 193–94, doi:10.1109/QEST.2010.33.'
short: F. Didier, T.A. Henzinger, M. Mateescu, V. Wolf, in:, IEEE, 2010, pp. 193–194.
conference:
end_date: 2010-09-18
location: Williamsburg, USA
name: 'QEST: Quantitative Evaluation of Systems'
start_date: 2010-09-15
date_created: 2018-12-11T12:05:29Z
date_published: 2010-10-14T00:00:00Z
date_updated: 2021-01-12T07:52:37Z
day: '14'
ddc:
- '004'
department:
- _id: ToHe
- _id: CaGu
doi: 10.1109/QEST.2010.33
file:
- access_level: open_access
checksum: 38707b149d2174f01be406e794ffa849
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:09:03Z
date_updated: 2020-07-14T12:46:17Z
file_id: '4726'
file_name: IST-2012-63-v1+1_SABRE-A_tool_for_the_stochastic_analysis_of_biochemical_reaction_networks.pdf
file_size: 433824
relation: main_file
file_date_updated: 2020-07-14T12:46:17Z
has_accepted_license: '1'
language:
- iso: eng
month: '10'
oa: 1
oa_version: Submitted Version
page: 193 - 194
publication_status: published
publisher: IEEE
publist_id: '2339'
pubrep_id: '63'
quality_controlled: '1'
scopus_import: 1
status: public
title: 'SABRE: A tool for the stochastic analysis of biochemical reaction networks'
type: conference
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
year: '2010'
...
---
_id: '3848'
abstract:
- lang: eng
text: We define the robustness of a level set homology class of a function f:XR
as the magnitude of a perturbation necessary to kill the class. Casting this notion
into a group theoretic framework, we compute the robustness for each class, using
a connection to extended persistent homology. The special case X=R3 has ramifications
in medical imaging and scientific visualization.
alternative_title:
- LNCS
author:
- first_name: Paul
full_name: Bendich, Paul
id: 43F6EC54-F248-11E8-B48F-1D18A9856A87
last_name: Bendich
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
- first_name: Dmitriy
full_name: Morozov, Dmitriy
last_name: Morozov
- first_name: Amit
full_name: Patel, Amit
id: 34A254A0-F248-11E8-B48F-1D18A9856A87
last_name: Patel
citation:
ama: 'Bendich P, Edelsbrunner H, Morozov D, Patel A. The robustness of level sets.
In: Vol 6346. Springer; 2010:1-10. doi:10.1007/978-3-642-15775-2_1'
apa: 'Bendich, P., Edelsbrunner, H., Morozov, D., & Patel, A. (2010). The robustness
of level sets (Vol. 6346, pp. 1–10). Presented at the ESA: European Symposium
on Algorithms, Liverpool, UK: Springer. https://doi.org/10.1007/978-3-642-15775-2_1'
chicago: Bendich, Paul, Herbert Edelsbrunner, Dmitriy Morozov, and Amit Patel. “The
Robustness of Level Sets,” 6346:1–10. Springer, 2010. https://doi.org/10.1007/978-3-642-15775-2_1.
ieee: 'P. Bendich, H. Edelsbrunner, D. Morozov, and A. Patel, “The robustness of
level sets,” presented at the ESA: European Symposium on Algorithms, Liverpool,
UK, 2010, vol. 6346, pp. 1–10.'
ista: 'Bendich P, Edelsbrunner H, Morozov D, Patel A. 2010. The robustness of level
sets. ESA: European Symposium on Algorithms, LNCS, vol. 6346, 1–10.'
mla: Bendich, Paul, et al. The Robustness of Level Sets. Vol. 6346, Springer,
2010, pp. 1–10, doi:10.1007/978-3-642-15775-2_1.
short: P. Bendich, H. Edelsbrunner, D. Morozov, A. Patel, in:, Springer, 2010, pp.
1–10.
conference:
end_date: 2010-09-08
location: Liverpool, UK
name: 'ESA: European Symposium on Algorithms'
start_date: 2010-09-06
date_created: 2018-12-11T12:05:30Z
date_published: 2010-09-01T00:00:00Z
date_updated: 2021-01-12T07:52:38Z
day: '01'
department:
- _id: HeEd
doi: 10.1007/978-3-642-15775-2_1
intvolume: ' 6346'
language:
- iso: eng
month: '09'
oa_version: None
page: 1 - 10
publication_status: published
publisher: Springer
publist_id: '2336'
quality_controlled: '1'
scopus_import: 1
status: public
title: The robustness of level sets
type: conference
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
volume: 6346
year: '2010'
...
---
_id: '3849'
abstract:
- lang: eng
text: Using ideas from persistent homology, the robustness of a level set of a real-valued
function is defined in terms of the magnitude of the perturbation necessary to
kill the classes. Prior work has shown that the homology and robustness information
can be read off the extended persistence diagram of the function. This paper extends
these results to a non-uniform error model in which perturbations vary in their
magnitude across the domain.
alternative_title:
- LNCS
author:
- first_name: Paul
full_name: Bendich, Paul
id: 43F6EC54-F248-11E8-B48F-1D18A9856A87
last_name: Bendich
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
- first_name: Michael
full_name: Kerber, Michael
id: 36E4574A-F248-11E8-B48F-1D18A9856A87
last_name: Kerber
orcid: 0000-0002-8030-9299
- first_name: Amit
full_name: Patel, Amit
id: 34A254A0-F248-11E8-B48F-1D18A9856A87
last_name: Patel
citation:
ama: 'Bendich P, Edelsbrunner H, Kerber M, Patel A. Persistent homology under non-uniform
error. In: Vol 6281. Springer; 2010:12-23. doi:10.1007/978-3-642-15155-2_2'
apa: 'Bendich, P., Edelsbrunner, H., Kerber, M., & Patel, A. (2010). Persistent
homology under non-uniform error (Vol. 6281, pp. 12–23). Presented at the MFCS:
Mathematical Foundations of Computer Science, Brno, Czech Republic: Springer.
https://doi.org/10.1007/978-3-642-15155-2_2'
chicago: Bendich, Paul, Herbert Edelsbrunner, Michael Kerber, and Amit Patel. “Persistent
Homology under Non-Uniform Error,” 6281:12–23. Springer, 2010. https://doi.org/10.1007/978-3-642-15155-2_2.
ieee: 'P. Bendich, H. Edelsbrunner, M. Kerber, and A. Patel, “Persistent homology
under non-uniform error,” presented at the MFCS: Mathematical Foundations of Computer
Science, Brno, Czech Republic, 2010, vol. 6281, pp. 12–23.'
ista: 'Bendich P, Edelsbrunner H, Kerber M, Patel A. 2010. Persistent homology under
non-uniform error. MFCS: Mathematical Foundations of Computer Science, LNCS, vol.
6281, 12–23.'
mla: Bendich, Paul, et al. Persistent Homology under Non-Uniform Error. Vol.
6281, Springer, 2010, pp. 12–23, doi:10.1007/978-3-642-15155-2_2.
short: P. Bendich, H. Edelsbrunner, M. Kerber, A. Patel, in:, Springer, 2010, pp.
12–23.
conference:
end_date: 2010-08-27
location: Brno, Czech Republic
name: 'MFCS: Mathematical Foundations of Computer Science'
start_date: 2010-08-23
date_created: 2018-12-11T12:05:30Z
date_published: 2010-08-10T00:00:00Z
date_updated: 2021-01-12T07:52:38Z
day: '10'
ddc:
- '000'
department:
- _id: HeEd
doi: 10.1007/978-3-642-15155-2_2
file:
- access_level: open_access
checksum: af61e1c2bb42f3d556179d4692caeb1b
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:13:13Z
date_updated: 2020-07-14T12:46:17Z
file_id: '4994'
file_name: IST-2016-537-v1+1_2010-P-05-NonuniformError.pdf
file_size: 142357
relation: main_file
file_date_updated: 2020-07-14T12:46:17Z
has_accepted_license: '1'
intvolume: ' 6281'
language:
- iso: eng
month: '08'
oa: 1
oa_version: Submitted Version
page: 12 - 23
publication_status: published
publisher: Springer
publist_id: '2333'
pubrep_id: '537'
quality_controlled: '1'
scopus_import: 1
status: public
title: Persistent homology under non-uniform error
type: conference
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
volume: 6281
year: '2010'
...
---
_id: '385'
abstract:
- lang: eng
text: 'Scanning tunneling spectroscopy studies on high-quality Bi2Te3 crystals exhibit
perfect correspondence to angle-resolved photoemission spectroscopy data, hence
enabling identification of different regimes measured in the local density of
states (LDOS). Oscillations of LDOS near a step are analyzed. Within the main
part of the surface band oscillations are strongly damped, supporting the hypothesis
of topological protection. At higher energies, as the surface band becomes concave,
oscillations appear, dispersing with a wave vector that may result from a hexagonal
warping term. '
author:
- first_name: Zhanybek
full_name: Alpichshev, Zhanybek
id: 45E67A2A-F248-11E8-B48F-1D18A9856A87
last_name: Alpichshev
orcid: 0000-0002-7183-5203
- first_name: James
full_name: Analytis, James
last_name: Analytis
- first_name: Jiunhaw
full_name: Chu, Jiunhaw
last_name: Chu
- first_name: Ian
full_name: Fisher, Ian
last_name: Fisher
- first_name: Yulin
full_name: Chen, Yulin
last_name: Chen
- first_name: Zhixun
full_name: Shen, Zhixun
last_name: Shen
- first_name: Aiping
full_name: Fang, Aiping
last_name: Fang
- first_name: Aharon
full_name: Kapitulnik, Aharon
last_name: Kapitulnik
citation:
ama: Alpichshev Z, Analytis J, Chu J, et al. STM imaging of electronic waves on
the surface of Bi2Te3 Topologically protected surface states and hexagonal warping
effects. Physical Review Letters. 2010;104(1). doi:10.1103/PhysRevLett.104.016401
apa: Alpichshev, Z., Analytis, J., Chu, J., Fisher, I., Chen, Y., Shen, Z., … Kapitulnik,
A. (2010). STM imaging of electronic waves on the surface of Bi2Te3 Topologically
protected surface states and hexagonal warping effects. Physical Review Letters.
American Physical Society. https://doi.org/10.1103/PhysRevLett.104.016401
chicago: Alpichshev, Zhanybek, James Analytis, Jiunhaw Chu, Ian Fisher, Yulin Chen,
Zhixun Shen, Aiping Fang, and Aharon Kapitulnik. “STM Imaging of Electronic Waves
on the Surface of Bi2Te3 Topologically Protected Surface States and Hexagonal
Warping Effects.” Physical Review Letters. American Physical Society, 2010.
https://doi.org/10.1103/PhysRevLett.104.016401.
ieee: Z. Alpichshev et al., “STM imaging of electronic waves on the surface
of Bi2Te3 Topologically protected surface states and hexagonal warping effects,”
Physical Review Letters, vol. 104, no. 1. American Physical Society, 2010.
ista: Alpichshev Z, Analytis J, Chu J, Fisher I, Chen Y, Shen Z, Fang A, Kapitulnik
A. 2010. STM imaging of electronic waves on the surface of Bi2Te3 Topologically
protected surface states and hexagonal warping effects. Physical Review Letters.
104(1).
mla: Alpichshev, Zhanybek, et al. “STM Imaging of Electronic Waves on the Surface
of Bi2Te3 Topologically Protected Surface States and Hexagonal Warping Effects.”
Physical Review Letters, vol. 104, no. 1, American Physical Society, 2010,
doi:10.1103/PhysRevLett.104.016401.
short: Z. Alpichshev, J. Analytis, J. Chu, I. Fisher, Y. Chen, Z. Shen, A. Fang,
A. Kapitulnik, Physical Review Letters 104 (2010).
date_created: 2018-12-11T11:46:10Z
date_published: 2010-01-04T00:00:00Z
date_updated: 2021-01-12T07:52:39Z
day: '04'
doi: 10.1103/PhysRevLett.104.016401
extern: '1'
intvolume: ' 104'
issue: '1'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/pdf/0908.0371.pdf
month: '01'
oa: 1
oa_version: None
publication: Physical Review Letters
publication_status: published
publisher: American Physical Society
publist_id: '7444'
status: public
title: STM imaging of electronic waves on the surface of Bi2Te3 Topologically protected
surface states and hexagonal warping effects
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 104
year: '2010'
...
---
_id: '3850'
abstract:
- lang: eng
text: Given a polygonal shape Q with n vertices, can it be expressed, up to a tolerance
ε in Hausdorff distance, as the Minkowski sum of another polygonal shape with
a disk of fixed radius? If it does, we also seek a preferably simple solution
shape P;P’s offset constitutes an accurate, vertex-reduced, and smoothened approximation
of Q. We give a decision algorithm for fixed radius in O(nlogn) time that handles
any polygonal shape. For convex shapes, the complexity drops to O(n), which is
also the time required to compute a solution shape P with at most one more vertex
than a vertex-minimal one.
author:
- first_name: Eric
full_name: Berberich, Eric
last_name: Berberich
- first_name: Dan
full_name: Halperin, Dan
last_name: Halperin
- first_name: Michael
full_name: Kerber, Michael
id: 36E4574A-F248-11E8-B48F-1D18A9856A87
last_name: Kerber
orcid: 0000-0002-8030-9299
- first_name: Roza
full_name: Pogalnikova, Roza
last_name: Pogalnikova
citation:
ama: 'Berberich E, Halperin D, Kerber M, Pogalnikova R. Polygonal reconstruction
from approximate offsets. In: TU Dortmund; 2010:12-23.'
apa: 'Berberich, E., Halperin, D., Kerber, M., & Pogalnikova, R. (2010). Polygonal
reconstruction from approximate offsets (pp. 12–23). Presented at the EuroCG:
European Workshop on Computational Geometry, Dortmund, Germany: TU Dortmund.'
chicago: Berberich, Eric, Dan Halperin, Michael Kerber, and Roza Pogalnikova. “Polygonal
Reconstruction from Approximate Offsets,” 12–23. TU Dortmund, 2010.
ieee: 'E. Berberich, D. Halperin, M. Kerber, and R. Pogalnikova, “Polygonal reconstruction
from approximate offsets,” presented at the EuroCG: European Workshop on Computational
Geometry, Dortmund, Germany, 2010, pp. 12–23.'
ista: 'Berberich E, Halperin D, Kerber M, Pogalnikova R. 2010. Polygonal reconstruction
from approximate offsets. EuroCG: European Workshop on Computational Geometry,
12–23.'
mla: Berberich, Eric, et al. Polygonal Reconstruction from Approximate Offsets.
TU Dortmund, 2010, pp. 12–23.
short: E. Berberich, D. Halperin, M. Kerber, R. Pogalnikova, in:, TU Dortmund, 2010,
pp. 12–23.
conference:
end_date: 2010-03-24
location: Dortmund, Germany
name: 'EuroCG: European Workshop on Computational Geometry'
start_date: 2010-03-22
date_created: 2018-12-11T12:05:30Z
date_published: 2010-01-01T00:00:00Z
date_updated: 2021-01-12T07:52:39Z
day: '01'
department:
- _id: HeEd
language:
- iso: eng
month: '01'
oa_version: None
page: 12 - 23
publication_status: published
publisher: TU Dortmund
publist_id: '2334'
quality_controlled: '1'
status: public
title: Polygonal reconstruction from approximate offsets
type: conference
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
year: '2010'
...
---
_id: '3851'
abstract:
- lang: eng
text: 'Energy parity games are infinite two-player turn-based games played on weighted
graphs. The objective of the game combines a (qualitative) parity condition with
the (quantitative) requirement that the sum of the weights (i.e., the level of
energy in the game) must remain positive. Beside their own interest in the design
and synthesis of resource-constrained omega-regular specifications, energy parity
games provide one of the simplest model of games with combined qualitative and
quantitative objective. Our main results are as follows: (a) exponential memory
is sufficient and may be necessary for winning strategies in energy parity games;
(b) the problem of deciding the winner in energy parity games can be solved in
NP ∩ coNP; and (c) we give an algorithm to solve energy parity by reduction to
energy games. We also show that the problem of deciding the winner in energy parity
games is polynomially equivalent to the problem of deciding the winner in mean-payoff
parity games, which can thus be solved in NP ∩ coNP. As a consequence we also
obtain a conceptually simple algorithm to solve mean-payoff parity games.'
alternative_title:
- LNCS
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: Laurent
full_name: Doyen, Laurent
last_name: Doyen
citation:
ama: 'Chatterjee K, Doyen L. Energy parity games. In: Vol 6199. Springer; 2010:599-610.
doi:10.1007/978-3-642-14162-1_50'
apa: 'Chatterjee, K., & Doyen, L. (2010). Energy parity games (Vol. 6199, pp.
599–610). Presented at the ICALP: Automata, Languages and Programming, 37th International
Colloquium, Bordeaux, France: Springer. https://doi.org/10.1007/978-3-642-14162-1_50'
chicago: Chatterjee, Krishnendu, and Laurent Doyen. “Energy Parity Games,” 6199:599–610.
Springer, 2010. https://doi.org/10.1007/978-3-642-14162-1_50.
ieee: 'K. Chatterjee and L. Doyen, “Energy parity games,” presented at the ICALP:
Automata, Languages and Programming, 37th International Colloquium, Bordeaux,
France, 2010, vol. 6199, pp. 599–610.'
ista: 'Chatterjee K, Doyen L. 2010. Energy parity games. ICALP: Automata, Languages
and Programming, 37th International Colloquium, LNCS, vol. 6199, 599–610.'
mla: Chatterjee, Krishnendu, and Laurent Doyen. Energy Parity Games. Vol.
6199, Springer, 2010, pp. 599–610, doi:10.1007/978-3-642-14162-1_50.
short: K. Chatterjee, L. Doyen, in:, Springer, 2010, pp. 599–610.
conference:
end_date: 2010-07-10
location: Bordeaux, France
name: ' ICALP: Automata, Languages and Programming, 37th International Colloquium'
start_date: 2010-07-06
date_created: 2018-12-11T12:05:31Z
date_published: 2010-09-10T00:00:00Z
date_updated: 2023-02-23T11:06:35Z
day: '10'
department:
- _id: KrCh
doi: 10.1007/978-3-642-14162-1_50
external_id:
arxiv:
- '1001.5183'
intvolume: ' 6199'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1001.5183
month: '09'
oa: 1
oa_version: Preprint
page: 599 - 610
publication_status: published
publisher: Springer
publist_id: '2330'
quality_controlled: '1'
related_material:
record:
- id: '2972'
relation: later_version
status: public
scopus_import: 1
status: public
title: Energy parity games
type: conference
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
volume: 6199
year: '2010'
...
---
_id: '3852'
abstract:
- lang: eng
text: 'We introduce two-level discounted games played by two players on a perfect-information
stochastic game graph. The upper level game is a discounted game and the lower
level game is an undiscounted reachability game. Two-level games model hierarchical
and sequential decision making under uncertainty across different time scales.
We show the existence of pure memoryless optimal strategies for both players and
an ordered field property for such games. We show that if there is only one player
(Markov decision processes), then the values can be computed in polynomial time.
It follows that whether the value of a player is equal to a given rational constant
in two-level discounted games can be decided in NP intersected coNP. We also give
an alternate strategy improvement algorithm to compute the value. '
alternative_title:
- EPTCS
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: Ritankar
full_name: Majumdar, Ritankar
last_name: Majumdar
citation:
ama: 'Chatterjee K, Majumdar R. Discounting in games across time scales. In: Vol
25. EPTCS; 2010:22-29. doi:10.4204/EPTCS.25.6'
apa: 'Chatterjee, K., & Majumdar, R. (2010). Discounting in games across time
scales (Vol. 25, pp. 22–29). Presented at the GandALF: Games, Automata, Logic,
and Formal Verification, Minori, Italy: EPTCS. https://doi.org/10.4204/EPTCS.25.6'
chicago: Chatterjee, Krishnendu, and Ritankar Majumdar. “Discounting in Games across
Time Scales,” 25:22–29. EPTCS, 2010. https://doi.org/10.4204/EPTCS.25.6.
ieee: 'K. Chatterjee and R. Majumdar, “Discounting in games across time scales,”
presented at the GandALF: Games, Automata, Logic, and Formal Verification, Minori,
Italy, 2010, vol. 25, pp. 22–29.'
ista: 'Chatterjee K, Majumdar R. 2010. Discounting in games across time scales.
GandALF: Games, Automata, Logic, and Formal Verification, EPTCS, vol. 25, 22–29.'
mla: Chatterjee, Krishnendu, and Ritankar Majumdar. Discounting in Games across
Time Scales. Vol. 25, EPTCS, 2010, pp. 22–29, doi:10.4204/EPTCS.25.6.
short: K. Chatterjee, R. Majumdar, in:, EPTCS, 2010, pp. 22–29.
conference:
end_date: 2010-06-18
location: Minori, Italy
name: 'GandALF: Games, Automata, Logic, and Formal Verification'
start_date: 2010-06-17
date_created: 2018-12-11T12:05:31Z
date_published: 2010-06-08T00:00:00Z
date_updated: 2023-09-04T11:47:04Z
day: '08'
ddc:
- '000'
department:
- _id: KrCh
doi: 10.4204/EPTCS.25.6
external_id:
arxiv:
- '1006.1403'
file:
- access_level: open_access
checksum: 2bdf1e9103710555c6251ca4153cb5e9
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:12:19Z
date_updated: 2020-07-14T12:46:17Z
file_id: '4937'
file_name: IST-2016-491-v1+1_1006.1403v1.pdf
file_size: 74598
relation: main_file
file_date_updated: 2020-07-14T12:46:17Z
has_accepted_license: '1'
intvolume: ' 25'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
page: 22 - 29
publication_status: published
publisher: EPTCS
publist_id: '2329'
pubrep_id: '491'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Discounting in games across time scales
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 25
year: '2010'
...
---
_id: '3853'
abstract:
- lang: eng
text: 'Quantitative languages are an extension of boolean languages that assign
to each word a real number. Mean-payoff automata are finite automata with numerical
weights on transitions that assign to each infinite path the long-run average
of the transition weights. When the mode of branching of the automaton is deterministic,
nondeterministic, or alternating, the corresponding class of quantitative languages
is not robust as it is not closed under the pointwise operations of max, min,
sum, and numerical complement. Nondeterministic and alternating mean-payoff automata
are not decidable either, as the quantitative generalization of the problems of
universality and language inclusion is undecidable. We introduce a new class of
quantitative languages, defined by mean-payoff automaton expressions, which is
robust and decidable: it is closed under the four pointwise operations, and we
show that all decision problems are decidable for this class. Mean-payoff automaton
expressions subsume deterministic meanpayoff automata, and we show that they have
expressive power incomparable to nondeterministic and alternating mean-payoff
automata. We also present for the first time an algorithm to compute distance
between two quantitative languages, and in our case the quantitative languages
are given as mean-payoff automaton expressions.'
alternative_title:
- LNCS
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: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
- 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: Philippe
full_name: Rannou, Philippe
last_name: Rannou
citation:
ama: 'Chatterjee K, Doyen L, Edelsbrunner H, Henzinger TA, Rannou P. Mean-payoff
automaton expressions. In: Vol 6269. Schloss Dagstuhl - Leibniz-Zentrum für Informatik;
2010:269-283. doi:10.1007/978-3-642-15375-4_19'
apa: 'Chatterjee, K., Doyen, L., Edelsbrunner, H., Henzinger, T. A., & Rannou,
P. (2010). Mean-payoff automaton expressions (Vol. 6269, pp. 269–283). Presented
at the CONCUR: Concurrency Theory, Paris, France: Schloss Dagstuhl - Leibniz-Zentrum
für Informatik. https://doi.org/10.1007/978-3-642-15375-4_19'
chicago: Chatterjee, Krishnendu, Laurent Doyen, Herbert Edelsbrunner, Thomas A Henzinger,
and Philippe Rannou. “Mean-Payoff Automaton Expressions,” 6269:269–83. Schloss
Dagstuhl - Leibniz-Zentrum für Informatik, 2010. https://doi.org/10.1007/978-3-642-15375-4_19.
ieee: 'K. Chatterjee, L. Doyen, H. Edelsbrunner, T. A. Henzinger, and P. Rannou,
“Mean-payoff automaton expressions,” presented at the CONCUR: Concurrency Theory,
Paris, France, 2010, vol. 6269, pp. 269–283.'
ista: 'Chatterjee K, Doyen L, Edelsbrunner H, Henzinger TA, Rannou P. 2010. Mean-payoff
automaton expressions. CONCUR: Concurrency Theory, LNCS, vol. 6269, 269–283.'
mla: Chatterjee, Krishnendu, et al. Mean-Payoff Automaton Expressions. Vol.
6269, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2010, pp. 269–83, doi:10.1007/978-3-642-15375-4_19.
short: K. Chatterjee, L. Doyen, H. Edelsbrunner, T.A. Henzinger, P. Rannou, in:,
Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2010, pp. 269–283.
conference:
end_date: 2010-09-03
location: Paris, France
name: 'CONCUR: Concurrency Theory'
start_date: 2010-08-31
date_created: 2018-12-11T12:05:31Z
date_published: 2010-11-18T00:00:00Z
date_updated: 2021-01-12T07:52:40Z
day: '18'
ddc:
- '000'
- '005'
department:
- _id: KrCh
- _id: HeEd
- _id: ToHe
doi: 10.1007/978-3-642-15375-4_19
ec_funded: 1
file:
- access_level: open_access
checksum: 4f753ae99d076553fb8733e2c8b390e2
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:15:41Z
date_updated: 2020-07-14T12:46:17Z
file_id: '5163'
file_name: IST-2012-62-v1+1_Mean-payoff_automaton_expressions.pdf
file_size: 233260
relation: main_file
file_date_updated: 2020-07-14T12:46:17Z
has_accepted_license: '1'
intvolume: ' 6269'
language:
- iso: eng
month: '11'
oa: 1
oa_version: Submitted Version
page: 269 - 283
project:
- _id: 25EFB36C-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '215543'
name: COMponent-Based Embedded Systems design Techniques
- _id: 25F1337C-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '214373'
name: Design for Embedded Systems
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
publist_id: '2328'
pubrep_id: '62'
quality_controlled: '1'
scopus_import: 1
status: public
title: Mean-payoff automaton expressions
type: conference
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
volume: 6269
year: '2010'
...
---
_id: '3854'
abstract:
- lang: eng
text: 'Graph games of infinite length provide a natural model for open reactive
systems: one player (Eve) represents the controller and the other player (Adam)
represents the environment. The evolution of the system depends on the decisions
of both players. The specification for the system is usually given as an ω-regular
language L over paths and Eve’s goal is to ensure that the play belongs to L irrespective
of Adam’s behaviour. The classical notion of winning strategies fails to capture
several interesting scenarios. For example, strong fairness (Streett) conditions
are specified by a number of request-grant pairs and require every pair that is
requested infinitely often to be granted infinitely often: Eve might win just
by preventing Adam from making any new request, but a “better” strategy would
allow Adam to make as many requests as possible and still ensure fairness. To
address such questions, we introduce the notion of obliging games, where Eve has
to ensure a strong condition Φ, while always allowing Adam to satisfy a weak condition
Ψ. We present a linear time reduction of obliging games with two Muller conditions
Φ and Ψ to classical Muller games. We consider obliging Streett games and show
they are co-NP complete, and show a natural quantitative optimisation problem
for obliging Streett games is in FNP. We also show how obliging games can provide
new and interesting semantics for multi-player games.'
alternative_title:
- LNCS
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Florian
full_name: Horn, Florian
id: 37327ACE-F248-11E8-B48F-1D18A9856A87
last_name: Horn
- first_name: Christof
full_name: Löding, Christof
last_name: Löding
citation:
ama: 'Chatterjee K, Horn F, Löding C. Obliging games. In: Vol 6269. Schloss Dagstuhl
- Leibniz-Zentrum für Informatik; 2010:284-296. doi:10.1007/978-3-642-15375-4_20'
apa: 'Chatterjee, K., Horn, F., & Löding, C. (2010). Obliging games (Vol. 6269,
pp. 284–296). Presented at the CONCUR: Concurrency Theory, Paris, France: Schloss
Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.1007/978-3-642-15375-4_20'
chicago: Chatterjee, Krishnendu, Florian Horn, and Christof Löding. “Obliging Games,”
6269:284–96. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2010. https://doi.org/10.1007/978-3-642-15375-4_20.
ieee: 'K. Chatterjee, F. Horn, and C. Löding, “Obliging games,” presented at the
CONCUR: Concurrency Theory, Paris, France, 2010, vol. 6269, pp. 284–296.'
ista: 'Chatterjee K, Horn F, Löding C. 2010. Obliging games. CONCUR: Concurrency
Theory, LNCS, vol. 6269, 284–296.'
mla: Chatterjee, Krishnendu, et al. Obliging Games. Vol. 6269, Schloss Dagstuhl
- Leibniz-Zentrum für Informatik, 2010, pp. 284–96, doi:10.1007/978-3-642-15375-4_20.
short: K. Chatterjee, F. Horn, C. Löding, in:, Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2010, pp. 284–296.
conference:
end_date: 2010-09-03
location: Paris, France
name: 'CONCUR: Concurrency Theory'
start_date: 2010-08-31
date_created: 2018-12-11T12:05:32Z
date_published: 2010-09-08T00:00:00Z
date_updated: 2021-01-12T07:52:41Z
day: '08'
department:
- _id: KrCh
doi: 10.1007/978-3-642-15375-4_20
intvolume: ' 6269'
language:
- iso: eng
month: '09'
oa_version: None
page: 284 - 296
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
publist_id: '2327'
quality_controlled: '1'
scopus_import: 1
status: public
title: Obliging games
type: conference
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
volume: 6269
year: '2010'
...
---
_id: '3855'
abstract:
- lang: eng
text: 'We study observation-based strategies for partially-observable Markov decision
processes (POMDPs) with parity objectives. An observation-based strategy relies
on partial information about the history of a play, namely, on the past sequence
of observations. We consider qualitative analysis problems: given a POMDP with
a parity objective, decide whether there exists an observation-based strategy
to achieve the objective with probability 1 (almost-sure winning), or with positive
probability (positive winning). Our main results are twofold. First, we present
a complete picture of the computational complexity of the qualitative analysis
problem for POMDPs with parity objectives and its subclasses: safety, reachability,
Büchi, and coBüchi objectives. We establish several upper and lower bounds that
were not known in the literature. Second, we give optimal bounds (matching upper
and lower bounds) for the memory required by pure and randomized observation-based
strategies for each class of objectives.'
alternative_title:
- LNCS
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. Qualitative analysis of partially-observable
Markov Decision Processes. In: Vol 6281. Springer; 2010:258-269. doi:10.1007/978-3-642-15155-2_24'
apa: 'Chatterjee, K., Doyen, L., & Henzinger, T. A. (2010). Qualitative analysis
of partially-observable Markov Decision Processes (Vol. 6281, pp. 258–269). Presented
at the MFCS: Mathematical Foundations of Computer Science, Brno, Czech Republic:
Springer. https://doi.org/10.1007/978-3-642-15155-2_24'
chicago: Chatterjee, Krishnendu, Laurent Doyen, and Thomas A Henzinger. “Qualitative
Analysis of Partially-Observable Markov Decision Processes,” 6281:258–69. Springer,
2010. https://doi.org/10.1007/978-3-642-15155-2_24.
ieee: 'K. Chatterjee, L. Doyen, and T. A. Henzinger, “Qualitative analysis of partially-observable
Markov Decision Processes,” presented at the MFCS: Mathematical Foundations of
Computer Science, Brno, Czech Republic, 2010, vol. 6281, pp. 258–269.'
ista: 'Chatterjee K, Doyen L, Henzinger TA. 2010. Qualitative analysis of partially-observable
Markov Decision Processes. MFCS: Mathematical Foundations of Computer Science,
LNCS, vol. 6281, 258–269.'
mla: Chatterjee, Krishnendu, et al. Qualitative Analysis of Partially-Observable
Markov Decision Processes. Vol. 6281, Springer, 2010, pp. 258–69, doi:10.1007/978-3-642-15155-2_24.
short: K. Chatterjee, L. Doyen, T.A. Henzinger, in:, Springer, 2010, pp. 258–269.
conference:
end_date: 2010-08-27
location: Brno, Czech Republic
name: 'MFCS: Mathematical Foundations of Computer Science'
start_date: 2010-08-23
date_created: 2018-12-11T12:05:32Z
date_published: 2010-08-01T00:00:00Z
date_updated: 2023-02-23T12:24:22Z
day: '01'
ddc:
- '004'
department:
- _id: KrCh
- _id: ToHe
doi: 10.1007/978-3-642-15155-2_24
ec_funded: 1
file:
- access_level: open_access
checksum: b6c82ec82f194e5b0ab7c1c3800e4580
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:13:51Z
date_updated: 2020-07-14T12:46:17Z
file_id: '5038'
file_name: IST-2012-61-v1+1_Qualitative_analysis_of_partially-observable_Markov_Decision_Processes.pdf
file_size: 173948
relation: main_file
file_date_updated: 2020-07-14T12:46:17Z
has_accepted_license: '1'
intvolume: ' 6281'
language:
- iso: eng
month: '08'
oa: 1
oa_version: Submitted Version
page: 258 - 269
project:
- _id: 25EFB36C-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '215543'
name: COMponent-Based Embedded Systems design Techniques
- _id: 25F1337C-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '214373'
name: Design for Embedded Systems
publication_status: published
publisher: Springer
publist_id: '2326'
pubrep_id: '61'
quality_controlled: '1'
related_material:
record:
- id: '5395'
relation: earlier_version
status: public
scopus_import: 1
status: public
title: Qualitative analysis of partially-observable Markov Decision Processes
type: conference
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
volume: 6281
year: '2010'
...
---
_id: '3856'
abstract:
- lang: eng
text: 'We consider two-player zero-sum games on graphs. These games can be classified
on the basis of the information of the players and on the mode of interaction
between them. On the basis of information the classification is as follows: (a)
partial-observation (both players have partial view of the game); (b) one-sided
complete-observation (one player has complete observation); and (c) complete-observation
(both players have complete view of the game). On the basis of mode of interaction
we have the following classification: (a) concurrent (players interact simultaneously);
and (b) turn-based (players interact in turn). The two sources of randomness in
these games are randomness in transition function and randomness in strategies.
In general, randomized strategies are more powerful than deterministic strategies,
and randomness in transitions gives more general classes of games. We present
a complete characterization for the classes of games where randomness is not helpful
in: (a) the transition function (probabilistic transition can be simulated by
deterministic transition); and (b) strategies (pure strategies are as powerful
as randomized strategies). As consequence of our characterization we obtain new
undecidability results for these games. '
acknowledgement: This research was supported by the European Union project COMBEST
and the European Network of Excellence ArtistDesign.
alternative_title:
- LNCS
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: Hugo
full_name: Gimbert, Hugo
last_name: Gimbert
- 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, Gimbert H, Henzinger TA. Randomness for free. In: Vol
6281. Springer; 2010:246-257. doi:10.1007/978-3-642-15155-2_23'
apa: 'Chatterjee, K., Doyen, L., Gimbert, H., & Henzinger, T. A. (2010). Randomness
for free (Vol. 6281, pp. 246–257). Presented at the MFCS: Mathematical Foundations
of Computer Science, Brno, Czech Republic: Springer. https://doi.org/10.1007/978-3-642-15155-2_23'
chicago: Chatterjee, Krishnendu, Laurent Doyen, Hugo Gimbert, and Thomas A Henzinger.
“Randomness for Free,” 6281:246–57. Springer, 2010. https://doi.org/10.1007/978-3-642-15155-2_23.
ieee: 'K. Chatterjee, L. Doyen, H. Gimbert, and T. A. Henzinger, “Randomness for
free,” presented at the MFCS: Mathematical Foundations of Computer Science, Brno,
Czech Republic, 2010, vol. 6281, pp. 246–257.'
ista: 'Chatterjee K, Doyen L, Gimbert H, Henzinger TA. 2010. Randomness for free.
MFCS: Mathematical Foundations of Computer Science, LNCS, vol. 6281, 246–257.'
mla: Chatterjee, Krishnendu, et al. Randomness for Free. Vol. 6281, Springer,
2010, pp. 246–57, doi:10.1007/978-3-642-15155-2_23.
short: K. Chatterjee, L. Doyen, H. Gimbert, T.A. Henzinger, in:, Springer, 2010,
pp. 246–257.
conference:
end_date: 2010-08-27
location: Brno, Czech Republic
name: 'MFCS: Mathematical Foundations of Computer Science'
start_date: 2010-08-23
date_created: 2018-12-11T12:05:32Z
date_published: 2010-09-06T00:00:00Z
date_updated: 2023-02-23T10:12:00Z
day: '06'
department:
- _id: KrCh
- _id: ToHe
doi: 10.1007/978-3-642-15155-2_23
ec_funded: 1
intvolume: ' 6281'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1006.0673v1
month: '09'
oa: 1
oa_version: Preprint
page: 246 - 257
project:
- _id: 25EFB36C-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '215543'
name: COMponent-Based Embedded Systems design Techniques
- _id: 25F1337C-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '214373'
name: Design for Embedded Systems
publication_status: published
publisher: Springer
publist_id: '2325'
pubrep_id: '60'
quality_controlled: '1'
related_material:
record:
- id: '1731'
relation: later_version
status: public
scopus_import: 1
status: public
title: Randomness for free
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 6281
year: '2010'
...
---
_id: '3857'
abstract:
- lang: eng
text: We consider probabilistic automata on infinite words with acceptance defined
by safety, reachability, Büchi, coBüchi, and limit-average conditions. We consider
quantitative and qualitative decision problems. We present extensions and adaptations
of proofs for probabilistic finite automata and present an almost complete characterization
of the decidability and undecidability frontier of the quantitative and qualitative
decision problems for probabilistic automata on infinite words.
alternative_title:
- LNCS
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. Probabilistic Automata on infinite words: decidability
and undecidability results. In: Vol 6252. Springer; 2010:1-16. doi:10.1007/978-3-642-15643-4_1'
apa: 'Chatterjee, K., & Henzinger, T. A. (2010). Probabilistic Automata on infinite
words: decidability and undecidability results (Vol. 6252, pp. 1–16). Presented
at the ATVA: Automated Technology for Verification and Analysis, Singapore, Singapore:
Springer. https://doi.org/10.1007/978-3-642-15643-4_1'
chicago: 'Chatterjee, Krishnendu, and Thomas A Henzinger. “Probabilistic Automata
on Infinite Words: Decidability and Undecidability Results,” 6252:1–16. Springer,
2010. https://doi.org/10.1007/978-3-642-15643-4_1.'
ieee: 'K. Chatterjee and T. A. Henzinger, “Probabilistic Automata on infinite words:
decidability and undecidability results,” presented at the ATVA: Automated Technology
for Verification and Analysis, Singapore, Singapore, 2010, vol. 6252, pp. 1–16.'
ista: 'Chatterjee K, Henzinger TA. 2010. Probabilistic Automata on infinite words:
decidability and undecidability results. ATVA: Automated Technology for Verification
and Analysis, LNCS, vol. 6252, 1–16.'
mla: 'Chatterjee, Krishnendu, and Thomas A. Henzinger. Probabilistic Automata
on Infinite Words: Decidability and Undecidability Results. Vol. 6252, Springer,
2010, pp. 1–16, doi:10.1007/978-3-642-15643-4_1.'
short: K. Chatterjee, T.A. Henzinger, in:, Springer, 2010, pp. 1–16.
conference:
end_date: 2010-09-24
location: Singapore, Singapore
name: 'ATVA: Automated Technology for Verification and Analysis'
start_date: 2010-09-21
date_created: 2018-12-11T12:05:33Z
date_published: 2010-10-12T00:00:00Z
date_updated: 2023-02-23T12:24:14Z
day: '12'
department:
- _id: KrCh
- _id: ToHe
doi: 10.1007/978-3-642-15643-4_1
ec_funded: 1
intvolume: ' 6252'
language:
- iso: eng
month: '10'
oa_version: None
page: 1 - 16
project:
- _id: 25EFB36C-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '215543'
name: COMponent-Based Embedded Systems design Techniques
- _id: 25F1337C-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '214373'
name: Design for Embedded Systems
publication_status: published
publisher: Springer
publist_id: '2324'
pubrep_id: '28'
quality_controlled: '1'
related_material:
record:
- id: '5392'
relation: earlier_version
status: public
scopus_import: 1
status: public
title: 'Probabilistic Automata on infinite words: decidability and undecidability
results'
type: conference
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
volume: 6252
year: '2010'
...