---
_id: '475'
abstract:
- lang: eng
text: 'First cycle games (FCG) are played on a finite graph by two players who push
a token along the edges until a vertex is repeated, and a simple cycle is formed.
The winner is determined by some fixed property Y of the sequence of labels of
the edges (or nodes) forming this cycle. These games are traditionally of interest
because of their connection with infinite-duration games such as parity and mean-payoff
games. We study the memory requirements for winning strategies of FCGs and certain
associated infinite duration games. We exhibit a simple FCG that is not memoryless
determined (this corrects a mistake in Memoryless determinacy of parity and mean
payoff games: a simple proof by Bj⋯orklund, Sandberg, Vorobyov (2004) that claims
that FCGs for which Y is closed under cyclic permutations are memoryless determined).
We show that θ (n)! memory (where n is the number of nodes in the graph), which
is always sufficient, may be necessary to win some FCGs. On the other hand, we
identify easy to check conditions on Y (i.e., Y is closed under cyclic permutations,
and both Y and its complement are closed under concatenation) that are sufficient
to ensure that the corresponding FCGs and their associated infinite duration games
are memoryless determined. We demonstrate that many games considered in the literature,
such as mean-payoff, parity, energy, etc., satisfy these conditions. On the complexity
side, we show (for efficiently computable Y) that while solving FCGs is in PSPACE,
solving some families of FCGs is PSPACE-hard. '
alternative_title:
- EPTCS
author:
- first_name: Benjamin
full_name: Aminof, Benjamin
id: 4A55BD00-F248-11E8-B48F-1D18A9856A87
last_name: Aminof
- first_name: Sasha
full_name: Rubin, Sasha
id: 2EC51194-F248-11E8-B48F-1D18A9856A87
last_name: Rubin
citation:
ama: 'Aminof B, Rubin S. First cycle games. In: Electronic Proceedings in Theoretical
Computer Science, EPTCS. Vol 146. Open Publishing Association; 2014:83-90.
doi:10.4204/EPTCS.146.11'
apa: 'Aminof, B., & Rubin, S. (2014). First cycle games. In Electronic Proceedings
in Theoretical Computer Science, EPTCS (Vol. 146, pp. 83–90). Grenoble, France:
Open Publishing Association. https://doi.org/10.4204/EPTCS.146.11'
chicago: Aminof, Benjamin, and Sasha Rubin. “First Cycle Games.” In Electronic
Proceedings in Theoretical Computer Science, EPTCS, 146:83–90. Open Publishing
Association, 2014. https://doi.org/10.4204/EPTCS.146.11.
ieee: B. Aminof and S. Rubin, “First cycle games,” in Electronic Proceedings
in Theoretical Computer Science, EPTCS, Grenoble, France, 2014, vol. 146,
pp. 83–90.
ista: 'Aminof B, Rubin S. 2014. First cycle games. Electronic Proceedings in Theoretical
Computer Science, EPTCS. SR: Strategic Reasoning, EPTCS, vol. 146, 83–90.'
mla: Aminof, Benjamin, and Sasha Rubin. “First Cycle Games.” Electronic Proceedings
in Theoretical Computer Science, EPTCS, vol. 146, Open Publishing Association,
2014, pp. 83–90, doi:10.4204/EPTCS.146.11.
short: B. Aminof, S. Rubin, in:, Electronic Proceedings in Theoretical Computer
Science, EPTCS, Open Publishing Association, 2014, pp. 83–90.
conference:
end_date: 2014-04-06
location: Grenoble, France
name: 'SR: Strategic Reasoning'
start_date: 2014-04-05
date_created: 2018-12-11T11:46:41Z
date_published: 2014-04-01T00:00:00Z
date_updated: 2021-01-12T08:00:53Z
day: '01'
ddc:
- '004'
department:
- _id: KrCh
doi: 10.4204/EPTCS.146.11
ec_funded: 1
file:
- access_level: open_access
checksum: 4d7b4ab82980cca2b96ac7703992a8c8
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:17:08Z
date_updated: 2020-07-14T12:46:35Z
file_id: '5260'
file_name: IST-2018-952-v1+1_2014_Rubin_First_cycle.pdf
file_size: 100115
relation: main_file
file_date_updated: 2020-07-14T12:46:35Z
has_accepted_license: '1'
intvolume: ' 146'
language:
- iso: eng
month: '04'
oa: 1
oa_version: Published Version
page: 83 - 90
project:
- _id: 2584A770-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: P 23499-N23
name: Modern Graph Algorithmic Techniques in Formal Verification
- _id: 25F5A88A-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S11402-N23
name: Moderne Concurrency Paradigms
- _id: 25863FF4-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S11407
name: Game Theory
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '279307'
name: 'Quantitative Graph Games: Theory and Applications'
- _id: 25892FC0-B435-11E9-9278-68D0E5697425
grant_number: ICT15-003
name: Efficient Algorithms for Computer Aided Verification
publication: Electronic Proceedings in Theoretical Computer Science, EPTCS
publication_status: published
publisher: Open Publishing Association
publist_id: '7345'
pubrep_id: '952'
quality_controlled: '1'
scopus_import: 1
status: public
title: First cycle games
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: conference
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
volume: 146
year: '2014'
...
---
_id: '535'
abstract:
- lang: eng
text: Energy games belong to a class of turn-based two-player infinite-duration
games played on a weighted directed graph. It is one of the rare and intriguing
combinatorial problems that lie in NP∩co-NP, but are not known to be in P. The
existence of polynomial-time algorithms has been a major open problem for decades
and apart from pseudopolynomial algorithms there is no algorithm that solves any
non-trivial subclass in polynomial time. In this paper, we give several results
based on the weight structures of the graph. First, we identify a notion of penalty
and present a polynomial-time algorithm when the penalty is large. Our algorithm
is the first polynomial-time algorithm on a large class of weighted graphs. It
includes several worst-case instances on which previous algorithms, such as value
iteration and random facet algorithms, require at least sub-exponential time.
Our main technique is developing the first non-trivial approximation algorithm
and showing how to convert it to an exact algorithm. Moreover, we show that in
a practical case in verification where weights are clustered around a constant
number of values, the energy game problem can be solved in polynomial time. We
also show that the problem is still as hard as in general when the clique-width
is bounded or the graph is strongly ergodic, suggesting that restricting the graph
structure does not necessarily help.
article_processing_charge: No
article_type: original
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: Monika H
full_name: Henzinger, Monika H
id: 540c9bbd-f2de-11ec-812d-d04a5be85630
last_name: Henzinger
orcid: 0000-0002-5008-6530
- first_name: Sebastian
full_name: Krinninger, Sebastian
last_name: Krinninger
- first_name: Danupon
full_name: Nanongkai, Danupon
last_name: Nanongkai
citation:
ama: Chatterjee K, Henzinger MH, Krinninger S, Nanongkai D. Polynomial-time algorithms
for energy games with special weight structures. Algorithmica. 2014;70(3):457-492.
doi:10.1007/s00453-013-9843-7
apa: Chatterjee, K., Henzinger, M. H., Krinninger, S., & Nanongkai, D. (2014).
Polynomial-time algorithms for energy games with special weight structures. Algorithmica.
Springer. https://doi.org/10.1007/s00453-013-9843-7
chicago: Chatterjee, Krishnendu, Monika H Henzinger, Sebastian Krinninger, and Danupon
Nanongkai. “Polynomial-Time Algorithms for Energy Games with Special Weight Structures.”
Algorithmica. Springer, 2014. https://doi.org/10.1007/s00453-013-9843-7.
ieee: K. Chatterjee, M. H. Henzinger, S. Krinninger, and D. Nanongkai, “Polynomial-time
algorithms for energy games with special weight structures,” Algorithmica,
vol. 70, no. 3. Springer, pp. 457–492, 2014.
ista: Chatterjee K, Henzinger MH, Krinninger S, Nanongkai D. 2014. Polynomial-time
algorithms for energy games with special weight structures. Algorithmica. 70(3),
457–492.
mla: Chatterjee, Krishnendu, et al. “Polynomial-Time Algorithms for Energy Games
with Special Weight Structures.” Algorithmica, vol. 70, no. 3, Springer,
2014, pp. 457–92, doi:10.1007/s00453-013-9843-7.
short: K. Chatterjee, M.H. Henzinger, S. Krinninger, D. Nanongkai, Algorithmica
70 (2014) 457–492.
date_created: 2018-12-11T11:47:01Z
date_published: 2014-11-01T00:00:00Z
date_updated: 2023-09-05T14:09:29Z
day: '01'
department:
- _id: KrCh
doi: 10.1007/s00453-013-9843-7
ec_funded: 1
external_id:
arxiv:
- '1604.08234'
intvolume: ' 70'
issue: '3'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1604.08234
month: '11'
oa: 1
oa_version: Preprint
page: 457 - 492
project:
- _id: 2584A770-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: P 23499-N23
name: Modern Graph Algorithmic Techniques in Formal Verification
- _id: 25863FF4-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S11407
name: Game Theory
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '279307'
name: 'Quantitative Graph Games: Theory and Applications'
- _id: 2587B514-B435-11E9-9278-68D0E5697425
name: Microsoft Research Faculty Fellowship
publication: Algorithmica
publication_status: published
publisher: Springer
publist_id: '7282'
quality_controlled: '1'
related_material:
record:
- id: '10905'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: Polynomial-time algorithms for energy games with special weight structures
type: journal_article
user_id: 72615eeb-f1f3-11ec-aa25-d4573ddc34fd
volume: 70
year: '2014'
...
---
_id: '537'
abstract:
- lang: eng
text: Transgenerational effects are broader than only parental relationships. Despite
mounting evidence that multigenerational effects alter phenotypic and life-history
traits, our understanding of how they combine to determine fitness is not well
developed because of the added complexity necessary to study them. Here, we derive
a quantitative genetic model of adaptation to an extraordinary new environment
by an additive genetic component, phenotypic plasticity, maternal and grandmaternal
effects. We show how, at equilibrium, negative maternal and negative grandmaternal
effects maximize expected population mean fitness. We define negative transgenerational
effects as those that have a negative effect on trait expression in the subsequent
generation, that is, they slow, or potentially reverse, the expected evolutionary
dynamic. When maternal effects are positive, negative grandmaternal effects are
preferred. As expected under Mendelian inheritance, the grandmaternal effects
have a lower impact on fitness than the maternal effects, but this dual inheritance
model predicts a more complex relationship between maternal and grandmaternal
effects to constrain phenotypic variance and so maximize expected population mean
fitness in the offspring.
author:
- first_name: Roshan
full_name: Prizak, Roshan
id: 4456104E-F248-11E8-B48F-1D18A9856A87
last_name: Prizak
- first_name: Thomas
full_name: Ezard, Thomas
last_name: Ezard
- first_name: Rebecca
full_name: Hoyle, Rebecca
last_name: Hoyle
citation:
ama: Prizak R, Ezard T, Hoyle R. Fitness consequences of maternal and grandmaternal
effects. Ecology and Evolution. 2014;4(15):3139-3145. doi:10.1002/ece3.1150
apa: Prizak, R., Ezard, T., & Hoyle, R. (2014). Fitness consequences of maternal
and grandmaternal effects. Ecology and Evolution. Wiley-Blackwell. https://doi.org/10.1002/ece3.1150
chicago: Prizak, Roshan, Thomas Ezard, and Rebecca Hoyle. “Fitness Consequences
of Maternal and Grandmaternal Effects.” Ecology and Evolution. Wiley-Blackwell,
2014. https://doi.org/10.1002/ece3.1150.
ieee: R. Prizak, T. Ezard, and R. Hoyle, “Fitness consequences of maternal and grandmaternal
effects,” Ecology and Evolution, vol. 4, no. 15. Wiley-Blackwell, pp. 3139–3145,
2014.
ista: Prizak R, Ezard T, Hoyle R. 2014. Fitness consequences of maternal and grandmaternal
effects. Ecology and Evolution. 4(15), 3139–3145.
mla: Prizak, Roshan, et al. “Fitness Consequences of Maternal and Grandmaternal
Effects.” Ecology and Evolution, vol. 4, no. 15, Wiley-Blackwell, 2014,
pp. 3139–45, doi:10.1002/ece3.1150.
short: R. Prizak, T. Ezard, R. Hoyle, Ecology and Evolution 4 (2014) 3139–3145.
date_created: 2018-12-11T11:47:02Z
date_published: 2014-07-19T00:00:00Z
date_updated: 2021-01-12T08:01:30Z
day: '19'
ddc:
- '530'
- '571'
department:
- _id: NiBa
- _id: GaTk
doi: 10.1002/ece3.1150
file:
- access_level: open_access
checksum: e32abf75a248e7a11811fd7f60858769
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:11:31Z
date_updated: 2020-07-14T12:46:38Z
file_id: '4886'
file_name: IST-2018-934-v1+1_Prizak_et_al-2014-Ecology_and_Evolution.pdf
file_size: 621582
relation: main_file
file_date_updated: 2020-07-14T12:46:38Z
has_accepted_license: '1'
intvolume: ' 4'
issue: '15'
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
page: 3139 - 3145
publication: Ecology and Evolution
publication_status: published
publisher: Wiley-Blackwell
publist_id: '7280'
pubrep_id: '934'
scopus_import: 1
status: public
title: Fitness consequences of maternal and grandmaternal effects
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: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 4
year: '2014'
...
---
_id: '827'
abstract:
- lang: eng
text: As sessile organisms, plants have to be able to adapt to a continuously changing
environment. Plants that perceive some of these changes as stress signals activate
signaling pathways to modulate their development and to enable them to survive.
The complex responses to environmental cues are to a large extent mediated by
plant hormones that together orchestrate the final plant response. The phytohormone
cytokinin is involved in many plant developmental processes. Recently, it has
been established that cytokinin plays an important role in stress responses, but
does not act alone. Indeed, the hormonal control of plant development and stress
adaptation is the outcome of a complex network of multiple synergistic and antagonistic
interactions between various hormones. Here, we review the recent findings on
the cytokinin function as part of this hormonal network. We focus on the importance
of the crosstalk between cytokinin and other hormones, such as abscisic acid,
jasmonate, salicylic acid, ethylene, and auxin in the modulation of plant development
and stress adaptation. Finally, the impact of the current research in the biotechnological
industry will be discussed.
article_number: '451'
author:
- first_name: José
full_name: O'Brien, José
last_name: O'Brien
- first_name: Eva
full_name: Benková, Eva
id: 38F4F166-F248-11E8-B48F-1D18A9856A87
last_name: Benková
orcid: 0000-0002-8510-9739
citation:
ama: O’Brien J, Benková E. Cytokinin cross talking during biotic and abiotic stress
responses. Frontiers in Plant Science. 2013;4. doi:10.3389/fpls.2013.00451
apa: O’Brien, J., & Benková, E. (2013). Cytokinin cross talking during biotic
and abiotic stress responses. Frontiers in Plant Science. Frontiers Research
Foundation. https://doi.org/10.3389/fpls.2013.00451
chicago: O’Brien, José, and Eva Benková. “Cytokinin Cross Talking during Biotic
and Abiotic Stress Responses.” Frontiers in Plant Science. Frontiers Research
Foundation, 2013. https://doi.org/10.3389/fpls.2013.00451.
ieee: J. O’Brien and E. Benková, “Cytokinin cross talking during biotic and abiotic
stress responses,” Frontiers in Plant Science, vol. 4. Frontiers Research
Foundation, 2013.
ista: O’Brien J, Benková E. 2013. Cytokinin cross talking during biotic and abiotic
stress responses. Frontiers in Plant Science. 4, 451.
mla: O’Brien, José, and Eva Benková. “Cytokinin Cross Talking during Biotic and
Abiotic Stress Responses.” Frontiers in Plant Science, vol. 4, 451, Frontiers
Research Foundation, 2013, doi:10.3389/fpls.2013.00451.
short: J. O’Brien, E. Benková, Frontiers in Plant Science 4 (2013).
date_created: 2018-12-11T11:48:43Z
date_published: 2013-11-19T00:00:00Z
date_updated: 2021-01-12T08:17:50Z
day: '19'
ddc:
- '580'
department:
- _id: EvBe
doi: 10.3389/fpls.2013.00451
ec_funded: 1
file:
- access_level: open_access
checksum: fdc25ddd1bf9a99b99f662cdbafeddd4
content_type: application/pdf
creator: dernst
date_created: 2019-01-31T10:40:38Z
date_updated: 2020-07-14T12:48:11Z
file_id: '5903'
file_name: 2013_FrontiersPlant_OBrien.pdf
file_size: 953299
relation: main_file
file_date_updated: 2020-07-14T12:48:11Z
has_accepted_license: '1'
intvolume: ' 4'
language:
- iso: eng
month: '11'
oa: 1
oa_version: Published Version
project:
- _id: 253FCA6A-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '207362'
name: Hormonal cross-talk in plant organogenesis
publication: Frontiers in Plant Science
publication_status: published
publisher: Frontiers Research Foundation
publist_id: '6821'
quality_controlled: '1'
scopus_import: 1
status: public
title: Cytokinin cross talking during biotic and abiotic stress responses
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: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 4
year: '2013'
...
---
_id: '828'
abstract:
- lang: eng
text: The plant root system is essential for providing anchorage to the soil, supplying
minerals and water, and synthesizing metabolites. It is a dynamic organ modulated
by external cues such as environmental signals, water and nutrients availability,
salinity and others. Lateral roots (LRs) are initiated from the primary root post-embryonically,
after which they progress through discrete developmental stages which can be independently
controlled, providing a high level of plasticity during root system formation.
Within this review, main contributions are presented, from the classical forward
genetic screens to the more recent high-throughput approaches, combined with computer
model predictions, dissecting how LRs and thereby root system architecture is
established and developed.
article_number: '537'
author:
- first_name: Candela
full_name: Cuesta, Candela
id: 33A3C818-F248-11E8-B48F-1D18A9856A87
last_name: Cuesta
orcid: 0000-0003-1923-2410
- first_name: Krzysztof T
full_name: Wabnik, Krzysztof T
id: 4DE369A4-F248-11E8-B48F-1D18A9856A87
last_name: Wabnik
orcid: 0000-0001-7263-0560
- first_name: Eva
full_name: Benková, Eva
id: 38F4F166-F248-11E8-B48F-1D18A9856A87
last_name: Benková
orcid: 0000-0002-8510-9739
citation:
ama: Cuesta C, Wabnik KT, Benková E. Systems approaches to study root architecture
dynamics. Frontiers in Plant Science. 2013;4. doi:10.3389/fpls.2013.00537
apa: Cuesta, C., Wabnik, K. T., & Benková, E. (2013). Systems approaches to
study root architecture dynamics. Frontiers in Plant Science. Frontiers
Research Foundation. https://doi.org/10.3389/fpls.2013.00537
chicago: Cuesta, Candela, Krzysztof T Wabnik, and Eva Benková. “Systems Approaches
to Study Root Architecture Dynamics.” Frontiers in Plant Science. Frontiers
Research Foundation, 2013. https://doi.org/10.3389/fpls.2013.00537.
ieee: C. Cuesta, K. T. Wabnik, and E. Benková, “Systems approaches to study root
architecture dynamics,” Frontiers in Plant Science, vol. 4. Frontiers Research
Foundation, 2013.
ista: Cuesta C, Wabnik KT, Benková E. 2013. Systems approaches to study root architecture
dynamics. Frontiers in Plant Science. 4, 537.
mla: Cuesta, Candela, et al. “Systems Approaches to Study Root Architecture Dynamics.”
Frontiers in Plant Science, vol. 4, 537, Frontiers Research Foundation,
2013, doi:10.3389/fpls.2013.00537.
short: C. Cuesta, K.T. Wabnik, E. Benková, Frontiers in Plant Science 4 (2013).
date_created: 2018-12-11T11:48:43Z
date_published: 2013-12-26T00:00:00Z
date_updated: 2021-01-12T08:17:52Z
day: '26'
ddc:
- '580'
department:
- _id: EvBe
doi: 10.3389/fpls.2013.00537
ec_funded: 1
file:
- access_level: open_access
checksum: 0185b3c4d7df9a94bd3ce5a66d213506
content_type: application/pdf
creator: dernst
date_created: 2019-01-31T10:36:43Z
date_updated: 2020-07-14T12:48:11Z
file_id: '5902'
file_name: 2013_FrontiersPlant_Cuesta.pdf
file_size: 710835
relation: main_file
file_date_updated: 2020-07-14T12:48:11Z
has_accepted_license: '1'
intvolume: ' 4'
language:
- iso: eng
month: '12'
oa: 1
oa_version: Published Version
project:
- _id: 253FCA6A-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '207362'
name: Hormonal cross-talk in plant organogenesis
publication: Frontiers in Plant Science
publication_status: published
publisher: Frontiers Research Foundation
publist_id: '6820'
quality_controlled: '1'
scopus_import: 1
status: public
title: Systems approaches to study root architecture dynamics
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: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 4
year: '2013'
...
---
_id: '2000'
abstract:
- lang: eng
text: In this work we present a flexible tool for tumor progression, which simulates
the evolutionary dynamics of cancer. Tumor progression implements a multi-type
branching process where the key parameters are the fitness landscape, the mutation
rate, and the average time of cell division. The fitness of a cancer cell depends
on the mutations it has accumulated. The input to our tool could be any fitness
landscape, mutation rate, and cell division time, and the tool produces the growth
dynamics and all relevant statistics.
alternative_title:
- LNCS
arxiv: 1
author:
- first_name: Johannes
full_name: Reiter, Johannes
id: 4A918E98-F248-11E8-B48F-1D18A9856A87
last_name: Reiter
orcid: 0000-0002-0170-7353
- first_name: Ivana
full_name: Božić, Ivana
last_name: Božić
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Martin
full_name: Nowak, Martin
last_name: Nowak
citation:
ama: 'Reiter J, Božić I, Chatterjee K, Nowak M. TTP: Tool for tumor progression.
In: Proceedings of 25th Int. Conf. on Computer Aided Verification. Vol
8044. Lecture Notes in Computer Science. Springer; 2013:101-106. doi:10.1007/978-3-642-39799-8_6'
apa: 'Reiter, J., Božić, I., Chatterjee, K., & Nowak, M. (2013). TTP: Tool for
tumor progression. In Proceedings of 25th Int. Conf. on Computer Aided Verification
(Vol. 8044, pp. 101–106). St. Petersburg, Russia: Springer. https://doi.org/10.1007/978-3-642-39799-8_6'
chicago: 'Reiter, Johannes, Ivana Božić, Krishnendu Chatterjee, and Martin Nowak.
“TTP: Tool for Tumor Progression.” In Proceedings of 25th Int. Conf. on Computer
Aided Verification, 8044:101–6. Lecture Notes in Computer Science. Springer,
2013. https://doi.org/10.1007/978-3-642-39799-8_6.'
ieee: 'J. Reiter, I. Božić, K. Chatterjee, and M. Nowak, “TTP: Tool for tumor progression,”
in Proceedings of 25th Int. Conf. on Computer Aided Verification, St. Petersburg,
Russia, 2013, vol. 8044, pp. 101–106.'
ista: 'Reiter J, Božić I, Chatterjee K, Nowak M. 2013. TTP: Tool for tumor progression.
Proceedings of 25th Int. Conf. on Computer Aided Verification. CAV: Computer Aided
VerificationLecture Notes in Computer Science, LNCS, vol. 8044, 101–106.'
mla: 'Reiter, Johannes, et al. “TTP: Tool for Tumor Progression.” Proceedings
of 25th Int. Conf. on Computer Aided Verification, vol. 8044, Springer, 2013,
pp. 101–06, doi:10.1007/978-3-642-39799-8_6.'
short: J. Reiter, I. Božić, K. Chatterjee, M. Nowak, in:, Proceedings of 25th Int.
Conf. on Computer Aided Verification, Springer, 2013, pp. 101–106.
conference:
end_date: 2013-07-19
location: St. Petersburg, Russia
name: 'CAV: Computer Aided Verification'
start_date: 2013-07-13
date_created: 2018-12-11T11:55:08Z
date_published: 2013-01-01T00:00:00Z
date_updated: 2023-09-07T11:40:43Z
day: '01'
department:
- _id: KrCh
doi: 10.1007/978-3-642-39799-8_6
ec_funded: 1
external_id:
arxiv:
- '1303.5251'
intvolume: ' 8044'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1303.5251
month: '01'
oa: 1
oa_version: Preprint
page: 101 - 106
project:
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '279307'
name: 'Quantitative Graph Games: Theory and Applications'
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
- _id: 2584A770-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: P 23499-N23
name: Modern Graph Algorithmic Techniques in Formal Verification
- _id: 2587B514-B435-11E9-9278-68D0E5697425
name: Microsoft Research Faculty Fellowship
publication: Proceedings of 25th Int. Conf. on Computer Aided Verification
publication_status: published
publisher: Springer
publist_id: '5077'
quality_controlled: '1'
related_material:
record:
- id: '5399'
relation: earlier_version
status: public
- id: '1400'
relation: dissertation_contains
status: public
scopus_import: 1
series_title: Lecture Notes in Computer Science
status: public
title: 'TTP: Tool for tumor progression'
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 8044
year: '2013'
...
---
_id: '2009'
abstract:
- lang: eng
text: Traditional statistical methods for confidentiality protection of statistical
databases do not scale well to deal with GWAS databases especially in terms of
guarantees regarding protection from linkage to external information. The more
recent concept of differential privacy, introduced by the cryptographic community,
is an approach which provides a rigorous definition of privacy with meaningful
privacy guarantees in the presence of arbitrary external information, although
the guarantees may come at a serious price in terms of data utility. Building
on such notions, we propose new methods to release aggregate GWAS data without
compromising an individual’s privacy. We present methods for releasing differentially
private minor allele frequencies, chi-square statistics and p-values. We compare
these approaches on simulated data and on a GWAS study of canine hair length involving
685 dogs. We also propose a privacy-preserving method for finding genome-wide
associations based on a differentially-private approach to penalized logistic
regression.
article_processing_charge: No
author:
- first_name: Caroline
full_name: Uhler, Caroline
id: 49ADD78E-F248-11E8-B48F-1D18A9856A87
last_name: Uhler
orcid: 0000-0002-7008-0216
- first_name: Aleksandra
full_name: Slavkovic, Aleksandra
last_name: Slavkovic
- first_name: Stephen
full_name: Fienberg, Stephen
last_name: Fienberg
citation:
ama: Uhler C, Slavkovic A, Fienberg S. Privacy-preserving data sharing for genome-wide
association studies. Journal of Privacy and Confidentiality . 2013;5(1):137-166.
doi:10.29012/jpc.v5i1.629
apa: Uhler, C., Slavkovic, A., & Fienberg, S. (2013). Privacy-preserving data
sharing for genome-wide association studies. Journal of Privacy and Confidentiality
. Carnegie Mellon University. https://doi.org/10.29012/jpc.v5i1.629
chicago: Uhler, Caroline, Aleksandra Slavkovic, and Stephen Fienberg. “Privacy-Preserving
Data Sharing for Genome-Wide Association Studies.” Journal of Privacy and Confidentiality
. Carnegie Mellon University, 2013. https://doi.org/10.29012/jpc.v5i1.629.
ieee: C. Uhler, A. Slavkovic, and S. Fienberg, “Privacy-preserving data sharing
for genome-wide association studies,” Journal of Privacy and Confidentiality
, vol. 5, no. 1. Carnegie Mellon University, pp. 137–166, 2013.
ista: Uhler C, Slavkovic A, Fienberg S. 2013. Privacy-preserving data sharing for
genome-wide association studies. Journal of Privacy and Confidentiality . 5(1),
137–166.
mla: Uhler, Caroline, et al. “Privacy-Preserving Data Sharing for Genome-Wide Association
Studies.” Journal of Privacy and Confidentiality , vol. 5, no. 1, Carnegie
Mellon University, 2013, pp. 137–66, doi:10.29012/jpc.v5i1.629.
short: C. Uhler, A. Slavkovic, S. Fienberg, Journal of Privacy and Confidentiality 5
(2013) 137–166.
date_created: 2018-12-11T11:55:11Z
date_published: 2013-08-01T00:00:00Z
date_updated: 2021-01-12T06:54:41Z
day: '01'
department:
- _id: CaUh
doi: 10.29012/jpc.v5i1.629
intvolume: ' 5'
issue: '1'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://repository.cmu.edu/jpc/vol5/iss1/6
month: '08'
oa: 1
oa_version: Published Version
page: 137 - 166
publication: 'Journal of Privacy and Confidentiality '
publication_status: published
publisher: Carnegie Mellon University
publist_id: '5067'
quality_controlled: '1'
status: public
title: Privacy-preserving data sharing for genome-wide association studies
type: journal_article
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 5
year: '2013'
...
---
_id: '2010'
abstract:
- lang: eng
text: Many algorithms for inferring causality rely heavily on the faithfulness assumption.
The main justification for imposing this assumption is that the set of unfaithful
distributions has Lebesgue measure zero, since it can be seen as a collection
of hypersurfaces in a hypercube. However, due to sampling error the faithfulness
condition alone is not sufficient for statistical estimation, and strong-faithfulness
has been proposed and assumed to achieve uniform or high-dimensional consistency.
In contrast to the plain faithfulness assumption, the set of distributions that
is not strong-faithful has nonzero Lebesgue measure and in fact, can be surprisingly
large as we show in this paper. We study the strong-faithfulness condition from
a geometric and combinatorial point of view and give upper and lower bounds on
the Lebesgue measure of strong-faithful distributions for various classes of directed
acyclic graphs. Our results imply fundamental limitations for the PC-algorithm
and potentially also for other algorithms based on partial correlation testing
in the Gaussian case.
arxiv: 1
author:
- first_name: Caroline
full_name: Uhler, Caroline
id: 49ADD78E-F248-11E8-B48F-1D18A9856A87
last_name: Uhler
orcid: 0000-0002-7008-0216
- first_name: Garvesh
full_name: Raskutti, Garvesh
last_name: Raskutti
- first_name: Peter
full_name: Bühlmann, Peter
last_name: Bühlmann
- first_name: Bin
full_name: Yu, Bin
last_name: Yu
citation:
ama: Uhler C, Raskutti G, Bühlmann P, Yu B. Geometry of the faithfulness assumption
in causal inference. The Annals of Statistics. 2013;41(2):436-463. doi:10.1214/12-AOS1080
apa: Uhler, C., Raskutti, G., Bühlmann, P., & Yu, B. (2013). Geometry of the
faithfulness assumption in causal inference. The Annals of Statistics.
Institute of Mathematical Statistics. https://doi.org/10.1214/12-AOS1080
chicago: Uhler, Caroline, Garvesh Raskutti, Peter Bühlmann, and Bin Yu. “Geometry
of the Faithfulness Assumption in Causal Inference.” The Annals of Statistics.
Institute of Mathematical Statistics, 2013. https://doi.org/10.1214/12-AOS1080.
ieee: C. Uhler, G. Raskutti, P. Bühlmann, and B. Yu, “Geometry of the faithfulness
assumption in causal inference,” The Annals of Statistics, vol. 41, no.
2. Institute of Mathematical Statistics, pp. 436–463, 2013.
ista: Uhler C, Raskutti G, Bühlmann P, Yu B. 2013. Geometry of the faithfulness
assumption in causal inference. The Annals of Statistics. 41(2), 436–463.
mla: Uhler, Caroline, et al. “Geometry of the Faithfulness Assumption in Causal
Inference.” The Annals of Statistics, vol. 41, no. 2, Institute of Mathematical
Statistics, 2013, pp. 436–63, doi:10.1214/12-AOS1080.
short: C. Uhler, G. Raskutti, P. Bühlmann, B. Yu, The Annals of Statistics 41 (2013)
436–463.
date_created: 2018-12-11T11:55:11Z
date_published: 2013-04-01T00:00:00Z
date_updated: 2021-01-12T06:54:42Z
day: '01'
department:
- _id: CaUh
doi: 10.1214/12-AOS1080
external_id:
arxiv:
- '1207.0547'
intvolume: ' 41'
issue: '2'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: www.doi.org/10.1214/12-AOS1080
month: '04'
oa: 1
oa_version: Published Version
page: 436 - 463
publication: The Annals of Statistics
publication_status: published
publisher: Institute of Mathematical Statistics
publist_id: '5066'
quality_controlled: '1'
scopus_import: 1
status: public
title: Geometry of the faithfulness assumption in causal inference
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 41
year: '2013'
...
---
_id: '1374'
abstract:
- lang: eng
text: 'We study two-player zero-sum games over infinite-state graphs equipped with
ωB and finitary conditions. Our first contribution is about the strategy complexity,
i.e the memory required for winning strategies: we prove that over general infinite-state
graphs, memoryless strategies are sufficient for finitary Büchi, and finite-memory
suffices for finitary parity games. We then study pushdown games with boundedness
conditions, with two contributions. First we prove a collapse result for pushdown
games with ωB-conditions, implying the decidability of solving these games. Second
we consider pushdown games with finitary parity along with stack boundedness conditions,
and show that solving these games is EXPTIME-complete.'
alternative_title:
- LIPIcs
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Nathanaël
full_name: Fijalkow, Nathanaël
last_name: Fijalkow
citation:
ama: 'Chatterjee K, Fijalkow N. Infinite-state games with finitary conditions. In:
22nd EACSL Annual Conference on Computer Science Logic. Vol 23. Leibniz
International Proceedings in Informatics. Schloss Dagstuhl - Leibniz-Zentrum für
Informatik; 2013:181-196. doi:10.4230/LIPIcs.CSL.2013.181'
apa: 'Chatterjee, K., & Fijalkow, N. (2013). Infinite-state games with finitary
conditions. In 22nd EACSL Annual Conference on Computer Science Logic (Vol.
23, pp. 181–196). Torino, Italy: Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
https://doi.org/10.4230/LIPIcs.CSL.2013.181'
chicago: Chatterjee, Krishnendu, and Nathanaël Fijalkow. “Infinite-State Games with
Finitary Conditions.” In 22nd EACSL Annual Conference on Computer Science Logic,
23:181–96. Leibniz International Proceedings in Informatics. Schloss Dagstuhl
- Leibniz-Zentrum für Informatik, 2013. https://doi.org/10.4230/LIPIcs.CSL.2013.181.
ieee: K. Chatterjee and N. Fijalkow, “Infinite-state games with finitary conditions,”
in 22nd EACSL Annual Conference on Computer Science Logic, Torino, Italy,
2013, vol. 23, pp. 181–196.
ista: 'Chatterjee K, Fijalkow N. 2013. Infinite-state games with finitary conditions.
22nd EACSL Annual Conference on Computer Science Logic. CSL: Computer Science
LogicLeibniz International Proceedings in Informatics, LIPIcs, vol. 23, 181–196.'
mla: Chatterjee, Krishnendu, and Nathanaël Fijalkow. “Infinite-State Games with
Finitary Conditions.” 22nd EACSL Annual Conference on Computer Science Logic,
vol. 23, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2013, pp. 181–96,
doi:10.4230/LIPIcs.CSL.2013.181.
short: K. Chatterjee, N. Fijalkow, in:, 22nd EACSL Annual Conference on Computer
Science Logic, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2013, pp. 181–196.
conference:
end_date: 2013-09-05
location: Torino, Italy
name: 'CSL: Computer Science Logic'
start_date: 203-09-02
date_created: 2018-12-11T11:51:39Z
date_published: 2013-09-01T00:00:00Z
date_updated: 2021-01-12T06:50:14Z
day: '01'
ddc:
- '000'
department:
- _id: KrCh
doi: 10.4230/LIPIcs.CSL.2013.181
ec_funded: 1
file:
- access_level: open_access
checksum: b7091a3866db573c0db5ec486952255e
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:13:38Z
date_updated: 2020-07-14T12:44:47Z
file_id: '5023'
file_name: IST-2016-624-v1+1_ChKr_Infinite-state_games_2013_17.pdf
file_size: 547296
relation: main_file
file_date_updated: 2020-07-14T12:44:47Z
has_accepted_license: '1'
intvolume: ' 23'
language:
- iso: eng
month: '09'
oa: 1
oa_version: Published Version
page: 181 - 196
project:
- _id: 2584A770-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: P 23499-N23
name: Modern Graph Algorithmic Techniques in Formal Verification
- _id: 25863FF4-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S11407
name: Game Theory
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '279307'
name: 'Quantitative Graph Games: Theory and Applications'
- _id: 2587B514-B435-11E9-9278-68D0E5697425
name: Microsoft Research Faculty Fellowship
publication: 22nd EACSL Annual Conference on Computer Science Logic
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
publist_id: '5837'
pubrep_id: '624'
quality_controlled: '1'
scopus_import: 1
series_title: Leibniz International Proceedings in Informatics
status: public
title: Infinite-state games with finitary conditions
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: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 23
year: '2013'
...
---
_id: '1376'
abstract:
- lang: eng
text: 'We consider the distributed synthesis problem for temporal logic specifications.
Traditionally, the problem has been studied for LTL, and the previous results
show that the problem is decidable iff there is no information fork in the architecture.
We consider the problem for fragments of LTL and our main results are as follows:
(1) We show that the problem is undecidable for architectures with information
forks even for the fragment of LTL with temporal operators restricted to next
and eventually. (2) For specifications restricted to globally along with non-nested
next operators, we establish decidability (in EXPSPACE) for star architectures
where the processes receive disjoint inputs, whereas we establish undecidability
for architectures containing an information fork-meet structure. (3) Finally,
we consider LTL without the next operator, and establish decidability (NEXPTIME-complete)
for all architectures for a fragment that consists of a set of safety assumptions,
and a set of guarantees where each guarantee is a safety, reachability, or liveness
condition.'
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: Jan
full_name: Otop, Jan
id: 2FC5DA74-F248-11E8-B48F-1D18A9856A87
last_name: Otop
- first_name: Andreas
full_name: Pavlogiannis, Andreas
id: 49704004-F248-11E8-B48F-1D18A9856A87
last_name: Pavlogiannis
orcid: 0000-0002-8943-0722
citation:
ama: 'Chatterjee K, Henzinger TA, Otop J, Pavlogiannis A. Distributed synthesis
for LTL fragments. In: 13th International Conference on Formal Methods in Computer-Aided
Design. IEEE; 2013:18-25. doi:10.1109/FMCAD.2013.6679386'
apa: 'Chatterjee, K., Henzinger, T. A., Otop, J., & Pavlogiannis, A. (2013).
Distributed synthesis for LTL fragments. In 13th International Conference on
Formal Methods in Computer-Aided Design (pp. 18–25). Portland, OR, United
States: IEEE. https://doi.org/10.1109/FMCAD.2013.6679386'
chicago: Chatterjee, Krishnendu, Thomas A Henzinger, Jan Otop, and Andreas Pavlogiannis.
“Distributed Synthesis for LTL Fragments.” In 13th International Conference
on Formal Methods in Computer-Aided Design, 18–25. IEEE, 2013. https://doi.org/10.1109/FMCAD.2013.6679386.
ieee: K. Chatterjee, T. A. Henzinger, J. Otop, and A. Pavlogiannis, “Distributed
synthesis for LTL fragments,” in 13th International Conference on Formal Methods
in Computer-Aided Design, Portland, OR, United States, 2013, pp. 18–25.
ista: 'Chatterjee K, Henzinger TA, Otop J, Pavlogiannis A. 2013. Distributed synthesis
for LTL fragments. 13th International Conference on Formal Methods in Computer-Aided
Design. FMCAD: Formal Methods in Computer-Aided Design, 18–25.'
mla: Chatterjee, Krishnendu, et al. “Distributed Synthesis for LTL Fragments.” 13th
International Conference on Formal Methods in Computer-Aided Design, IEEE,
2013, pp. 18–25, doi:10.1109/FMCAD.2013.6679386.
short: K. Chatterjee, T.A. Henzinger, J. Otop, A. Pavlogiannis, in:, 13th International
Conference on Formal Methods in Computer-Aided Design, IEEE, 2013, pp. 18–25.
conference:
end_date: 2013-10-23
location: Portland, OR, United States
name: 'FMCAD: Formal Methods in Computer-Aided Design'
start_date: 2013-10-20
date_created: 2018-12-11T11:51:40Z
date_published: 2013-12-11T00:00:00Z
date_updated: 2023-02-23T12:24:53Z
day: '11'
department:
- _id: KrCh
- _id: ToHe
doi: 10.1109/FMCAD.2013.6679386
ec_funded: 1
language:
- iso: eng
month: '12'
oa_version: None
page: 18 - 25
project:
- _id: 2584A770-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: P 23499-N23
name: Modern Graph Algorithmic Techniques in Formal Verification
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '279307'
name: 'Quantitative Graph Games: Theory and Applications'
- _id: 25EE3708-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '267989'
name: Quantitative Reactive Modeling
- _id: 2587B514-B435-11E9-9278-68D0E5697425
name: Microsoft Research Faculty Fellowship
publication: 13th International Conference on Formal Methods in Computer-Aided Design
publication_status: published
publisher: IEEE
publist_id: '5835'
quality_controlled: '1'
related_material:
record:
- id: '5406'
relation: earlier_version
status: public
status: public
title: Distributed synthesis for LTL fragments
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2013'
...
---
_id: '1385'
abstract:
- lang: eng
text: It is often difficult to correctly implement a Boolean controller for a complex
system, especially when concurrency is involved. Yet, it may be easy to formally
specify a controller. For instance, for a pipelined processor it suffices to state
that the visible behavior of the pipelined system should be identical to a non-pipelined
reference system (Burch-Dill paradigm). We present a novel procedure to efficiently
synthesize multiple Boolean control signals from a specification given as a quantified
first-order formula (with a specific quantifier structure). Our approach uses
uninterpreted functions to abstract details of the design. We construct an unsatisfiable
SMT formula from the given specification. Then, from just one proof of unsatisfiability,
we use a variant of Craig interpolation to compute multiple coordinated interpolants
that implement the Boolean control signals. Our method avoids iterative learning
and back-substitution of the control functions. We applied our approach to synthesize
a controller for a simple two-stage pipelined processor, and present first experimental
results.
acknowledgement: "This research was supported by the European Commission through project\r\nDIAMOND
\ (FP7-2009-IST-4-248613), and QUAINT (I774-N23), "
arxiv: 1
author:
- first_name: Georg
full_name: Hofferek, Georg
last_name: Hofferek
- first_name: Ashutosh
full_name: Gupta, Ashutosh
id: 335E5684-F248-11E8-B48F-1D18A9856A87
last_name: Gupta
- first_name: Bettina
full_name: Könighofer, Bettina
last_name: Könighofer
- first_name: Jie
full_name: Jiang, Jie
last_name: Jiang
- first_name: Roderick
full_name: Bloem, Roderick
last_name: Bloem
citation:
ama: 'Hofferek G, Gupta A, Könighofer B, Jiang J, Bloem R. Synthesizing multiple
boolean functions using interpolation on a single proof. In: 2013 Formal Methods
in Computer-Aided Design. IEEE; 2013:77-84. doi:10.1109/FMCAD.2013.6679394'
apa: 'Hofferek, G., Gupta, A., Könighofer, B., Jiang, J., & Bloem, R. (2013).
Synthesizing multiple boolean functions using interpolation on a single proof.
In 2013 Formal Methods in Computer-Aided Design (pp. 77–84). Portland,
OR, United States: IEEE. https://doi.org/10.1109/FMCAD.2013.6679394'
chicago: Hofferek, Georg, Ashutosh Gupta, Bettina Könighofer, Jie Jiang, and Roderick
Bloem. “Synthesizing Multiple Boolean Functions Using Interpolation on a Single
Proof.” In 2013 Formal Methods in Computer-Aided Design, 77–84. IEEE, 2013.
https://doi.org/10.1109/FMCAD.2013.6679394.
ieee: G. Hofferek, A. Gupta, B. Könighofer, J. Jiang, and R. Bloem, “Synthesizing
multiple boolean functions using interpolation on a single proof,” in 2013
Formal Methods in Computer-Aided Design, Portland, OR, United States, 2013,
pp. 77–84.
ista: 'Hofferek G, Gupta A, Könighofer B, Jiang J, Bloem R. 2013. Synthesizing multiple
boolean functions using interpolation on a single proof. 2013 Formal Methods in
Computer-Aided Design. FMCAD: Formal Methods in Computer-Aided Design, 77–84.'
mla: Hofferek, Georg, et al. “Synthesizing Multiple Boolean Functions Using Interpolation
on a Single Proof.” 2013 Formal Methods in Computer-Aided Design, IEEE,
2013, pp. 77–84, doi:10.1109/FMCAD.2013.6679394.
short: G. Hofferek, A. Gupta, B. Könighofer, J. Jiang, R. Bloem, in:, 2013 Formal
Methods in Computer-Aided Design, IEEE, 2013, pp. 77–84.
conference:
end_date: 2013-10-23
location: Portland, OR, United States
name: 'FMCAD: Formal Methods in Computer-Aided Design'
start_date: 2013-10-20
date_created: 2018-12-11T11:51:43Z
date_published: 2013-12-11T00:00:00Z
date_updated: 2021-01-12T06:50:19Z
day: '11'
department:
- _id: ToHe
doi: 10.1109/FMCAD.2013.6679394
ec_funded: 1
external_id:
arxiv:
- '1308.4767'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1308.4767
month: '12'
oa: 1
oa_version: Preprint
page: 77 - 84
project:
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
- _id: 25EE3708-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '267989'
name: Quantitative Reactive Modeling
publication: 2013 Formal Methods in Computer-Aided Design
publication_status: published
publisher: IEEE
publist_id: '5825'
quality_controlled: '1'
status: public
title: Synthesizing multiple boolean functions using interpolation on a single proof
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2013'
...
---
_id: '1387'
abstract:
- lang: eng
text: Choices made by nondeterministic word automata depend on both the past (the
prefix of the word read so far) and the future (the suffix yet to be read). In
several applications, most notably synthesis, the future is diverse or unknown,
leading to algorithms that are based on deterministic automata. Hoping to retain
some of the advantages of nondeterministic automata, researchers have studied
restricted classes of nondeterministic automata. Three such classes are nondeterministic
automata that are good for trees (GFT; i.e., ones that can be expanded to tree
automata accepting the derived tree languages, thus whose choices should satisfy
diverse futures), good for games (GFG; i.e., ones whose choices depend only on
the past), and determinizable by pruning (DBP; i.e., ones that embody equivalent
deterministic automata). The theoretical properties and relative merits of the
different classes are still open, having vagueness on whether they really differ
from deterministic automata. In particular, while DBP ⊆ GFG ⊆ GFT, it is not known
whether every GFT automaton is GFG and whether every GFG automaton is DBP. Also
open is the possible succinctness of GFG and GFT automata compared to deterministic
automata. We study these problems for ω-regular automata with all common acceptance
conditions. We show that GFT=GFG⊃DBP, and describe a determinization construction
for GFG automata.
acknowledgement: and ERC Grant QUALITY.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Udi
full_name: Boker, Udi
id: 31E297B6-F248-11E8-B48F-1D18A9856A87
last_name: Boker
- first_name: Denis
full_name: Kuperberg, Denis
last_name: Kuperberg
- first_name: Orna
full_name: Kupferman, Orna
last_name: Kupferman
- first_name: Michał
full_name: Skrzypczak, Michał
last_name: Skrzypczak
citation:
ama: Boker U, Kuperberg D, Kupferman O, Skrzypczak M. Nondeterminism in the presence
of a diverse or unknown future. 2013;7966(PART 2):89-100. doi:10.1007/978-3-642-39212-2_11
apa: 'Boker, U., Kuperberg, D., Kupferman, O., & Skrzypczak, M. (2013). Nondeterminism
in the presence of a diverse or unknown future. Presented at the ICALP: Automata,
Languages and Programming, Riga, Latvia: Springer. https://doi.org/10.1007/978-3-642-39212-2_11'
chicago: Boker, Udi, Denis Kuperberg, Orna Kupferman, and Michał Skrzypczak. “Nondeterminism
in the Presence of a Diverse or Unknown Future.” Lecture Notes in Computer Science.
Springer, 2013. https://doi.org/10.1007/978-3-642-39212-2_11.
ieee: U. Boker, D. Kuperberg, O. Kupferman, and M. Skrzypczak, “Nondeterminism in
the presence of a diverse or unknown future,” vol. 7966, no. PART 2. Springer,
pp. 89–100, 2013.
ista: Boker U, Kuperberg D, Kupferman O, Skrzypczak M. 2013. Nondeterminism in the
presence of a diverse or unknown future. 7966(PART 2), 89–100.
mla: Boker, Udi, et al. Nondeterminism in the Presence of a Diverse or Unknown
Future. Vol. 7966, no. PART 2, Springer, 2013, pp. 89–100, doi:10.1007/978-3-642-39212-2_11.
short: U. Boker, D. Kuperberg, O. Kupferman, M. Skrzypczak, 7966 (2013) 89–100.
conference:
end_date: 2013-07-12
location: Riga, Latvia
name: 'ICALP: Automata, Languages and Programming'
start_date: 2013-07-08
date_created: 2018-12-11T11:51:44Z
date_published: 2013-07-01T00:00:00Z
date_updated: 2020-08-11T10:09:09Z
day: '01'
ddc:
- '000'
department:
- _id: ToHe
doi: 10.1007/978-3-642-39212-2_11
ec_funded: 1
file:
- access_level: open_access
checksum: 98bc02e3793072e279ec8d364b381ff3
content_type: application/pdf
creator: dernst
date_created: 2020-05-15T11:05:50Z
date_updated: 2020-07-14T12:44:48Z
file_id: '7857'
file_name: 2013_ICALP_Boker.pdf
file_size: 276982
relation: main_file
file_date_updated: 2020-07-14T12:44:48Z
has_accepted_license: '1'
intvolume: ' 7966'
issue: PART 2
language:
- iso: eng
month: '07'
oa: 1
oa_version: Submitted Version
page: 89 - 100
project:
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
- _id: 25EE3708-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '267989'
name: Quantitative Reactive Modeling
publication_status: published
publisher: Springer
publist_id: '5823'
quality_controlled: '1'
scopus_import: 1
series_title: Lecture Notes in Computer Science
status: public
title: Nondeterminism in the presence of a diverse or unknown future
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 7966
year: '2013'
...
---
_id: '1405'
abstract:
- lang: eng
text: "Motivated by the analysis of highly dynamic message-passing systems, i.e.
unbounded thread creation, mobility, etc. we present a framework for the analysis
of depth-bounded systems. Depth-bounded systems are one of the most expressive
known fragment of the π-calculus for which interesting verification problems are
still decidable. Even though they are infinite state systems depth-bounded systems
are well-structured, thus can be analyzed algorithmically. We give an interpretation
of depth-bounded systems as graph-rewriting systems. This gives more flexibility
and ease of use to apply depth-bounded systems to other type of systems like shared
memory concurrency.\r\n\r\nFirst, we develop an adequate domain of limits for
depth-bounded systems, a prerequisite for the effective representation of downward-closed
sets. Downward-closed sets are needed by forward saturation-based algorithms to
represent potentially infinite sets of states. Then, we present an abstract interpretation
framework to compute the covering set of well-structured transition systems. Because,
in general, the covering set is not computable, our abstraction over-approximates
the actual covering set. Our abstraction captures the essence of acceleration
based-algorithms while giving up enough precision to ensure convergence. We have
implemented the analysis in the PICASSO tool and show that it is accurate in practice.
Finally, we build some further analyses like termination using the covering set
as starting point."
acknowledgement: "This work was supported in part by the Austrian Science Fund NFN
RiSE (Rigorous Systems Engineering) and by the ERC Advanced Grant QUAREM (Quantitative
Reactve Modeling).\r\nChapter 2, 3, and 4 are joint work with Thomas A. Henzinger
and Thomas Wies. Chapter 2 was published in FoSSaCS 2010 as “Forward Analysis of
Depth-Bounded Processes” [112]. Chapter 3 was published in VMCAI 2012 as “Ideal
Abstractions for Well-Structured Transition Systems” [114]. Chap- ter 5.1 is joint
work with Kshitij Bansal, Eric Koskinen, and Thomas Wies. It was published in TACAS
2013 as “Structural Counter Abstraction” [13]. The author’s contribution in this
part is mostly related to the implementation. The theory required to understand
the method and its implementation is quickly recalled to make the thesis self-contained,
but should not be considered as a contribution. For the details of the methods,
we refer the reader to the orig- inal publication [13] and the corresponding technical
report [14]. Chapter 5.2 is ongoing work with Shahram Esmaeilsabzali, Rupak Majumdar,
and Thomas Wies. I also would like to thank the people who supported over the past
4 years. My advisor Thomas A. Henzinger who gave me a lot of freedom to work on
projects I was interested in. My collaborators, especially Thomas Wies with whom
I worked since the beginning. The members of my thesis committee, Viktor Kun- cak
and Rupak Majumdar, who also agreed to advise me. Simon Aeschbacher, Pavol Cerny,
Cezara Dragoi, Arjun Radhakrishna, my family, friends and col- leagues who created
an enjoyable environment. "
alternative_title:
- ISTA Thesis
article_processing_charge: No
author:
- first_name: Damien
full_name: Zufferey, Damien
id: 4397AC76-F248-11E8-B48F-1D18A9856A87
last_name: Zufferey
orcid: 0000-0002-3197-8736
citation:
ama: Zufferey D. Analysis of dynamic message passing programs. 2013. doi:10.15479/at:ista:1405
apa: Zufferey, D. (2013). Analysis of dynamic message passing programs. Institute
of Science and Technology Austria. https://doi.org/10.15479/at:ista:1405
chicago: Zufferey, Damien. “Analysis of Dynamic Message Passing Programs.” Institute
of Science and Technology Austria, 2013. https://doi.org/10.15479/at:ista:1405.
ieee: D. Zufferey, “Analysis of dynamic message passing programs,” Institute of
Science and Technology Austria, 2013.
ista: Zufferey D. 2013. Analysis of dynamic message passing programs. Institute
of Science and Technology Austria.
mla: Zufferey, Damien. Analysis of Dynamic Message Passing Programs. Institute
of Science and Technology Austria, 2013, doi:10.15479/at:ista:1405.
short: D. Zufferey, Analysis of Dynamic Message Passing Programs, Institute of Science
and Technology Austria, 2013.
date_created: 2018-12-11T11:51:50Z
date_published: 2013-09-05T00:00:00Z
date_updated: 2023-09-07T11:36:37Z
day: '05'
ddc:
- '000'
degree_awarded: PhD
department:
- _id: ToHe
- _id: GradSch
doi: 10.15479/at:ista:1405
ec_funded: 1
file:
- access_level: open_access
checksum: ed2d7b52933d134e8dc69d569baa284e
content_type: application/pdf
creator: dernst
date_created: 2021-02-22T11:28:36Z
date_updated: 2021-02-22T11:28:36Z
file_id: '9176'
file_name: 2013_Zufferey_thesis_final.pdf
file_size: 1514906
relation: main_file
success: 1
- access_level: closed
checksum: cecc4c4b14225bee973d32e3dba91a55
content_type: application/pdf
creator: cchlebak
date_created: 2021-11-16T14:42:52Z
date_updated: 2021-11-17T13:47:58Z
file_id: '10298'
file_name: 2013_Zufferey_thesis_final_pdfa.pdf
file_size: 1378313
relation: main_file
file_date_updated: 2021-11-17T13:47:58Z
has_accepted_license: '1'
language:
- iso: eng
main_file_link:
- url: http://dzufferey.github.io/files/2013_thesis.pdf
month: '09'
oa: 1
oa_version: Published Version
page: '134'
project:
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
- _id: 25EE3708-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '267989'
name: Quantitative Reactive Modeling
publication_identifier:
issn:
- 2663-337X
publication_status: published
publisher: Institute of Science and Technology Austria
publist_id: '5802'
related_material:
record:
- id: '2847'
relation: part_of_dissertation
status: public
- id: '3251'
relation: part_of_dissertation
status: public
- id: '4361'
relation: part_of_dissertation
status: public
status: public
supervisor:
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000−0002−2985−7724
title: Analysis of dynamic message passing programs
type: dissertation
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
year: '2013'
...
---
_id: '1406'
abstract:
- lang: eng
text: Epithelial spreading is a critical part of various developmental and wound
repair processes. Here we use zebrafish epiboly as a model system to study the
cellular and molecular mechanisms underlying the spreading of epithelial sheets.
During zebrafish epiboly the enveloping cell layer (EVL), a simple squamous epithelium,
spreads over the embryo to eventually cover the entire yolk cell by the end of
gastrulation. The EVL leading edge is anchored through tight junctions to the
yolk syncytial layer (YSL), where directly adjacent to the EVL margin a contractile
actomyosin ring is formed that is thought to drive EVL epiboly. The prevalent
view in the field was that the contractile ring exerts a pulling force on the
EVL margin, which pulls the EVL towards the vegetal pole. However, how this force
is generated and how it affects EVL morphology still remains elusive. Moreover,
the cellular mechanisms mediating the increase in EVL surface area, while maintaining
tissue integrity and function are still unclear. Here we show that the YSL actomyosin
ring pulls on the EVL margin by two distinct force-generating mechanisms. One
mechanism is based on contraction of the ring around its circumference, as previously
proposed. The second mechanism is based on actomyosin retrogade flows, generating
force through resistance against the substrate. The latter can function at any
epiboly stage even in situations where the contraction-based mechanism is unproductive.
Additionally, we demonstrate that during epiboly the EVL is subjected to anisotropic
tension, which guides the orientation of EVL cell division along the main axis
(animal-vegetal) of tension. The influence of tension in cell division orientation
involves cell elongation and requires myosin-2 activity for proper spindle alignment.
Strikingly, we reveal that tension-oriented cell divisions release anisotropic
tension within the EVL and that in the absence of such divisions, EVL cells undergo
ectopic fusions. We conclude that forces applied to the EVL by the action of the
YSL actomyosin ring generate a tension anisotropy in the EVL that orients cell
divisions, which in turn limit tissue tension increase thereby facilitating tissue
spreading.
acknowledged_ssus:
- _id: Bio
- _id: PreCl
alternative_title:
- ISTA Thesis
article_processing_charge: No
author:
- first_name: Pedro
full_name: Campinho, Pedro
id: 3AFBBC42-F248-11E8-B48F-1D18A9856A87
last_name: Campinho
orcid: 0000-0002-8526-5416
citation:
ama: 'Campinho P. Mechanics of zebrafish epiboly: Tension-oriented cell divisions
limit anisotropic tissue tension in epithelial spreading. 2013.'
apa: 'Campinho, P. (2013). Mechanics of zebrafish epiboly: Tension-oriented cell
divisions limit anisotropic tissue tension in epithelial spreading. Institute
of Science and Technology Austria.'
chicago: 'Campinho, Pedro. “Mechanics of Zebrafish Epiboly: Tension-Oriented Cell
Divisions Limit Anisotropic Tissue Tension in Epithelial Spreading.” Institute
of Science and Technology Austria, 2013.'
ieee: 'P. Campinho, “Mechanics of zebrafish epiboly: Tension-oriented cell divisions
limit anisotropic tissue tension in epithelial spreading,” Institute of Science
and Technology Austria, 2013.'
ista: 'Campinho P. 2013. Mechanics of zebrafish epiboly: Tension-oriented cell divisions
limit anisotropic tissue tension in epithelial spreading. Institute of Science
and Technology Austria.'
mla: 'Campinho, Pedro. Mechanics of Zebrafish Epiboly: Tension-Oriented Cell
Divisions Limit Anisotropic Tissue Tension in Epithelial Spreading. Institute
of Science and Technology Austria, 2013.'
short: 'P. Campinho, Mechanics of Zebrafish Epiboly: Tension-Oriented Cell Divisions
Limit Anisotropic Tissue Tension in Epithelial Spreading, Institute of Science
and Technology Austria, 2013.'
date_created: 2018-12-11T11:51:50Z
date_published: 2013-10-01T00:00:00Z
date_updated: 2023-09-07T11:36:07Z
day: '01'
degree_awarded: PhD
department:
- _id: CaHe
language:
- iso: eng
month: '10'
oa_version: None
page: '123'
publication_identifier:
issn:
- 2663-337X
publication_status: published
publisher: Institute of Science and Technology Austria
publist_id: '5801'
status: public
supervisor:
- first_name: Carl-Philipp J
full_name: Heisenberg, Carl-Philipp J
id: 39427864-F248-11E8-B48F-1D18A9856A87
last_name: Heisenberg
orcid: 0000-0002-0912-4566
title: 'Mechanics of zebrafish epiboly: Tension-oriented cell divisions limit anisotropic
tissue tension in epithelial spreading'
type: dissertation
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
year: '2013'
...
---
_id: '5399'
abstract:
- lang: eng
text: In this work we present a flexible tool for tumor progression, which simulates
the evolutionary dynamics of cancer. Tumor progression implements a multi-type
branching process where the key parameters are the fitness landscape, the mutation
rate, and the average time of cell division. The fitness of a cancer cell depends
on the mutations it has accumulated. The input to our tool could be any fitness
landscape, mutation rate, and cell division time, and the tool produces the growth
dynamics and all relevant statistics.
alternative_title:
- IST Austria Technical Report
author:
- first_name: Johannes
full_name: Reiter, Johannes
id: 4A918E98-F248-11E8-B48F-1D18A9856A87
last_name: Reiter
orcid: 0000-0002-0170-7353
- first_name: Ivana
full_name: Bozic, Ivana
last_name: Bozic
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Martin
full_name: Nowak, Martin
last_name: Nowak
citation:
ama: 'Reiter J, Bozic I, Chatterjee K, Nowak M. TTP: Tool for Tumor Progression.
IST Austria; 2013. doi:10.15479/AT:IST-2013-104-v1-1'
apa: 'Reiter, J., Bozic, I., Chatterjee, K., & Nowak, M. (2013). TTP: Tool
for Tumor Progression. IST Austria. https://doi.org/10.15479/AT:IST-2013-104-v1-1'
chicago: 'Reiter, Johannes, Ivana Bozic, Krishnendu Chatterjee, and Martin Nowak.
TTP: Tool for Tumor Progression. IST Austria, 2013. https://doi.org/10.15479/AT:IST-2013-104-v1-1.'
ieee: 'J. Reiter, I. Bozic, K. Chatterjee, and M. Nowak, TTP: Tool for Tumor
Progression. IST Austria, 2013.'
ista: 'Reiter J, Bozic I, Chatterjee K, Nowak M. 2013. TTP: Tool for Tumor Progression,
IST Austria, 17p.'
mla: 'Reiter, Johannes, et al. TTP: Tool for Tumor Progression. IST Austria,
2013, doi:10.15479/AT:IST-2013-104-v1-1.'
short: 'J. Reiter, I. Bozic, K. Chatterjee, M. Nowak, TTP: Tool for Tumor Progression,
IST Austria, 2013.'
date_created: 2018-12-12T11:39:07Z
date_published: 2013-01-11T00:00:00Z
date_updated: 2023-02-23T10:23:57Z
day: '11'
ddc:
- '000'
department:
- _id: KrCh
doi: 10.15479/AT:IST-2013-104-v1-1
file:
- access_level: open_access
checksum: 2cc8c6e157eca1271128db80bb3dec80
content_type: application/pdf
creator: system
date_created: 2018-12-12T11:54:20Z
date_updated: 2020-07-14T12:46:44Z
file_id: '5542'
file_name: IST-2013-104-v1+1_tumortool.pdf
file_size: 1471954
relation: main_file
file_date_updated: 2020-07-14T12:46:44Z
has_accepted_license: '1'
language:
- iso: eng
month: '01'
oa: 1
oa_version: Published Version
page: '17'
publication_identifier:
issn:
- 2664-1690
publication_status: published
publisher: IST Austria
pubrep_id: '104'
related_material:
record:
- id: '2000'
relation: later_version
status: public
status: public
title: 'TTP: Tool for Tumor Progression'
type: technical_report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2013'
...
---
_id: '5400'
abstract:
- lang: eng
text: We consider partially observable Markov decision processes (POMDPs) with ω-regular
conditions specified as parity objectives. The class of ω-regular languages extends
regular languages to infinite strings and provides a robust specification language
to express all properties used in verification, and parity objectives are canonical
forms to express ω-regular conditions. The qualitative analysis problem given
a POMDP and a parity objective asks whether there is a strategy to ensure that
the objective is satis- fied with probability 1 (resp. positive probability).
While the qualitative analysis problems are known to be undecidable even for very
special cases of parity objectives, we establish decidability (with optimal complexity)
of the qualitative analysis problems for POMDPs with all parity objectives under
finite- memory strategies. We establish asymptotically optimal (exponential) memory
bounds and EXPTIME- completeness of the qualitative analysis problems under finite-memory
strategies for POMDPs with parity objectives.
alternative_title:
- IST Austria Technical Report
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Martin
full_name: Chmelik, Martin
id: 3624234E-F248-11E8-B48F-1D18A9856A87
last_name: Chmelik
- first_name: Mathieu
full_name: Tracol, Mathieu
id: 3F54FA38-F248-11E8-B48F-1D18A9856A87
last_name: Tracol
citation:
ama: Chatterjee K, Chmelik M, Tracol M. What Is Decidable about Partially Observable
Markov Decision Processes with ω-Regular Objectives. IST Austria; 2013. doi:10.15479/AT:IST-2013-109-v1-1
apa: Chatterjee, K., Chmelik, M., & Tracol, M. (2013). What is decidable
about partially observable Markov decision processes with ω-regular objectives.
IST Austria. https://doi.org/10.15479/AT:IST-2013-109-v1-1
chicago: Chatterjee, Krishnendu, Martin Chmelik, and Mathieu Tracol. What Is
Decidable about Partially Observable Markov Decision Processes with ω-Regular
Objectives. IST Austria, 2013. https://doi.org/10.15479/AT:IST-2013-109-v1-1.
ieee: K. Chatterjee, M. Chmelik, and M. Tracol, What is decidable about partially
observable Markov decision processes with ω-regular objectives. IST Austria,
2013.
ista: Chatterjee K, Chmelik M, Tracol M. 2013. What is decidable about partially
observable Markov decision processes with ω-regular objectives, IST Austria, 41p.
mla: Chatterjee, Krishnendu, et al. What Is Decidable about Partially Observable
Markov Decision Processes with ω-Regular Objectives. IST Austria, 2013, doi:10.15479/AT:IST-2013-109-v1-1.
short: K. Chatterjee, M. Chmelik, M. Tracol, What Is Decidable about Partially Observable
Markov Decision Processes with ω-Regular Objectives, IST Austria, 2013.
date_created: 2018-12-12T11:39:07Z
date_published: 2013-02-20T00:00:00Z
date_updated: 2023-02-23T10:36:45Z
day: '20'
ddc:
- '000'
- '005'
department:
- _id: KrCh
doi: 10.15479/AT:IST-2013-109-v1-1
file:
- access_level: open_access
checksum: cbba40210788a1b22c6cf06433b5ed6f
content_type: application/pdf
creator: system
date_created: 2018-12-12T11:53:06Z
date_updated: 2020-07-14T12:46:44Z
file_id: '5467'
file_name: IST-2013-109-v1+1_What_is_Decidable_about_Partially_Observable_Markov_Decision_Processes_with_ω-Regular_Objectives.pdf
file_size: 483407
relation: main_file
file_date_updated: 2020-07-14T12:46:44Z
has_accepted_license: '1'
language:
- iso: eng
month: '02'
oa: 1
oa_version: Published Version
page: '41'
publication_identifier:
issn:
- 2664-1690
publication_status: published
publisher: IST Austria
pubrep_id: '109'
related_material:
record:
- id: '1477'
relation: later_version
status: public
- id: '2295'
relation: later_version
status: public
status: public
title: What is decidable about partially observable Markov decision processes with
ω-regular objectives
type: technical_report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2013'
...
---
_id: '5401'
abstract:
- lang: eng
text: This document is created as a part of the project “Repository for Research
Data at IST Austria”. It summarises the actual initiatives, projects and standards
related to the project. It supports the preparation of standards and specifications
for the project, which should be considered and followed to ensure interoperability
and visibility of the uploaded data.
author:
- first_name: Jana
full_name: Porsche, Jana
id: 3252EDC2-F248-11E8-B48F-1D18A9856A87
last_name: Porsche
citation:
ama: Porsche J. Initiatives and Projects Related to RD. IST Austria; 2013.
apa: Porsche, J. (2013). Initiatives and projects related to RD. IST Austria.
chicago: Porsche, Jana. Initiatives and Projects Related to RD. IST Austria,
2013.
ieee: J. Porsche, Initiatives and projects related to RD. IST Austria, 2013.
ista: Porsche J. 2013. Initiatives and projects related to RD, IST Austria,p.
mla: Porsche, Jana. Initiatives and Projects Related to RD. IST Austria,
2013.
short: J. Porsche, Initiatives and Projects Related to RD, IST Austria, 2013.
date_created: 2018-12-12T11:39:07Z
date_published: 2013-03-20T00:00:00Z
date_updated: 2020-07-14T23:04:47Z
day: '20'
ddc:
- '020'
department:
- _id: E-Lib
file:
- access_level: open_access
checksum: d68712db838432ecdacf9ffb1de8f8a6
content_type: application/pdf
creator: system
date_created: 2018-12-12T11:54:14Z
date_updated: 2020-07-14T12:46:45Z
file_id: '5536'
file_name: IST-2013-113-v1+1_Initiatives_and_projects_related_to_RD.pdf
file_size: 151208
relation: main_file
file_date_updated: 2020-07-14T12:46:45Z
has_accepted_license: '1'
language:
- iso: eng
month: '03'
oa: 1
oa_version: Published Version
publication_status: published
publisher: IST Austria
pubrep_id: '113'
status: public
title: Initiatives and projects related to RD
type: report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2013'
...
---
_id: '5402'
abstract:
- lang: eng
text: "Linearizability requires that the outcome of calls by competing threads to
a concurrent data structure is the same as some sequential execution where each
thread has exclusive access to the data structure. In an ordered data structure,
such as a queue or a stack, linearizability is ensured by requiring threads commit
in the order dictated by the sequential semantics of the data structure; e.g.,
in a concurrent queue implementation a dequeue can only remove the oldest element.
\r\nIn this paper, we investigate the impact of this strict ordering, by comparing
what linearizability allows to what existing implementations do. We first give
an operational definition for linearizability which allows us to build the most
general linearizable implementation as a transition system for any given sequential
specification. We then use this operational definition to categorize linearizable
implementations based on whether they are bound or free. In a bound implementation,
whenever all threads observe the same logical state, the updates to the logical
state and the temporal order of commits coincide. All existing queue implementations
we know of are bound. We then proceed to present, to the best of our knowledge,
the first ever free queue implementation. Our experiments show that free implementations
have the potential for better performance by suffering less from contention."
alternative_title:
- IST Austria Technical Report
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: Ali
full_name: Sezgin, Ali
id: 4C7638DA-F248-11E8-B48F-1D18A9856A87
last_name: Sezgin
citation:
ama: Henzinger TA, Sezgin A. How Free Is Your Linearizable Concurrent Data Structure?
IST Austria; 2013. doi:10.15479/AT:IST-2013-123-v1-1
apa: Henzinger, T. A., & Sezgin, A. (2013). How free is your linearizable
concurrent data structure? IST Austria. https://doi.org/10.15479/AT:IST-2013-123-v1-1
chicago: Henzinger, Thomas A, and Ali Sezgin. How Free Is Your Linearizable Concurrent
Data Structure? IST Austria, 2013. https://doi.org/10.15479/AT:IST-2013-123-v1-1.
ieee: T. A. Henzinger and A. Sezgin, How free is your linearizable concurrent
data structure? IST Austria, 2013.
ista: Henzinger TA, Sezgin A. 2013. How free is your linearizable concurrent data
structure?, IST Austria, 16p.
mla: Henzinger, Thomas A., and Ali Sezgin. How Free Is Your Linearizable Concurrent
Data Structure? IST Austria, 2013, doi:10.15479/AT:IST-2013-123-v1-1.
short: T.A. Henzinger, A. Sezgin, How Free Is Your Linearizable Concurrent Data
Structure?, IST Austria, 2013.
date_created: 2018-12-12T11:39:07Z
date_published: 2013-06-12T00:00:00Z
date_updated: 2020-07-14T23:04:47Z
day: '12'
ddc:
- '000'
- '004'
department:
- _id: ToHe
doi: 10.15479/AT:IST-2013-123-v1-1
file:
- access_level: open_access
checksum: ce580605ae9756a8c99d7b403ebb8eed
content_type: application/pdf
creator: system
date_created: 2018-12-12T11:53:19Z
date_updated: 2020-07-14T12:46:45Z
file_id: '5480'
file_name: IST-2013-123-v1+1_main-concur2013.pdf
file_size: 249790
relation: main_file
file_date_updated: 2020-07-14T12:46:45Z
has_accepted_license: '1'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
page: '16'
publication_identifier:
issn:
- 2664-1690
publication_status: published
publisher: IST Austria
pubrep_id: '123'
status: public
title: How free is your linearizable concurrent data structure?
type: technical_report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2013'
...
---
_id: '5403'
abstract:
- lang: eng
text: 'We consider concurrent games played by two-players on a finite state graph,
where in every round the players simultaneously choose a move, and the current
state along with the joint moves determine the successor state. We study the most
fundamental objective for concurrent games, namely, mean-payoff or limit-average
objective, where a reward is associated to every transition, and the goal of player
1 is to maximize the long-run average of the rewards, and the objective of player
2 is strictly the opposite (i.e., the games are zero-sum). The path constraint
for player 1 could be qualitative, i.e., the mean-payoff is the maximal reward,
or arbitrarily close to it; or quantitative, i.e., a given threshold between the
minimal and maximal reward. We consider the computation of the almost-sure (resp.
positive) winning sets, where player 1 can ensure that the path constraint is
satisfied with probability 1 (resp. positive probability). Almost-sure winning
with qualitative constraint exactly corresponds to the question whether there
exists a strategy to ensure that the payoff is the maximal reward of the game.
Our main results for qualitative path constraints are as follows: (1) we establish
qualitative determinacy results that show for every state either player 1 has
a strategy to ensure almost-sure (resp. positive) winning against all player-2
strategies or player 2 has a spoiling strategy to falsify almost-sure (resp. positive)
winning against all player-1 strategies; (2) we present optimal strategy complexity
results that precisely characterize the classes of strategies required for almost-sure
and positive winning for both players; and (3) we present quadratic time algorithms
to compute the almost-sure and the positive winning sets, matching the best known
bound of the algorithms for much simpler problems (such as reachability objectives).
For quantitative constraints we show that a polynomial time solution for the almost-sure
or the positive winning set would imply a solution to a long-standing open problem
(of solving the value problem of mean-payoff games) that is not known to be in
polynomial time.'
alternative_title:
- IST Austria Technical Report
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Rasmus
full_name: Ibsen-Jensen, Rasmus
id: 3B699956-F248-11E8-B48F-1D18A9856A87
last_name: Ibsen-Jensen
orcid: 0000-0003-4783-0389
citation:
ama: Chatterjee K, Ibsen-Jensen R. Qualitative Analysis of Concurrent Mean-Payoff
Games. IST Austria; 2013. doi:10.15479/AT:IST-2013-126-v1-1
apa: Chatterjee, K., & Ibsen-Jensen, R. (2013). Qualitative analysis of concurrent
mean-payoff games. IST Austria. https://doi.org/10.15479/AT:IST-2013-126-v1-1
chicago: Chatterjee, Krishnendu, and Rasmus Ibsen-Jensen. Qualitative Analysis
of Concurrent Mean-Payoff Games. IST Austria, 2013. https://doi.org/10.15479/AT:IST-2013-126-v1-1.
ieee: K. Chatterjee and R. Ibsen-Jensen, Qualitative analysis of concurrent mean-payoff
games. IST Austria, 2013.
ista: Chatterjee K, Ibsen-Jensen R. 2013. Qualitative analysis of concurrent mean-payoff
games, IST Austria, 33p.
mla: Chatterjee, Krishnendu, and Rasmus Ibsen-Jensen. Qualitative Analysis of
Concurrent Mean-Payoff Games. IST Austria, 2013, doi:10.15479/AT:IST-2013-126-v1-1.
short: K. Chatterjee, R. Ibsen-Jensen, Qualitative Analysis of Concurrent Mean-Payoff
Games, IST Austria, 2013.
date_created: 2018-12-12T11:39:08Z
date_published: 2013-07-03T00:00:00Z
date_updated: 2023-02-23T12:22:53Z
day: '03'
ddc:
- '000'
- '005'
department:
- _id: KrCh
doi: 10.15479/AT:IST-2013-126-v1-1
file:
- access_level: open_access
checksum: 063868c665beec37bf28160e2a695746
content_type: application/pdf
creator: system
date_created: 2018-12-12T11:53:49Z
date_updated: 2020-07-14T12:46:45Z
file_id: '5510'
file_name: IST-2013-126-v1+1_soda_full.pdf
file_size: 434523
relation: main_file
file_date_updated: 2020-07-14T12:46:45Z
has_accepted_license: '1'
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
page: '33'
publication_identifier:
issn:
- 2664-1690
publication_status: published
publisher: IST Austria
pubrep_id: '126'
related_material:
record:
- id: '524'
relation: later_version
status: public
status: public
title: Qualitative analysis of concurrent mean-payoff games
type: technical_report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2013'
...
---
_id: '5404'
abstract:
- lang: eng
text: 'We study finite-state two-player (zero-sum) concurrent mean-payoff games
played on a graph. We focus on the important sub-class of ergodic games where
all states are visited infinitely often with probability 1. The algorithmic study
of ergodic games was initiated in a seminal work of Hoffman and Karp in 1966,
but all basic complexity questions have remained unresolved. Our main results
for ergodic games are as follows: We establish (1) an optimal exponential bound
on the patience of stationary strategies (where patience of a distribution is
the inverse of the smallest positive probability and represents a complexity measure
of a stationary strategy); (2) the approximation problem lie in FNP; (3) the approximation
problem is at least as hard as the decision problem for simple stochastic games
(for which NP and coNP is the long-standing best known bound). We show that the
exact value can be expressed in the existential theory of the reals, and also
establish square-root sum hardness for a related class of games.'
alternative_title:
- IST Austria Technical Report
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Rasmus
full_name: Ibsen-Jensen, Rasmus
id: 3B699956-F248-11E8-B48F-1D18A9856A87
last_name: Ibsen-Jensen
orcid: 0000-0003-4783-0389
citation:
ama: Chatterjee K, Ibsen-Jensen R. The Complexity of Ergodic Games. IST Austria;
2013. doi:10.15479/AT:IST-2013-127-v1-1
apa: Chatterjee, K., & Ibsen-Jensen, R. (2013). The complexity of ergodic
games. IST Austria. https://doi.org/10.15479/AT:IST-2013-127-v1-1
chicago: Chatterjee, Krishnendu, and Rasmus Ibsen-Jensen. The Complexity of Ergodic
Games. IST Austria, 2013. https://doi.org/10.15479/AT:IST-2013-127-v1-1.
ieee: K. Chatterjee and R. Ibsen-Jensen, The complexity of ergodic games.
IST Austria, 2013.
ista: Chatterjee K, Ibsen-Jensen R. 2013. The complexity of ergodic games, IST Austria,
29p.
mla: Chatterjee, Krishnendu, and Rasmus Ibsen-Jensen. The Complexity of Ergodic
Games. IST Austria, 2013, doi:10.15479/AT:IST-2013-127-v1-1.
short: K. Chatterjee, R. Ibsen-Jensen, The Complexity of Ergodic Games, IST Austria,
2013.
date_created: 2018-12-12T11:39:08Z
date_published: 2013-07-03T00:00:00Z
date_updated: 2023-02-23T10:30:55Z
day: '03'
ddc:
- '000'
- '005'
department:
- _id: KrCh
doi: 10.15479/AT:IST-2013-127-v1-1
file:
- access_level: open_access
checksum: 79ee5e677a82611ce06e0360c69d494a
content_type: application/pdf
creator: system
date_created: 2018-12-12T11:53:35Z
date_updated: 2020-07-14T12:46:45Z
file_id: '5496'
file_name: IST-2013-127-v1+1_ergodic.pdf
file_size: 517275
relation: main_file
file_date_updated: 2020-07-14T12:46:45Z
has_accepted_license: '1'
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
page: '29'
publication_identifier:
issn:
- 2664-1690
publication_status: published
publisher: IST Austria
pubrep_id: '127'
related_material:
record:
- id: '2162'
relation: later_version
status: public
status: public
title: The complexity of ergodic games
type: technical_report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2013'
...