---
_id: '6740'
abstract:
- lang: eng
text: We describe coding techniques that achieve the capacity of a discrete memoryless
asymmetric channel. To do so, we discuss how recent advances in coding for symmetric
channels yield more efficient solutions also for the asymmetric case. In more
detail, we consider three basic approaches. The first one is Gallager's scheme
that concatenates a linear code with a non-linear mapper, in order to bias the
input distribution. We explicitly show that both polar codes and spatially coupled
codes can be employed in this scenario. Further, we derive a scaling law between
the gap to capacity, the cardinality of channel input and output alphabets, and
the required size of the mapper. The second one is an integrated approach in which
the coding scheme is used both for source coding, in order to create codewords
with the capacity-achieving distribution, and for channel coding, in order to
provide error protection. Such a technique has been recently introduced by Honda
and Yamamoto in the context of polar codes, and we show how to apply it also to
the design of sparse graph codes. The third approach is based on an idea due to
Böcherer and Mathar and separates completely the two tasks of source coding and
channel coding by “chaining” together several codewords. We prove that we can
combine any suitable source code with any suitable channel code in order to provide
optimal schemes for asymmetric channels. In particular, polar codes and spatially
coupled codes fulfill the required conditions.
arxiv: 1
author:
- first_name: Marco
full_name: Mondelli, Marco
id: 27EB676C-8706-11E9-9510-7717E6697425
last_name: Mondelli
orcid: 0000-0002-3242-7020
- first_name: Rudiger
full_name: Urbanke, Rudiger
last_name: Urbanke
- first_name: Hamed
full_name: Hassani, Hamed
last_name: Hassani
citation:
ama: 'Mondelli M, Urbanke R, Hassani H. How to achieve the capacity of asymmetric
channels. In: 52nd Annual Allerton Conference on Communication, Control, and
Computing. IEEE; 2014:789-796. doi:10.1109/allerton.2014.7028535'
apa: 'Mondelli, M., Urbanke, R., & Hassani, H. (2014). How to achieve the capacity
of asymmetric channels. In 52nd Annual Allerton Conference on Communication,
Control, and Computing (pp. 789–796). Monticello, IL, United States: IEEE.
https://doi.org/10.1109/allerton.2014.7028535'
chicago: Mondelli, Marco, Rudiger Urbanke, and Hamed Hassani. “How to Achieve the
Capacity of Asymmetric Channels.” In 52nd Annual Allerton Conference on Communication,
Control, and Computing, 789–96. IEEE, 2014. https://doi.org/10.1109/allerton.2014.7028535.
ieee: M. Mondelli, R. Urbanke, and H. Hassani, “How to achieve the capacity of asymmetric
channels,” in 52nd Annual Allerton Conference on Communication, Control, and
Computing, Monticello, IL, United States, 2014, pp. 789–796.
ista: Mondelli M, Urbanke R, Hassani H. 2014. How to achieve the capacity of asymmetric
channels. 52nd Annual Allerton Conference on Communication, Control, and Computing.
Allerton Conference on Communication, Control, and Computing, 789–796.
mla: Mondelli, Marco, et al. “How to Achieve the Capacity of Asymmetric Channels.”
52nd Annual Allerton Conference on Communication, Control, and Computing,
IEEE, 2014, pp. 789–96, doi:10.1109/allerton.2014.7028535.
short: M. Mondelli, R. Urbanke, H. Hassani, in:, 52nd Annual Allerton Conference
on Communication, Control, and Computing, IEEE, 2014, pp. 789–796.
conference:
end_date: 2014-10-03
location: Monticello, IL, United States
name: Allerton Conference on Communication, Control, and Computing
start_date: 2014-09-30
date_created: 2019-07-31T07:24:23Z
date_published: 2014-10-01T00:00:00Z
date_updated: 2023-02-23T12:49:36Z
day: '01'
doi: 10.1109/allerton.2014.7028535
extern: '1'
external_id:
arxiv:
- '1406.7373'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1406.7373
month: '10'
oa: 1
oa_version: Preprint
page: 789-796
publication: 52nd Annual Allerton Conference on Communication, Control, and Computing
publication_identifier:
eisbn:
- 978-1-4799-8009-3
publication_status: published
publisher: IEEE
quality_controlled: '1'
related_material:
record:
- id: '6678'
relation: later_version
status: public
status: public
title: How to achieve the capacity of asymmetric channels
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2014'
...
---
_id: '7038'
article_processing_charge: No
author:
- first_name: Kristóf
full_name: Huszár, Kristóf
id: 33C26278-F248-11E8-B48F-1D18A9856A87
last_name: Huszár
orcid: 0000-0002-5445-5057
- first_name: Michal
full_name: Rolinek, Michal
id: 3CB3BC06-F248-11E8-B48F-1D18A9856A87
last_name: Rolinek
citation:
ama: Huszár K, Rolinek M. Playful Math - An Introduction to Mathematical Games.
IST Austria
apa: Huszár, K., & Rolinek, M. (n.d.). Playful Math - An introduction to
mathematical games. IST Austria.
chicago: Huszár, Kristóf, and Michal Rolinek. Playful Math - An Introduction
to Mathematical Games. IST Austria, n.d.
ieee: K. Huszár and M. Rolinek, Playful Math - An introduction to mathematical
games. IST Austria.
ista: Huszár K, Rolinek M. Playful Math - An introduction to mathematical games,
IST Austria, 5p.
mla: Huszár, Kristóf, and Michal Rolinek. Playful Math - An Introduction to Mathematical
Games. IST Austria.
short: K. Huszár, M. Rolinek, Playful Math - An Introduction to Mathematical Games,
IST Austria, n.d.
date_created: 2019-11-18T15:57:05Z
date_published: 2014-06-30T00:00:00Z
date_updated: 2020-07-14T23:11:45Z
day: '30'
ddc:
- '510'
department:
- _id: VlKo
- _id: UlWa
file:
- access_level: open_access
checksum: 2b94e5e1f4c3fe8ab89b12806276fb09
content_type: application/pdf
creator: dernst
date_created: 2019-11-18T15:57:51Z
date_updated: 2020-07-14T12:47:48Z
file_id: '7039'
file_name: 2014_Playful_Math_Huszar.pdf
file_size: 511233
relation: main_file
file_date_updated: 2020-07-14T12:47:48Z
has_accepted_license: '1'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
page: '5'
publication_status: draft
publisher: IST Austria
status: public
title: Playful Math - An introduction to mathematical games
type: working_paper
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2014'
...
---
_id: '7071'
abstract:
- lang: eng
text: Spin and orbital quantum numbers play a key role in the physics of Mott insulators,
but in most systems they are connected only indirectly—via the Pauli exclusion
principle and the Coulomb interaction. Iridium-based oxides (iridates) introduce
strong spin–orbit coupling directly, such that these numbers become entwined together
and the Mott physics attains a strong orbital character. In the layered honeycomb
iridates this is thought to generate highly spin–anisotropic magnetic interactions,
coupling the spin to a given spatial direction of exchange and leading to strongly
frustrated magnetism. Here we report a new iridate structure that has the same
local connectivity as the layered honeycomb and exhibits striking evidence for
highly spin–anisotropic exchange. The basic structural units of this material
suggest that a new family of three-dimensional structures could exist, the ‘harmonic
honeycomb’ iridates, of which the present compound is the first example.
article_number: '4203'
article_processing_charge: No
article_type: original
author:
- first_name: Kimberly A
full_name: Modic, Kimberly A
id: 13C26AC0-EB69-11E9-87C6-5F3BE6697425
last_name: Modic
orcid: 0000-0001-9760-3147
- first_name: Tess E.
full_name: Smidt, Tess E.
last_name: Smidt
- first_name: Itamar
full_name: Kimchi, Itamar
last_name: Kimchi
- first_name: Nicholas P.
full_name: Breznay, Nicholas P.
last_name: Breznay
- first_name: Alun
full_name: Biffin, Alun
last_name: Biffin
- first_name: Sungkyun
full_name: Choi, Sungkyun
last_name: Choi
- first_name: Roger D.
full_name: Johnson, Roger D.
last_name: Johnson
- first_name: Radu
full_name: Coldea, Radu
last_name: Coldea
- first_name: Pilanda
full_name: Watkins-Curry, Pilanda
last_name: Watkins-Curry
- first_name: Gregory T.
full_name: McCandless, Gregory T.
last_name: McCandless
- first_name: Julia Y.
full_name: Chan, Julia Y.
last_name: Chan
- first_name: Felipe
full_name: Gandara, Felipe
last_name: Gandara
- first_name: Z.
full_name: Islam, Z.
last_name: Islam
- first_name: Ashvin
full_name: Vishwanath, Ashvin
last_name: Vishwanath
- first_name: Arkady
full_name: Shekhter, Arkady
last_name: Shekhter
- first_name: Ross D.
full_name: McDonald, Ross D.
last_name: McDonald
- first_name: James G.
full_name: Analytis, James G.
last_name: Analytis
citation:
ama: Modic KA, Smidt TE, Kimchi I, et al. Realization of a three-dimensional spin–anisotropic
harmonic honeycomb iridate. Nature Communications. 2014;5. doi:10.1038/ncomms5203
apa: Modic, K. A., Smidt, T. E., Kimchi, I., Breznay, N. P., Biffin, A., Choi, S.,
… Analytis, J. G. (2014). Realization of a three-dimensional spin–anisotropic
harmonic honeycomb iridate. Nature Communications. Springer Science and
Business Media LLC. https://doi.org/10.1038/ncomms5203
chicago: Modic, Kimberly A, Tess E. Smidt, Itamar Kimchi, Nicholas P. Breznay, Alun
Biffin, Sungkyun Choi, Roger D. Johnson, et al. “Realization of a Three-Dimensional
Spin–Anisotropic Harmonic Honeycomb Iridate.” Nature Communications. Springer
Science and Business Media LLC, 2014. https://doi.org/10.1038/ncomms5203.
ieee: K. A. Modic et al., “Realization of a three-dimensional spin–anisotropic
harmonic honeycomb iridate,” Nature Communications, vol. 5. Springer Science
and Business Media LLC, 2014.
ista: Modic KA, Smidt TE, Kimchi I, Breznay NP, Biffin A, Choi S, Johnson RD, Coldea
R, Watkins-Curry P, McCandless GT, Chan JY, Gandara F, Islam Z, Vishwanath A,
Shekhter A, McDonald RD, Analytis JG. 2014. Realization of a three-dimensional
spin–anisotropic harmonic honeycomb iridate. Nature Communications. 5, 4203.
mla: Modic, Kimberly A., et al. “Realization of a Three-Dimensional Spin–Anisotropic
Harmonic Honeycomb Iridate.” Nature Communications, vol. 5, 4203, Springer
Science and Business Media LLC, 2014, doi:10.1038/ncomms5203.
short: K.A. Modic, T.E. Smidt, I. Kimchi, N.P. Breznay, A. Biffin, S. Choi, R.D.
Johnson, R. Coldea, P. Watkins-Curry, G.T. McCandless, J.Y. Chan, F. Gandara,
Z. Islam, A. Vishwanath, A. Shekhter, R.D. McDonald, J.G. Analytis, Nature Communications
5 (2014).
date_created: 2019-11-19T13:22:39Z
date_published: 2014-06-27T00:00:00Z
date_updated: 2021-01-12T08:11:42Z
day: '27'
ddc:
- '530'
doi: 10.1038/ncomms5203
extern: '1'
file:
- access_level: open_access
checksum: d290f0bfa93c5169cc6c8086874c5a78
content_type: application/pdf
creator: dernst
date_created: 2019-11-26T12:44:23Z
date_updated: 2020-07-14T12:47:48Z
file_id: '7113'
file_name: 2014_NatureComm_Modic.pdf
file_size: 4832820
relation: main_file
file_date_updated: 2020-07-14T12:47:48Z
has_accepted_license: '1'
intvolume: ' 5'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
publication: Nature Communications
publication_identifier:
issn:
- 2041-1723
publication_status: published
publisher: Springer Science and Business Media LLC
quality_controlled: '1'
status: public
title: Realization of a three-dimensional spin–anisotropic harmonic honeycomb iridate
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: 5
year: '2014'
...
---
_id: '7598'
article_processing_charge: No
article_type: original
author:
- first_name: Shutang
full_name: Tan, Shutang
id: 2DE75584-F248-11E8-B48F-1D18A9856A87
last_name: Tan
orcid: 0000-0002-0471-8285
- first_name: Hong-Wei
full_name: Xue, Hong-Wei
last_name: Xue
citation:
ama: Tan S, Xue H-W. Casein kinase 1 regulates ethylene synthesis by phosphorylating
and promoting the turnover of ACS5. Cell Reports. 2014;9(5):1692-1702.
doi:10.1016/j.celrep.2014.10.047
apa: Tan, S., & Xue, H.-W. (2014). Casein kinase 1 regulates ethylene synthesis
by phosphorylating and promoting the turnover of ACS5. Cell Reports. Elsevier.
https://doi.org/10.1016/j.celrep.2014.10.047
chicago: Tan, Shutang, and Hong-Wei Xue. “Casein Kinase 1 Regulates Ethylene Synthesis
by Phosphorylating and Promoting the Turnover of ACS5.” Cell Reports. Elsevier,
2014. https://doi.org/10.1016/j.celrep.2014.10.047.
ieee: S. Tan and H.-W. Xue, “Casein kinase 1 regulates ethylene synthesis by phosphorylating
and promoting the turnover of ACS5,” Cell Reports, vol. 9, no. 5. Elsevier,
pp. 1692–1702, 2014.
ista: Tan S, Xue H-W. 2014. Casein kinase 1 regulates ethylene synthesis by phosphorylating
and promoting the turnover of ACS5. Cell Reports. 9(5), 1692–1702.
mla: Tan, Shutang, and Hong-Wei Xue. “Casein Kinase 1 Regulates Ethylene Synthesis
by Phosphorylating and Promoting the Turnover of ACS5.” Cell Reports, vol.
9, no. 5, Elsevier, 2014, pp. 1692–702, doi:10.1016/j.celrep.2014.10.047.
short: S. Tan, H.-W. Xue, Cell Reports 9 (2014) 1692–1702.
date_created: 2020-03-21T16:08:18Z
date_published: 2014-12-11T00:00:00Z
date_updated: 2021-01-12T08:14:24Z
day: '11'
ddc:
- '580'
doi: 10.1016/j.celrep.2014.10.047
extern: '1'
file:
- access_level: open_access
checksum: 23c30de4ac98ce9879fc054121517626
content_type: application/pdf
creator: dernst
date_created: 2020-03-23T12:23:40Z
date_updated: 2020-07-14T12:48:01Z
file_id: '7613'
file_name: 2014_CellPress_Tan.pdf
file_size: 2755808
relation: main_file
file_date_updated: 2020-07-14T12:48:01Z
has_accepted_license: '1'
intvolume: ' 9'
issue: '5'
language:
- iso: eng
month: '12'
oa: 1
oa_version: Published Version
page: 1692-1702
publication: Cell Reports
publication_identifier:
issn:
- 2211-1247
publication_status: published
publisher: Elsevier
quality_controlled: '1'
status: public
title: Casein kinase 1 regulates ethylene synthesis by phosphorylating and promoting
the turnover of ACS5
tmp:
image: /images/cc_by_nc_nd.png
legal_code_url: https://creativecommons.org/licenses/by-nc-nd/4.0/legalcode
name: Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International
(CC BY-NC-ND 4.0)
short: CC BY-NC-ND (4.0)
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 9
year: '2014'
...
---
_id: '772'
abstract:
- lang: eng
text: Lock-free concurrent algorithms guarantee that some concurrent operation will
always make progress in a finite number of steps. Yet programmers prefer to treat
concurrent code as if it were wait-free, guaranteeing that all operations always
make progress. Unfortunately, designing wait-free algorithms is generally a very
complex task, and the resulting algorithms are not always efficient. While obtaining
efficient wait-free algorithms has been a long-time goal for the theory community,
most non-blocking commercial code is only lock-free. This paper suggests a simple
solution to this problem. We show that, for a large class of lock-free algorithms,
under scheduling conditions which approximate those found in commercial hardware
architectures, lock-free algorithms behave as if they are wait-free. In other
words, programmers can keep on designing simple lock-free algorithms instead of
complex wait-free ones, and in practice, they will get wait-free progress. Our
main contribution is a new way of analyzing a general class of lock-free algorithms
under a stochastic scheduler. Our analysis relates the individual performance
of processes with the global performance of the system using Markov chain lifting
between a complex per-process chain and a simpler system progress chain. We show
that lock-free algorithms are not only wait-free with probability 1, but that
in fact a general subset of lock-free algorithms can be closely bounded in terms
of the average number of steps required until an operation completes. To the best
of our knowledge, this is the first attempt to analyze progress conditions, typically
stated in relation to a worst case adversary, in a stochastic model capturing
their expected asymptotic behavior.
acknowledgement: "Dan Alistarh - Part of this work was performed while the author
was a Postdoctoral Associate at MIT CSAIL, where he was supported by SNF\r\nPostdoctoral
Fellows Program, NSF grant CCF-1217921, DoE\r\nASCR grant ER26116/DE-SC0008923,
and by grants from the Oracle and Intel corporations.\r\nKeron Censor-Hillel - Shalon
Fellow\r\nNir Shavit - This work was supported in part by NSF grants CCF-1217921
and\r\nCCF-1301926, DoE ASCR grant ER26116/DE-SC0008923, and\r\nby grants from the
Oracle and Intel corporations."
article_processing_charge: No
arxiv: 1
author:
- first_name: Dan-Adrian
full_name: Alistarh, Dan-Adrian
id: 4A899BFC-F248-11E8-B48F-1D18A9856A87
last_name: Alistarh
orcid: 0000-0003-3650-940X
- first_name: Keren
full_name: Censor Hillel, Keren
last_name: Censor Hillel
- first_name: Nir
full_name: Shavit, Nir
last_name: Shavit
citation:
ama: 'Alistarh D-A, Censor Hillel K, Shavit N. Are lock-free concurrent algorithms
practically wait-free? In: ACM; 2014:714-723. doi:10.1145/2591796.2591836'
apa: 'Alistarh, D.-A., Censor Hillel, K., & Shavit, N. (2014). Are lock-free
concurrent algorithms practically wait-free? (pp. 714–723). Presented at the STOC:
Symposium on Theory of Computing, ACM. https://doi.org/10.1145/2591796.2591836'
chicago: Alistarh, Dan-Adrian, Keren Censor Hillel, and Nir Shavit. “Are Lock-Free
Concurrent Algorithms Practically Wait-Free?,” 714–23. ACM, 2014. https://doi.org/10.1145/2591796.2591836.
ieee: 'D.-A. Alistarh, K. Censor Hillel, and N. Shavit, “Are lock-free concurrent
algorithms practically wait-free?,” presented at the STOC: Symposium on Theory
of Computing, 2014, pp. 714–723.'
ista: 'Alistarh D-A, Censor Hillel K, Shavit N. 2014. Are lock-free concurrent algorithms
practically wait-free? STOC: Symposium on Theory of Computing, 714–723.'
mla: Alistarh, Dan-Adrian, et al. Are Lock-Free Concurrent Algorithms Practically
Wait-Free? ACM, 2014, pp. 714–23, doi:10.1145/2591796.2591836.
short: D.-A. Alistarh, K. Censor Hillel, N. Shavit, in:, ACM, 2014, pp. 714–723.
conference:
name: 'STOC: Symposium on Theory of Computing'
date_created: 2018-12-11T11:48:25Z
date_published: 2014-01-01T00:00:00Z
date_updated: 2023-02-23T13:15:13Z
day: '01'
doi: 10.1145/2591796.2591836
extern: '1'
external_id:
arxiv:
- '1311.3200'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1311.3200
month: '01'
oa: 1
oa_version: Preprint
page: 714 - 723
publication_status: published
publisher: ACM
publist_id: '6885'
status: public
title: Are lock-free concurrent algorithms practically wait-free?
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2014'
...
---
_id: '775'
abstract:
- lang: eng
text: 'The long-lived renaming problem appears in shared-memory systems where a
set of threads need to register and deregister frequently from the computation,
while concurrent operations scan the set of currently registered threads. Instances
of this problem show up in concurrent implementations of transactional memory,
flat combining, thread barriers, and memory reclamation schemes for lock-free
data structures. In this paper, we analyze a randomized solution for long-lived
renaming. The algorithmic technique we consider, called the Level Array, has previously
been used for hashing and one-shot (single-use) renaming. Our main contribution
is to prove that, in long-lived executions, where processes may register and deregister
polynomially many times, the technique guarantees constant steps on average and
O (log log n) steps with high probability for registering, unit cost for deregistering,
and O (n) steps for collect queries, where n is an upper bound on the number of
processes that may be active at any point in time. We also show that the algorithm
has the surprising property that it is self-healing: under reasonable assumptions
on the schedule, operations running while the data structure is in a degraded
state implicitly help the data structure re-balance itself. This subtle mechanism
obviates the need for expensive periodic rebuilding procedures. Our benchmarks
validate this approach, showing that, for typical use parameters, the average
number of steps a process takes to register is less than two and the worst-case
number of steps is bounded by six, even in executions with billions of operations.
We contrast this with other randomized implementations, whose worst-case behavior
we show to be unreliable, and with deterministic implementations, whose cost is
linear in n.'
article_processing_charge: No
arxiv: 1
author:
- first_name: Dan-Adrian
full_name: Alistarh, Dan-Adrian
id: 4A899BFC-F248-11E8-B48F-1D18A9856A87
last_name: Alistarh
orcid: 0000-0003-3650-940X
- first_name: Justin
full_name: Kopinsky, Justin
last_name: Kopinsky
- first_name: Alexander
full_name: Matveev, Alexander
last_name: Matveev
- first_name: Nir
full_name: Shavit, Nir
last_name: Shavit
citation:
ama: 'Alistarh D-A, Kopinsky J, Matveev A, Shavit N. The levelarray: A fast, practical
long-lived renaming algorithm. In: IEEE; 2014:348-357. doi:10.1109/ICDCS.2014.43'
apa: 'Alistarh, D.-A., Kopinsky, J., Matveev, A., & Shavit, N. (2014). The levelarray:
A fast, practical long-lived renaming algorithm (pp. 348–357). Presented at the
ICDCS: International Conference on Distributed Computing Systems, IEEE. https://doi.org/10.1109/ICDCS.2014.43'
chicago: 'Alistarh, Dan-Adrian, Justin Kopinsky, Alexander Matveev, and Nir Shavit.
“The Levelarray: A Fast, Practical Long-Lived Renaming Algorithm,” 348–57. IEEE,
2014. https://doi.org/10.1109/ICDCS.2014.43.'
ieee: 'D.-A. Alistarh, J. Kopinsky, A. Matveev, and N. Shavit, “The levelarray:
A fast, practical long-lived renaming algorithm,” presented at the ICDCS: International
Conference on Distributed Computing Systems, 2014, pp. 348–357.'
ista: 'Alistarh D-A, Kopinsky J, Matveev A, Shavit N. 2014. The levelarray: A fast,
practical long-lived renaming algorithm. ICDCS: International Conference on Distributed
Computing Systems, 348–357.'
mla: 'Alistarh, Dan-Adrian, et al. The Levelarray: A Fast, Practical Long-Lived
Renaming Algorithm. IEEE, 2014, pp. 348–57, doi:10.1109/ICDCS.2014.43.'
short: D.-A. Alistarh, J. Kopinsky, A. Matveev, N. Shavit, in:, IEEE, 2014, pp.
348–357.
conference:
name: 'ICDCS: International Conference on Distributed Computing Systems'
date_created: 2018-12-11T11:48:26Z
date_published: 2014-08-29T00:00:00Z
date_updated: 2023-02-23T13:16:18Z
day: '29'
doi: 10.1109/ICDCS.2014.43
extern: '1'
external_id:
arxiv:
- '1405.5461'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1405.5461
month: '08'
oa: 1
oa_version: Preprint
page: 348 - 357
publication_status: published
publisher: IEEE
publist_id: '6883'
status: public
title: 'The levelarray: A fast, practical long-lived renaming algorithm'
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2014'
...
---
_id: '468'
abstract:
- lang: eng
text: Invasive alien parasites and pathogens are a growing threat to biodiversity
worldwide, which can contribute to the extinction of endemic species. On the Galápagos
Islands, the invasive parasitic fly Philornis downsi poses a major threat to the
endemic avifauna. Here, we investigated the influence of this parasite on the
breeding success of two Darwin's finch species, the warbler finch (Certhidea olivacea)
and the sympatric small tree finch (Camarhynchus parvulus), on Santa Cruz Island
in 2010 and 2012. While the population of the small tree finch appeared to be
stable, the warbler finch has experienced a dramatic decline in population size
on Santa Cruz Island since 1997. We aimed to identify whether warbler finches
are particularly vulnerable during different stages of the breeding cycle. Contrary
to our prediction, breeding success was lower in the small tree finch than in
the warbler finch. In both species P. downsi had a strong negative impact on breeding
success and our data suggest that heavy rain events also lowered the fledging
success. On the one hand parents might be less efficient in compensating their
chicks' energy loss due to parasitism as they might be less efficient in foraging
on days of heavy rain. On the other hand, intense rainfalls might lead to increased
humidity and more rapid cooling of the nests. In the case of the warbler finch
we found that the control of invasive plant species with herbicides had a significant
additive negative impact on the breeding success. It is very likely that the availability
of insects (i.e. food abundance) is lower in such controlled areas, as herbicide
usage led to the removal of the entire understory. Predation seems to be a minor
factor in brood loss.
acknowledgement: The study was funded by the University of Vienna (Focus of Excellence
grant), the Galápagos Conservation Trust, and the Ethologische Gesellschaft e.V.
article_number: '0107518'
author:
- first_name: Arno
full_name: Cimadom, Arno
last_name: Cimadom
- first_name: Angel
full_name: Ulloa, Angel
last_name: Ulloa
- first_name: Patrick
full_name: Meidl, Patrick
id: 4709BCE6-F248-11E8-B48F-1D18A9856A87
last_name: Meidl
- first_name: Markus
full_name: Zöttl, Markus
last_name: Zöttl
- first_name: Elisabet
full_name: Zöttl, Elisabet
last_name: Zöttl
- first_name: Birgit
full_name: Fessl, Birgit
last_name: Fessl
- first_name: Erwin
full_name: Nemeth, Erwin
last_name: Nemeth
- first_name: Michael
full_name: Dvorak, Michael
last_name: Dvorak
- first_name: Francesca
full_name: Cunninghame, Francesca
last_name: Cunninghame
- first_name: Sabine
full_name: Tebbich, Sabine
last_name: Tebbich
citation:
ama: Cimadom A, Ulloa A, Meidl P, et al. Invasive parasites habitat change and heavy
rainfall reduce breeding success in Darwin’s finches. PLoS One. 2014;9(9).
doi:10.1371/journal.pone.0107518
apa: Cimadom, A., Ulloa, A., Meidl, P., Zöttl, M., Zöttl, E., Fessl, B., … Tebbich,
S. (2014). Invasive parasites habitat change and heavy rainfall reduce breeding
success in Darwin’s finches. PLoS One. Public Library of Science. https://doi.org/10.1371/journal.pone.0107518
chicago: Cimadom, Arno, Angel Ulloa, Patrick Meidl, Markus Zöttl, Elisabet Zöttl,
Birgit Fessl, Erwin Nemeth, Michael Dvorak, Francesca Cunninghame, and Sabine
Tebbich. “Invasive Parasites Habitat Change and Heavy Rainfall Reduce Breeding
Success in Darwin’s Finches.” PLoS One. Public Library of Science, 2014.
https://doi.org/10.1371/journal.pone.0107518.
ieee: A. Cimadom et al., “Invasive parasites habitat change and heavy rainfall
reduce breeding success in Darwin’s finches,” PLoS One, vol. 9, no. 9.
Public Library of Science, 2014.
ista: Cimadom A, Ulloa A, Meidl P, Zöttl M, Zöttl E, Fessl B, Nemeth E, Dvorak M,
Cunninghame F, Tebbich S. 2014. Invasive parasites habitat change and heavy rainfall
reduce breeding success in Darwin’s finches. PLoS One. 9(9), 0107518.
mla: Cimadom, Arno, et al. “Invasive Parasites Habitat Change and Heavy Rainfall
Reduce Breeding Success in Darwin’s Finches.” PLoS One, vol. 9, no. 9,
0107518, Public Library of Science, 2014, doi:10.1371/journal.pone.0107518.
short: A. Cimadom, A. Ulloa, P. Meidl, M. Zöttl, E. Zöttl, B. Fessl, E. Nemeth,
M. Dvorak, F. Cunninghame, S. Tebbich, PLoS One 9 (2014).
date_created: 2018-12-11T11:46:38Z
date_published: 2014-09-23T00:00:00Z
date_updated: 2021-01-12T08:00:48Z
day: '23'
ddc:
- '576'
department:
- _id: CampIT
doi: 10.1371/journal.pone.0107518
file:
- access_level: open_access
checksum: b24e7518ccd41effed0d7d9e2498f67f
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:14:48Z
date_updated: 2020-07-14T12:46:34Z
file_id: '5103'
file_name: IST-2018-954-v1+1_2014_Meidl_Invasive_parasites.PDF
file_size: 489387
relation: main_file
file_date_updated: 2020-07-14T12:46:34Z
has_accepted_license: '1'
intvolume: ' 9'
issue: '9'
language:
- iso: eng
month: '09'
oa: 1
oa_version: Published Version
publication: PLoS One
publication_status: published
publisher: Public Library of Science
publist_id: '7352'
pubrep_id: '954'
quality_controlled: '1'
scopus_import: 1
status: public
title: Invasive parasites habitat change and heavy rainfall reduce breeding success
in Darwin's finches
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: 4435EBFC-F248-11E8-B48F-1D18A9856A87
volume: 9
year: '2014'
...
---
_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: '5411'
abstract:
- lang: eng
text: "Model-based testing is a promising technology for black-box software and
hardware testing, in which test cases are generated automatically from high-level
specifications. Nowadays, systems typically consist of multiple interacting components
and, due to their complexity, testing presents a considerable portion of the effort
and cost in the design process. Exploiting the compositional structure of system
specifications can considerably reduce the effort in model-based testing. Moreover,
inferring properties about the system from testing its individual components allows
the designer to reduce the amount of integration testing.\r\nIn this paper, we
study compositional properties of the IOCO-testing theory. We propose a new approach
to composition and hiding operations, inspired by contract-based design and interface
theories. These operations preserve behaviors that are compatible under composition
and hiding, and prune away incompatible ones. The resulting specification characterizes
the input sequences for which the unit testing of components is sufficient to
infer the correctness of component integration without the need for further tests.
We provide a methodology that uses these results to minimize integration testing
effort, but also to detect potential weaknesses in specifications. While we focus
on asynchronous models and the IOCO conformance relation, the resulting methodology
can be applied to a broader class of systems."
alternative_title:
- IST Austria Technical Report
author:
- first_name: Przemyslaw
full_name: Daca, Przemyslaw
id: 49351290-F248-11E8-B48F-1D18A9856A87
last_name: Daca
- 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: Willibald
full_name: Krenn, Willibald
last_name: Krenn
- first_name: Dejan
full_name: Nickovic, Dejan
id: 41BCEE5C-F248-11E8-B48F-1D18A9856A87
last_name: Nickovic
citation:
ama: Daca P, Henzinger TA, Krenn W, Nickovic D. Compositional Specifications
for IOCO Testing. IST Austria; 2014. doi:10.15479/AT:IST-2014-148-v2-1
apa: Daca, P., Henzinger, T. A., Krenn, W., & Nickovic, D. (2014). Compositional
specifications for IOCO testing. IST Austria. https://doi.org/10.15479/AT:IST-2014-148-v2-1
chicago: Daca, Przemyslaw, Thomas A Henzinger, Willibald Krenn, and Dejan Nickovic.
Compositional Specifications for IOCO Testing. IST Austria, 2014. https://doi.org/10.15479/AT:IST-2014-148-v2-1.
ieee: P. Daca, T. A. Henzinger, W. Krenn, and D. Nickovic, Compositional specifications
for IOCO testing. IST Austria, 2014.
ista: Daca P, Henzinger TA, Krenn W, Nickovic D. 2014. Compositional specifications
for IOCO testing, IST Austria, 20p.
mla: Daca, Przemyslaw, et al. Compositional Specifications for IOCO Testing.
IST Austria, 2014, doi:10.15479/AT:IST-2014-148-v2-1.
short: P. Daca, T.A. Henzinger, W. Krenn, D. Nickovic, Compositional Specifications
for IOCO Testing, IST Austria, 2014.
date_created: 2018-12-12T11:39:11Z
date_published: 2014-01-28T00:00:00Z
date_updated: 2023-02-23T10:31:07Z
day: '28'
ddc:
- '000'
department:
- _id: ToHe
doi: 10.15479/AT:IST-2014-148-v2-1
file:
- access_level: open_access
checksum: 0e03aba625cc334141a3148432aa5760
content_type: application/pdf
creator: system
date_created: 2018-12-12T11:54:21Z
date_updated: 2020-07-14T12:46:46Z
file_id: '5543'
file_name: IST-2014-148-v2+1_main_tr.pdf
file_size: 534732
relation: main_file
file_date_updated: 2020-07-14T12:46:46Z
has_accepted_license: '1'
language:
- iso: eng
month: '01'
oa: 1
oa_version: Published Version
page: '20'
publication_identifier:
issn:
- 2664-1690
publication_status: published
publisher: IST Austria
pubrep_id: '152'
related_material:
record:
- id: '2167'
relation: later_version
status: public
status: public
title: Compositional specifications for IOCO testing
type: technical_report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2014'
...
---
_id: '5412'
abstract:
- lang: eng
text: "We consider Markov decision processes (MDPs) which are a standard model for
probabilistic systems. We focus on qualitative properties for MDPs that can express
that desired behaviors of the system arise almost-surely (with probability 1)
or with positive probability.\r\nWe introduce a new simulation relation to capture
the refinement relation of MDPs with respect to qualitative properties, and present
discrete graph theoretic algorithms with quadratic complexity to compute the simulation
relation.\r\nWe present an automated technique for assume-guarantee style reasoning
for compositional analysis of MDPs with qualitative properties by giving a counter-example
guided abstraction-refinement approach to compute our new simulation relation.
We have implemented our algorithms and show that the compositional analysis leads
to significant improvements. "
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: Przemyslaw
full_name: Daca, Przemyslaw
id: 49351290-F248-11E8-B48F-1D18A9856A87
last_name: Daca
- first_name: Martin
full_name: Chmelik, Martin
id: 3624234E-F248-11E8-B48F-1D18A9856A87
last_name: Chmelik
citation:
ama: Chatterjee K, Daca P, Chmelik M. CEGAR for Qualitative Analysis of Probabilistic
Systems. IST Austria; 2014. doi:10.15479/AT:IST-2014-153-v1-1
apa: Chatterjee, K., Daca, P., & Chmelik, M. (2014). CEGAR for qualitative
analysis of probabilistic systems. IST Austria. https://doi.org/10.15479/AT:IST-2014-153-v1-1
chicago: Chatterjee, Krishnendu, Przemyslaw Daca, and Martin Chmelik. CEGAR for
Qualitative Analysis of Probabilistic Systems. IST Austria, 2014. https://doi.org/10.15479/AT:IST-2014-153-v1-1.
ieee: K. Chatterjee, P. Daca, and M. Chmelik, CEGAR for qualitative analysis
of probabilistic systems. IST Austria, 2014.
ista: Chatterjee K, Daca P, Chmelik M. 2014. CEGAR for qualitative analysis of probabilistic
systems, IST Austria, 31p.
mla: Chatterjee, Krishnendu, et al. CEGAR for Qualitative Analysis of Probabilistic
Systems. IST Austria, 2014, doi:10.15479/AT:IST-2014-153-v1-1.
short: K. Chatterjee, P. Daca, M. Chmelik, CEGAR for Qualitative Analysis of Probabilistic
Systems, IST Austria, 2014.
date_created: 2018-12-12T11:39:11Z
date_published: 2014-01-29T00:00:00Z
date_updated: 2023-02-23T12:25:18Z
day: '29'
ddc:
- '000'
department:
- _id: KrCh
doi: 10.15479/AT:IST-2014-153-v1-1
file:
- access_level: open_access
checksum: 4d6cda4bebed970926403ad6ad8c745f
content_type: application/pdf
creator: system
date_created: 2018-12-12T11:53:39Z
date_updated: 2020-07-14T12:46:47Z
file_id: '5500'
file_name: IST-2014-153-v1+1_main.pdf
file_size: 423322
relation: main_file
file_date_updated: 2020-07-14T12:46:47Z
has_accepted_license: '1'
language:
- iso: eng
month: '01'
oa: 1
oa_version: Published Version
page: '31'
publication_identifier:
issn:
- 2664-1690
publication_status: published
publisher: IST Austria
pubrep_id: '153'
related_material:
record:
- id: '2063'
relation: later_version
status: public
- id: '5413'
relation: later_version
status: public
- id: '5414'
relation: later_version
status: public
status: public
title: CEGAR for qualitative analysis of probabilistic systems
type: technical_report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2014'
...
---
_id: '5413'
abstract:
- lang: eng
text: "We consider Markov decision processes (MDPs) which are a standard model for
probabilistic systems. We focus on qualitative properties for MDPs that can express
that desired behaviors of the system arise almost-surely (with probability 1)
or with positive probability.\r\nWe introduce a new simulation relation to capture
the refinement relation of MDPs with respect to qualitative properties, and present
discrete graph theoretic algorithms with quadratic complexity to compute the simulation
relation.\r\nWe present an automated technique for assume-guarantee style reasoning
for compositional analysis of MDPs with qualitative properties by giving a counter-example
guided abstraction-refinement approach to compute our new simulation relation.
We have implemented our algorithms and show that the compositional analysis leads
to significant improvements. "
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: Przemyslaw
full_name: Daca, Przemyslaw
id: 49351290-F248-11E8-B48F-1D18A9856A87
last_name: Daca
- first_name: Martin
full_name: Chmelik, Martin
id: 3624234E-F248-11E8-B48F-1D18A9856A87
last_name: Chmelik
citation:
ama: Chatterjee K, Daca P, Chmelik M. CEGAR for Qualitative Analysis of Probabilistic
Systems. IST Austria; 2014. doi:10.15479/AT:IST-2014-153-v2-2
apa: Chatterjee, K., Daca, P., & Chmelik, M. (2014). CEGAR for qualitative
analysis of probabilistic systems. IST Austria. https://doi.org/10.15479/AT:IST-2014-153-v2-2
chicago: Chatterjee, Krishnendu, Przemyslaw Daca, and Martin Chmelik. CEGAR for
Qualitative Analysis of Probabilistic Systems. IST Austria, 2014. https://doi.org/10.15479/AT:IST-2014-153-v2-2.
ieee: K. Chatterjee, P. Daca, and M. Chmelik, CEGAR for qualitative analysis
of probabilistic systems. IST Austria, 2014.
ista: Chatterjee K, Daca P, Chmelik M. 2014. CEGAR for qualitative analysis of probabilistic
systems, IST Austria, 33p.
mla: Chatterjee, Krishnendu, et al. CEGAR for Qualitative Analysis of Probabilistic
Systems. IST Austria, 2014, doi:10.15479/AT:IST-2014-153-v2-2.
short: K. Chatterjee, P. Daca, M. Chmelik, CEGAR for Qualitative Analysis of Probabilistic
Systems, IST Austria, 2014.
date_created: 2018-12-12T11:39:11Z
date_published: 2014-02-06T00:00:00Z
date_updated: 2023-02-23T12:25:18Z
day: '06'
ddc:
- '000'
department:
- _id: KrCh
doi: 10.15479/AT:IST-2014-153-v2-2
file:
- access_level: open_access
checksum: ce4967a184d84863eec76c66cbac1614
content_type: application/pdf
creator: system
date_created: 2018-12-12T11:54:17Z
date_updated: 2020-07-14T12:46:47Z
file_id: '5539'
file_name: IST-2014-153-v2+2_main.pdf
file_size: 606049
relation: main_file
file_date_updated: 2020-07-14T12:46:47Z
has_accepted_license: '1'
language:
- iso: eng
month: '02'
oa: 1
oa_version: Published Version
page: '33'
publication_identifier:
issn:
- 2664-1690
publication_status: published
publisher: IST Austria
pubrep_id: '164'
related_material:
record:
- id: '2063'
relation: later_version
status: public
- id: '5412'
relation: earlier_version
status: public
- id: '5414'
relation: later_version
status: public
status: public
title: CEGAR for qualitative analysis of probabilistic systems
type: technical_report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2014'
...
---
_id: '5414'
abstract:
- lang: eng
text: "We consider Markov decision processes (MDPs) which are a standard model for
probabilistic systems. We focus on qualitative properties for MDPs that can express
that desired behaviors of the system arise almost-surely (with probability 1)
or with positive probability.\r\nWe introduce a new simulation relation to capture
the refinement relation of MDPs with respect to qualitative properties, and present
discrete graph theoretic algorithms with quadratic complexity to compute the simulation
relation.\r\nWe present an automated technique for assume-guarantee style reasoning
for compositional analysis of MDPs with qualitative properties by giving a counter-example
guided abstraction-refinement approach to compute our new simulation relation.
\r\nWe have implemented our algorithms and show that the compositional analysis
leads to significant improvements. "
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: Przemyslaw
full_name: Daca, Przemyslaw
id: 49351290-F248-11E8-B48F-1D18A9856A87
last_name: Daca
- first_name: Martin
full_name: Chmelik, Martin
id: 3624234E-F248-11E8-B48F-1D18A9856A87
last_name: Chmelik
citation:
ama: Chatterjee K, Daca P, Chmelik M. CEGAR for Qualitative Analysis of Probabilistic
Systems. IST Austria; 2014. doi:10.15479/AT:IST-2014-153-v3-1
apa: Chatterjee, K., Daca, P., & Chmelik, M. (2014). CEGAR for qualitative
analysis of probabilistic systems. IST Austria. https://doi.org/10.15479/AT:IST-2014-153-v3-1
chicago: Chatterjee, Krishnendu, Przemyslaw Daca, and Martin Chmelik. CEGAR for
Qualitative Analysis of Probabilistic Systems. IST Austria, 2014. https://doi.org/10.15479/AT:IST-2014-153-v3-1.
ieee: K. Chatterjee, P. Daca, and M. Chmelik, CEGAR for qualitative analysis
of probabilistic systems. IST Austria, 2014.
ista: Chatterjee K, Daca P, Chmelik M. 2014. CEGAR for qualitative analysis of probabilistic
systems, IST Austria, 33p.
mla: Chatterjee, Krishnendu, et al. CEGAR for Qualitative Analysis of Probabilistic
Systems. IST Austria, 2014, doi:10.15479/AT:IST-2014-153-v3-1.
short: K. Chatterjee, P. Daca, M. Chmelik, CEGAR for Qualitative Analysis of Probabilistic
Systems, IST Austria, 2014.
date_created: 2018-12-12T11:39:12Z
date_published: 2014-02-07T00:00:00Z
date_updated: 2023-02-23T12:25:15Z
day: '07'
ddc:
- '000'
department:
- _id: KrCh
doi: 10.15479/AT:IST-2014-153-v3-1
file:
- access_level: open_access
checksum: 87b93fe9af71fc5c94b0eb6151537e11
content_type: application/pdf
creator: system
date_created: 2018-12-12T11:53:03Z
date_updated: 2020-07-14T12:46:48Z
file_id: '5464'
file_name: IST-2014-153-v3+1_main.pdf
file_size: 606227
relation: main_file
file_date_updated: 2020-07-14T12:46:48Z
has_accepted_license: '1'
language:
- iso: eng
month: '02'
oa: 1
oa_version: Published Version
page: '33'
publication_identifier:
issn:
- 2664-1690
publication_status: published
publisher: IST Austria
pubrep_id: '165'
related_material:
record:
- id: '2063'
relation: later_version
status: public
- id: '5412'
relation: earlier_version
status: public
- id: '5413'
relation: earlier_version
status: public
status: public
title: CEGAR for qualitative analysis of probabilistic systems
type: technical_report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2014'
...
---
_id: '5415'
abstract:
- lang: eng
text: 'Recently there has been a significant effort to add quantitative properties
in formal verification and synthesis. While weighted automata over finite and
infinite words provide a natural and flexible framework to express quantitative
properties, perhaps surprisingly, several basic system properties such as average
response time cannot be expressed with weighted automata. In this work, we introduce
nested weighted automata as a new formalism for expressing important quantitative
properties such as average response time. We establish an almost complete decidability
picture for the basic decision problems for nested weighted automata, and illustrate
its applicability in several domains. '
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: 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
citation:
ama: Chatterjee K, Henzinger TA, Otop J. Nested Weighted Automata. IST Austria;
2014. doi:10.15479/AT:IST-2014-170-v1-1
apa: Chatterjee, K., Henzinger, T. A., & Otop, J. (2014). Nested weighted
automata. IST Austria. https://doi.org/10.15479/AT:IST-2014-170-v1-1
chicago: Chatterjee, Krishnendu, Thomas A Henzinger, and Jan Otop. Nested Weighted
Automata. IST Austria, 2014. https://doi.org/10.15479/AT:IST-2014-170-v1-1.
ieee: K. Chatterjee, T. A. Henzinger, and J. Otop, Nested weighted automata.
IST Austria, 2014.
ista: Chatterjee K, Henzinger TA, Otop J. 2014. Nested weighted automata, IST Austria,
27p.
mla: Chatterjee, Krishnendu, et al. Nested Weighted Automata. IST Austria,
2014, doi:10.15479/AT:IST-2014-170-v1-1.
short: K. Chatterjee, T.A. Henzinger, J. Otop, Nested Weighted Automata, IST Austria,
2014.
date_created: 2018-12-12T11:39:12Z
date_published: 2014-02-19T00:00:00Z
date_updated: 2023-02-23T12:26:19Z
day: '19'
ddc:
- '004'
department:
- _id: KrCh
- _id: ToHe
doi: 10.15479/AT:IST-2014-170-v1-1
file:
- access_level: open_access
checksum: 31f90dcf2cf899c3f8c6427cfcc2b3c7
content_type: application/pdf
creator: system
date_created: 2018-12-12T11:53:36Z
date_updated: 2020-07-14T12:46:48Z
file_id: '5497'
file_name: IST-2014-170-v1+1_main.pdf
file_size: 573457
relation: main_file
file_date_updated: 2020-07-14T12:46:48Z
has_accepted_license: '1'
language:
- iso: eng
month: '02'
oa: 1
oa_version: Published Version
page: '27'
publication_identifier:
issn:
- 2664-1690
publication_status: published
publisher: IST Austria
pubrep_id: '170'
related_material:
record:
- id: '1656'
relation: later_version
status: public
- id: '467'
relation: later_version
status: public
- id: '5436'
relation: later_version
status: public
status: public
title: Nested weighted automata
type: technical_report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2014'
...
---
_id: '5416'
abstract:
- lang: eng
text: As hybrid systems involve continuous behaviors, they should be evaluated by
quantitative methods, rather than qualitative methods. In this paper we adapt
a quantitative framework, called model measuring, to the hybrid systems domain.
The model-measuring problem asks, given a model M and a specification, what is
the maximal distance such that all models within that distance from M satisfy
(or violate) the specification. A distance function on models is given as part
of the input of the problem. Distances, especially related to continuous behaviors
are more natural in the hybrid case than the discrete case. We are interested
in distances represented by monotonic hybrid automata, a hybrid counterpart of
(discrete) weighted automata, whose recognized timed languages are monotone (w.r.t.
inclusion) in the values of parameters.The contributions of this paper are twofold.
First, we give sufficient conditions under which the model-measuring problem can
be solved. Second, we discuss the modeling of distances and applications of the
model-measuring problem.
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: Jan
full_name: Otop, Jan
id: 2FC5DA74-F248-11E8-B48F-1D18A9856A87
last_name: Otop
citation:
ama: Henzinger TA, Otop J. Model Measuring for Hybrid Systems. IST Austria;
2014. doi:10.15479/AT:IST-2014-171-v1-1
apa: Henzinger, T. A., & Otop, J. (2014). Model measuring for hybrid systems.
IST Austria. https://doi.org/10.15479/AT:IST-2014-171-v1-1
chicago: Henzinger, Thomas A, and Jan Otop. Model Measuring for Hybrid Systems.
IST Austria, 2014. https://doi.org/10.15479/AT:IST-2014-171-v1-1.
ieee: T. A. Henzinger and J. Otop, Model measuring for hybrid systems. IST
Austria, 2014.
ista: Henzinger TA, Otop J. 2014. Model measuring for hybrid systems, IST Austria,
22p.
mla: Henzinger, Thomas A., and Jan Otop. Model Measuring for Hybrid Systems.
IST Austria, 2014, doi:10.15479/AT:IST-2014-171-v1-1.
short: T.A. Henzinger, J. Otop, Model Measuring for Hybrid Systems, IST Austria,
2014.
date_created: 2018-12-12T11:39:12Z
date_published: 2014-02-19T00:00:00Z
date_updated: 2023-02-23T10:33:21Z
day: '19'
ddc:
- '005'
department:
- _id: ToHe
doi: 10.15479/AT:IST-2014-171-v1-1
file:
- access_level: open_access
checksum: 445456d22371e4e49aad2b9a0c13bf80
content_type: application/pdf
creator: system
date_created: 2018-12-12T11:53:32Z
date_updated: 2020-07-14T12:46:49Z
file_id: '5492'
file_name: IST-2014-171-v1+1_report.pdf
file_size: 712077
relation: main_file
file_date_updated: 2020-07-14T12:46:49Z
has_accepted_license: '1'
language:
- iso: eng
month: '02'
oa: 1
oa_version: Published Version
page: '22'
publication_identifier:
issn:
- 2664-1690
publication_status: published
publisher: IST Austria
pubrep_id: '171'
related_material:
record:
- id: '2217'
relation: later_version
status: public
status: public
title: Model measuring for hybrid systems
type: technical_report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2014'
...
---
_id: '5417'
abstract:
- lang: eng
text: "We define the model-measuring problem: given a model M and specification
φ, what is the maximal distance ρ such that all models M'within distance ρ from
M satisfy (or violate)φ. The model measuring problem presupposes a distance function
on models. We concentrate on automatic distance functions, which are defined by
weighted automata.\r\nThe model-measuring problem subsumes several generalizations
of the classical model-checking problem, in particular, quantitative model-checking
problems that measure the degree of satisfaction of a specification, and robustness
problems that measure how much a model can be perturbed without violating the
specification.\r\nWe show that for automatic distance functions, and ω-regular
linear-time and branching-time specifications, the model-measuring problem can
be solved.\r\nWe use automata-theoretic model-checking methods for model measuring,
replacing the emptiness question for standard word and tree automata by the optimal-weight
question for the weighted versions of these automata. We consider weighted automata
that accumulate weights by maximizing, summing, discounting, and limit averaging.
\r\nWe give several examples of using the model-measuring problem to compute various
notions of robustness and quantitative satisfaction for temporal specifications."
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: Jan
full_name: Otop, Jan
id: 2FC5DA74-F248-11E8-B48F-1D18A9856A87
last_name: Otop
citation:
ama: Henzinger TA, Otop J. From Model Checking to Model Measuring. IST Austria;
2014. doi:10.15479/AT:IST-2014-172-v1-1
apa: Henzinger, T. A., & Otop, J. (2014). From model checking to model measuring.
IST Austria. https://doi.org/10.15479/AT:IST-2014-172-v1-1
chicago: Henzinger, Thomas A, and Jan Otop. From Model Checking to Model Measuring.
IST Austria, 2014. https://doi.org/10.15479/AT:IST-2014-172-v1-1.
ieee: T. A. Henzinger and J. Otop, From model checking to model measuring.
IST Austria, 2014.
ista: Henzinger TA, Otop J. 2014. From model checking to model measuring, IST Austria,
14p.
mla: Henzinger, Thomas A., and Jan Otop. From Model Checking to Model Measuring.
IST Austria, 2014, doi:10.15479/AT:IST-2014-172-v1-1.
short: T.A. Henzinger, J. Otop, From Model Checking to Model Measuring, IST Austria,
2014.
date_created: 2018-12-12T11:39:13Z
date_published: 2014-02-19T00:00:00Z
date_updated: 2023-02-23T10:38:10Z
day: '19'
ddc:
- '000'
department:
- _id: ToHe
doi: 10.15479/AT:IST-2014-172-v1-1
file:
- access_level: open_access
checksum: fcc3eab903cfcd3778b338d2d0d44d18
content_type: application/pdf
creator: system
date_created: 2018-12-12T11:53:20Z
date_updated: 2020-07-14T12:46:49Z
file_id: '5481'
file_name: IST-2014-172-v1+1_report.pdf
file_size: 383052
relation: main_file
file_date_updated: 2020-07-14T12:46:49Z
has_accepted_license: '1'
language:
- iso: eng
month: '02'
oa: 1
oa_version: Published Version
page: '14'
publication_identifier:
issn:
- 2664-1690
publication_status: published
publisher: IST Austria
pubrep_id: '175'
related_material:
record:
- id: '2327'
relation: later_version
status: public
status: public
title: From model checking to model measuring
type: technical_report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2014'
...
---
_id: '5418'
abstract:
- lang: eng
text: We consider multi-player graph games with partial-observation and parity objective.
While the decision problem for three-player games with a coalition of the first
and second players against the third player is undecidable, we present a decidability
result for partial-observation games where the first and third player are in a
coalition against the second player, thus where the second player is adversarial
but weaker due to partial-observation. We establish tight complexity bounds in
the case where player 1 is less informed than player 2, namely 2-EXPTIME-completeness
for parity objectives. The symmetric case of player 1 more informed than player
2 is much more complicated, and we show that already in the case where player
1 has perfect observation, memory of size non-elementary is necessary in general
for reachability objectives, and the problem is decidable for safety and reachability
objectives. Our results have tight connections with partial-observation stochastic
games for which we derive new complexity results.
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: Laurent
full_name: Doyen, Laurent
last_name: Doyen
citation:
ama: Chatterjee K, Doyen L. Games with a Weak Adversary. IST Austria; 2014.
doi:10.15479/AT:IST-2014-176-v1-1
apa: Chatterjee, K., & Doyen, L. (2014). Games with a weak adversary.
IST Austria. https://doi.org/10.15479/AT:IST-2014-176-v1-1
chicago: Chatterjee, Krishnendu, and Laurent Doyen. Games with a Weak Adversary.
IST Austria, 2014. https://doi.org/10.15479/AT:IST-2014-176-v1-1.
ieee: K. Chatterjee and L. Doyen, Games with a weak adversary. IST Austria,
2014.
ista: Chatterjee K, Doyen L. 2014. Games with a weak adversary, IST Austria, 18p.
mla: Chatterjee, Krishnendu, and Laurent Doyen. Games with a Weak Adversary.
IST Austria, 2014, doi:10.15479/AT:IST-2014-176-v1-1.
short: K. Chatterjee, L. Doyen, Games with a Weak Adversary, IST Austria, 2014.
date_created: 2018-12-12T11:39:13Z
date_published: 2014-03-22T00:00:00Z
date_updated: 2023-02-23T10:30:58Z
day: '22'
ddc:
- '000'
- '005'
department:
- _id: KrCh
doi: 10.15479/AT:IST-2014-176-v1-1
file:
- access_level: open_access
checksum: 1d6958aa60050e1c3e932c6e5f34c39f
content_type: application/pdf
creator: system
date_created: 2018-12-12T11:53:07Z
date_updated: 2020-07-14T12:46:49Z
file_id: '5468'
file_name: IST-2014-176-v1+1_icalp_14.pdf
file_size: 328253
relation: main_file
file_date_updated: 2020-07-14T12:46:49Z
has_accepted_license: '1'
language:
- iso: eng
month: '03'
oa: 1
oa_version: Published Version
page: '18'
publication_identifier:
issn:
- 2664-1690
publication_status: published
publisher: IST Austria
pubrep_id: '176'
related_material:
record:
- id: '2163'
relation: later_version
status: public
status: public
title: Games with a weak adversary
type: technical_report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2014'
...
---
_id: '5419'
abstract:
- lang: eng
text: "We consider the reachability and shortest path problems on low tree-width
graphs, with n nodes, m edges, and tree-width t, on a standard RAM with wordsize
W. We use O to hide polynomial factors of the inverse of the Ackermann function.
Our main contributions are three fold:\r\n1. For reachability, we present an algorithm
that requires O(n·t2·log(n/t)) preprocessing time, O(n·(t·log(n/t))/W) space,
and O(t/W) time for pair queries and O((n·t)/W) time for single-source queries.
Note that for constant t our algorithm uses O(n·logn) time for preprocessing;
and O(n/W) time for single-source queries, which is faster than depth first search/breath
first search (after the preprocessing).\r\n2. We present an algorithm for shortest
path that requires O(n·t2) preprocessing time, O(n·t) space, and O(t2) time for
pair queries and O(n·t) time single-source queries.\r\n3. We give a space versus
query time trade-off algorithm for shortest path that, given any constant >0,
requires O(n·t2) preprocessing time, O(n·t2) space, and O(n1−·t2) time for pair
queries.\r\nOur algorithms improve all existing results, and use very simple data
structures."
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
- 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, Ibsen-Jensen R, Pavlogiannis A. Improved Algorithms for Reachability
and Shortest Path on Low Tree-Width Graphs. IST Austria; 2014. doi:10.15479/AT:IST-2014-187-v1-1
apa: Chatterjee, K., Ibsen-Jensen, R., & Pavlogiannis, A. (2014). Improved
algorithms for reachability and shortest path on low tree-width graphs. IST
Austria. https://doi.org/10.15479/AT:IST-2014-187-v1-1
chicago: Chatterjee, Krishnendu, Rasmus Ibsen-Jensen, and Andreas Pavlogiannis.
Improved Algorithms for Reachability and Shortest Path on Low Tree-Width Graphs.
IST Austria, 2014. https://doi.org/10.15479/AT:IST-2014-187-v1-1.
ieee: K. Chatterjee, R. Ibsen-Jensen, and A. Pavlogiannis, Improved algorithms
for reachability and shortest path on low tree-width graphs. IST Austria,
2014.
ista: Chatterjee K, Ibsen-Jensen R, Pavlogiannis A. 2014. Improved algorithms for
reachability and shortest path on low tree-width graphs, IST Austria, 34p.
mla: Chatterjee, Krishnendu, et al. Improved Algorithms for Reachability and
Shortest Path on Low Tree-Width Graphs. IST Austria, 2014, doi:10.15479/AT:IST-2014-187-v1-1.
short: K. Chatterjee, R. Ibsen-Jensen, A. Pavlogiannis, Improved Algorithms for
Reachability and Shortest Path on Low Tree-Width Graphs, IST Austria, 2014.
date_created: 2018-12-12T11:39:13Z
date_published: 2014-04-14T00:00:00Z
date_updated: 2021-01-12T08:02:03Z
day: '14'
ddc:
- '000'
department:
- _id: KrCh
doi: 10.15479/AT:IST-2014-187-v1-1
file:
- access_level: open_access
checksum: c608e66030a4bf51d2d99b451f539b99
content_type: application/pdf
creator: system
date_created: 2018-12-12T11:54:25Z
date_updated: 2020-07-14T12:46:50Z
file_id: '5548'
file_name: IST-2014-187-v1+1_main_full_tech.pdf
file_size: 670031
relation: main_file
file_date_updated: 2020-07-14T12:46:50Z
has_accepted_license: '1'
language:
- iso: eng
month: '04'
oa: 1
oa_version: Published Version
page: '34'
publication_identifier:
issn:
- 2664-1690
publication_status: published
publisher: IST Austria
pubrep_id: '187'
status: public
title: Improved algorithms for reachability and shortest path on low tree-width graphs
type: technical_report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2014'
...
---
_id: '5420'
abstract:
- lang: eng
text: 'We consider concurrent mean-payoff games, a very well-studied class of two-player
(player 1 vs player 2) zero-sum games on finite-state graphs where every transition
is assigned a reward between 0 and 1, and the payoff function is the long-run
average of the rewards. The value is the maximal expected payoff that player 1
can guarantee against all strategies of player 2. We consider the computation
of the set of states with value 1 under finite-memory strategies for player 1,
and our main results for the problem are as follows: (1) we present a polynomial-time
algorithm; (2) we show that whenever there is a finite-memory strategy, there
is a stationary strategy that does not need memory at all; and (3) we present
an optimal bound (which is double exponential) 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).'
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 Value 1 Problem for Concurrent Mean-Payoff
Games. IST Austria; 2014. doi:10.15479/AT:IST-2014-191-v1-1
apa: Chatterjee, K., & Ibsen-Jensen, R. (2014). The value 1 problem for concurrent
mean-payoff games. IST Austria. https://doi.org/10.15479/AT:IST-2014-191-v1-1
chicago: Chatterjee, Krishnendu, and Rasmus Ibsen-Jensen. The Value 1 Problem
for Concurrent Mean-Payoff Games. IST Austria, 2014. https://doi.org/10.15479/AT:IST-2014-191-v1-1.
ieee: K. Chatterjee and R. Ibsen-Jensen, The value 1 problem for concurrent mean-payoff
games. IST Austria, 2014.
ista: Chatterjee K, Ibsen-Jensen R. 2014. The value 1 problem for concurrent mean-payoff
games, IST Austria, 49p.
mla: Chatterjee, Krishnendu, and Rasmus Ibsen-Jensen. The Value 1 Problem for
Concurrent Mean-Payoff Games. IST Austria, 2014, doi:10.15479/AT:IST-2014-191-v1-1.
short: K. Chatterjee, R. Ibsen-Jensen, The Value 1 Problem for Concurrent Mean-Payoff
Games, IST Austria, 2014.
date_created: 2018-12-12T11:39:14Z
date_published: 2014-04-14T00:00:00Z
date_updated: 2021-01-12T08:02:05Z
day: '14'
ddc:
- '000'
- '005'
department:
- _id: KrCh
doi: 10.15479/AT:IST-2014-191-v1-1
file:
- access_level: open_access
checksum: 49e0fd3e62650346daf7dc04604f7a0a
content_type: application/pdf
creator: system
date_created: 2018-12-12T11:53:58Z
date_updated: 2020-07-14T12:46:50Z
file_id: '5520'
file_name: IST-2014-191-v1+1_main_full.pdf
file_size: 584368
relation: main_file
file_date_updated: 2020-07-14T12:46:50Z
has_accepted_license: '1'
language:
- iso: eng
month: '04'
oa: 1
oa_version: Published Version
page: '49'
publication_identifier:
issn:
- 2664-1690
publication_status: published
publisher: IST Austria
pubrep_id: '191'
status: public
title: The value 1 problem for concurrent mean-payoff games
type: technical_report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2014'
...