---
_id: '14417'
abstract:
- lang: eng
text: Entropic risk (ERisk) is an established risk measure in finance, quantifying
risk by an exponential re-weighting of rewards. We study ERisk for the first time
in the context of turn-based stochastic games with the total reward objective.
This gives rise to an objective function that demands the control of systems in
a risk-averse manner. We show that the resulting games are determined and, in
particular, admit optimal memoryless deterministic strategies. This contrasts
risk measures that previously have been considered in the special case of Markov
decision processes and that require randomization and/or memory. We provide several
results on the decidability and the computational complexity of the threshold
problem, i.e. whether the optimal value of ERisk exceeds a given threshold. In
the most general case, the problem is decidable subject to Shanuel’s conjecture.
If all inputs are rational, the resulting threshold problem can be solved using
algebraic numbers, leading to decidability via a polynomial-time reduction to
the existential theory of the reals. Further restrictions on the encoding of the
input allow the solution of the threshold problem in NP∩coNP. Finally, an approximation
algorithm for the optimal value of ERisk is provided.
acknowledgement: "This work was partly funded by the ERC CoG 863818 (ForM-SMArt),
the DFG Grant\r\n389792660 as part of TRR 248 (Foundations of Perspicuous Software
Systems), the Cluster of\r\nExcellence EXC 2050/1 (CeTI, project ID 390696704, as
part of Germany’s Excellence Strategy), and the DFG projects BA-1679/11-1 and BA-1679/12-1."
alternative_title:
- LIPIcs
article_number: '15'
article_processing_charge: Yes
arxiv: 1
author:
- first_name: Christel
full_name: Baier, Christel
last_name: Baier
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Tobias
full_name: Meggendorfer, Tobias
id: b21b0c15-30a2-11eb-80dc-f13ca25802e1
last_name: Meggendorfer
orcid: 0000-0002-1712-2165
- first_name: Jakob
full_name: Piribauer, Jakob
last_name: Piribauer
citation:
ama: 'Baier C, Chatterjee K, Meggendorfer T, Piribauer J. Entropic risk for turn-based
stochastic games. In: 48th International Symposium on Mathematical Foundations
of Computer Science. Vol 272. Schloss Dagstuhl - Leibniz-Zentrum für Informatik;
2023. doi:10.4230/LIPIcs.MFCS.2023.15'
apa: 'Baier, C., Chatterjee, K., Meggendorfer, T., & Piribauer, J. (2023). Entropic
risk for turn-based stochastic games. In 48th International Symposium on Mathematical
Foundations of Computer Science (Vol. 272). Bordeaux, France: Schloss Dagstuhl
- Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.MFCS.2023.15'
chicago: Baier, Christel, Krishnendu Chatterjee, Tobias Meggendorfer, and Jakob
Piribauer. “Entropic Risk for Turn-Based Stochastic Games.” In 48th International
Symposium on Mathematical Foundations of Computer Science, Vol. 272. Schloss
Dagstuhl - Leibniz-Zentrum für Informatik, 2023. https://doi.org/10.4230/LIPIcs.MFCS.2023.15.
ieee: C. Baier, K. Chatterjee, T. Meggendorfer, and J. Piribauer, “Entropic risk
for turn-based stochastic games,” in 48th International Symposium on Mathematical
Foundations of Computer Science, Bordeaux, France, 2023, vol. 272.
ista: 'Baier C, Chatterjee K, Meggendorfer T, Piribauer J. 2023. Entropic risk for
turn-based stochastic games. 48th International Symposium on Mathematical Foundations
of Computer Science. MFCS: Symposium on Mathematical Foundations of Computer Science,
LIPIcs, vol. 272, 15.'
mla: Baier, Christel, et al. “Entropic Risk for Turn-Based Stochastic Games.” 48th
International Symposium on Mathematical Foundations of Computer Science, vol.
272, 15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023, doi:10.4230/LIPIcs.MFCS.2023.15.
short: C. Baier, K. Chatterjee, T. Meggendorfer, J. Piribauer, in:, 48th International
Symposium on Mathematical Foundations of Computer Science, Schloss Dagstuhl -
Leibniz-Zentrum für Informatik, 2023.
conference:
end_date: 2023-09-01
location: Bordeaux, France
name: 'MFCS: Symposium on Mathematical Foundations of Computer Science'
start_date: 2023-08-28
date_created: 2023-10-09T09:21:05Z
date_published: 2023-08-21T00:00:00Z
date_updated: 2025-07-14T09:09:57Z
day: '21'
ddc:
- '000'
department:
- _id: KrCh
doi: 10.4230/LIPIcs.MFCS.2023.15
ec_funded: 1
external_id:
arxiv:
- '2307.06611'
file:
- access_level: open_access
checksum: 402281b17ed669bbf149d0fdf68ac201
content_type: application/pdf
creator: dernst
date_created: 2023-10-09T09:19:11Z
date_updated: 2023-10-09T09:19:11Z
file_id: '14418'
file_name: 2023_LIPIcsMFCS_Baier.pdf
file_size: 826843
relation: main_file
success: 1
file_date_updated: 2023-10-09T09:19:11Z
has_accepted_license: '1'
intvolume: ' 272'
language:
- iso: eng
month: '08'
oa: 1
oa_version: Published Version
project:
- _id: 0599E47C-7A3F-11EA-A408-12923DDC885E
call_identifier: H2020
grant_number: '863818'
name: 'Formal Methods for Stochastic Models: Algorithms and Applications'
publication: 48th International Symposium on Mathematical Foundations of Computer
Science
publication_identifier:
eissn:
- 1868-8969
isbn:
- '9783959772921'
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Entropic risk for turn-based stochastic 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: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 272
year: '2023'
...
---
_id: '13120'
abstract:
- lang: eng
text: 'We formalized general (i.e., type-0) grammars using the Lean 3 proof assistant.
We defined basic notions of rewrite rules and of words derived by a grammar, and
used grammars to show closure of the class of type-0 languages under four operations:
union, reversal, concatenation, and the Kleene star. The literature mostly focuses
on Turing machine arguments, which are possibly more difficult to formalize. For
the Kleene star, we could not follow the literature and came up with our own grammar-based
construction.'
acknowledgement: "Jasmin Blanchette: This research has received funding from the Netherlands
Organization\r\nfor Scientific Research (NWO) under the Vidi program (project No.
016.Vidi.189.037, Lean Forward).\r\n__\r\nWe thank Vladimir Kolmogorov for making
this collaboration possible. We\r\nthank Václav Končický for discussing ideas about
the Kleene star construction. We thank Patrick Johnson, Floris van Doorn, and Damiano
Testa for their small yet very valuable contributions to our code. We thank Eric
Wieser for simplifying one of our proofs. We thank Mark Summerfield for suggesting
textual improvements. We thank the anonymous reviewers for very helpful comments.
Finally, we thank the Lean community for helping us with various technical issues
and answering many questions. "
alternative_title:
- LIPIcs
article_number: '15'
article_processing_charge: No
arxiv: 1
author:
- first_name: Martin
full_name: Dvorak, Martin
id: 40ED02A8-C8B4-11E9-A9C0-453BE6697425
last_name: Dvorak
orcid: 0000-0001-5293-214X
- first_name: Jasmin
full_name: Blanchette, Jasmin
last_name: Blanchette
citation:
ama: 'Dvorak M, Blanchette J. Closure properties of general grammars - formally
verified. In: 14th International Conference on Interactive Theorem Proving.
Vol 268. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2023. doi:10.4230/LIPIcs.ITP.2023.15'
apa: 'Dvorak, M., & Blanchette, J. (2023). Closure properties of general grammars
- formally verified. In 14th International Conference on Interactive Theorem
Proving (Vol. 268). Bialystok, Poland: Schloss Dagstuhl - Leibniz-Zentrum
für Informatik. https://doi.org/10.4230/LIPIcs.ITP.2023.15'
chicago: Dvorak, Martin, and Jasmin Blanchette. “Closure Properties of General Grammars
- Formally Verified.” In 14th International Conference on Interactive Theorem
Proving, Vol. 268. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023.
https://doi.org/10.4230/LIPIcs.ITP.2023.15.
ieee: M. Dvorak and J. Blanchette, “Closure properties of general grammars - formally
verified,” in 14th International Conference on Interactive Theorem Proving,
Bialystok, Poland, 2023, vol. 268.
ista: 'Dvorak M, Blanchette J. 2023. Closure properties of general grammars - formally
verified. 14th International Conference on Interactive Theorem Proving. ITP: International
Conference on Interactive Theorem Proving, LIPIcs, vol. 268, 15.'
mla: Dvorak, Martin, and Jasmin Blanchette. “Closure Properties of General Grammars
- Formally Verified.” 14th International Conference on Interactive Theorem
Proving, vol. 268, 15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2023, doi:10.4230/LIPIcs.ITP.2023.15.
short: M. Dvorak, J. Blanchette, in:, 14th International Conference on Interactive
Theorem Proving, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023.
conference:
end_date: 2023-08-04
location: Bialystok, Poland
name: 'ITP: International Conference on Interactive Theorem Proving'
start_date: 2023-07-31
date_created: 2023-06-05T07:29:05Z
date_published: 2023-07-27T00:00:00Z
date_updated: 2023-09-25T11:04:29Z
day: '27'
ddc:
- '000'
department:
- _id: GradSch
- _id: VlKo
doi: 10.4230/LIPIcs.ITP.2023.15
external_id:
arxiv:
- '2302.06420'
file:
- access_level: open_access
checksum: 773a0197f05b67feaa6cb1e17ec3642d
content_type: application/pdf
creator: dernst
date_created: 2023-08-07T11:55:43Z
date_updated: 2023-08-07T11:55:43Z
file_id: '13982'
file_name: 2023_LIPIcS_Dvorak.pdf
file_size: 715976
relation: main_file
success: 1
file_date_updated: 2023-08-07T11:55:43Z
has_accepted_license: '1'
intvolume: ' 268'
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
publication: 14th International Conference on Interactive Theorem Proving
publication_identifier:
eissn:
- 1868-8969
isbn:
- '9783959772846'
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
related_material:
link:
- relation: software
url: https://github.com/madvorak/grammars/tree/publish
scopus_import: '1'
status: public
title: Closure properties of general grammars - formally verified
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: 268
year: '2023'
...
---
_id: '13221'
abstract:
- lang: eng
text: The safety-liveness dichotomy is a fundamental concept in formal languages
which plays a key role in verification. Recently, this dichotomy has been lifted
to quantitative properties, which are arbitrary functions from infinite words
to partially-ordered domains. We look into harnessing the dichotomy for the specific
classes of quantitative properties expressed by quantitative automata. These automata
contain finitely many states and rational-valued transition weights, and their
common value functions Inf, Sup, LimInf, LimSup, LimInfAvg, LimSupAvg, and DSum
map infinite words into the totallyordered domain of real numbers. In this automata-theoretic
setting, we establish a connection between quantitative safety and topological
continuity and provide an alternative characterization of quantitative safety
and liveness in terms of their boolean counterparts. For all common value functions,
we show how the safety closure of a quantitative automaton can be constructed
in PTime, and we provide PSpace-complete checks of whether a given quantitative
automaton is safe or live, with the exception of LimInfAvg and LimSupAvg automata,
for which the safety check is in ExpSpace. Moreover, for deterministic Sup, LimInf,
and LimSup automata, we give PTime decompositions into safe and live automata.
These decompositions enable the separation of techniques for safety and liveness
verification for quantitative specifications.
acknowledgement: We thank Christof Löding for pointing us to some results on PSpace-hardess
of universality problems and the anonymous reviewers for their helpful comments.
This work was supported in part by the ERC-2020-AdG 101020093 and the Israel Science
Foundation grant 2410/22.
alternative_title:
- LIPIcs
article_number: '17'
article_processing_charge: No
arxiv: 1
author:
- first_name: Udi
full_name: Boker, Udi
id: 31E297B6-F248-11E8-B48F-1D18A9856A87
last_name: Boker
- 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: Nicolas Adrien
full_name: Mazzocchi, Nicolas Adrien
id: b26baa86-3308-11ec-87b0-8990f34baa85
last_name: Mazzocchi
- first_name: Naci E
full_name: Sarac, Naci E
id: 8C6B42F8-C8E6-11E9-A03A-F2DCE5697425
last_name: Sarac
citation:
ama: 'Boker U, Henzinger TA, Mazzocchi NA, Sarac NE. Safety and liveness of quantitative
automata. In: 34th International Conference on Concurrency Theory. Vol
279. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2023. doi:10.4230/LIPIcs.CONCUR.2023.17'
apa: 'Boker, U., Henzinger, T. A., Mazzocchi, N. A., & Sarac, N. E. (2023).
Safety and liveness of quantitative automata. In 34th International Conference
on Concurrency Theory (Vol. 279). Antwerp, Belgium: Schloss Dagstuhl - Leibniz-Zentrum
für Informatik. https://doi.org/10.4230/LIPIcs.CONCUR.2023.17'
chicago: Boker, Udi, Thomas A Henzinger, Nicolas Adrien Mazzocchi, and Naci E Sarac.
“Safety and Liveness of Quantitative Automata.” In 34th International Conference
on Concurrency Theory, Vol. 279. Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2023. https://doi.org/10.4230/LIPIcs.CONCUR.2023.17.
ieee: U. Boker, T. A. Henzinger, N. A. Mazzocchi, and N. E. Sarac, “Safety and liveness
of quantitative automata,” in 34th International Conference on Concurrency
Theory, Antwerp, Belgium, 2023, vol. 279.
ista: 'Boker U, Henzinger TA, Mazzocchi NA, Sarac NE. 2023. Safety and liveness
of quantitative automata. 34th International Conference on Concurrency Theory.
CONCUR: Conference on Concurrency Theory, LIPIcs, vol. 279, 17.'
mla: Boker, Udi, et al. “Safety and Liveness of Quantitative Automata.” 34th
International Conference on Concurrency Theory, vol. 279, 17, Schloss Dagstuhl
- Leibniz-Zentrum für Informatik, 2023, doi:10.4230/LIPIcs.CONCUR.2023.17.
short: U. Boker, T.A. Henzinger, N.A. Mazzocchi, N.E. Sarac, in:, 34th International
Conference on Concurrency Theory, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2023.
conference:
end_date: 2023-09-23
location: Antwerp, Belgium
name: 'CONCUR: Conference on Concurrency Theory'
start_date: 2023-09-18
date_created: 2023-07-14T10:00:15Z
date_published: 2023-09-01T00:00:00Z
date_updated: 2023-10-09T07:14:03Z
day: '01'
ddc:
- '000'
department:
- _id: GradSch
- _id: ToHe
doi: 10.4230/LIPIcs.CONCUR.2023.17
ec_funded: 1
external_id:
arxiv:
- '2307.06016'
file:
- access_level: open_access
checksum: d40e57a04448ea5c77d7e1cfb9590a81
content_type: application/pdf
creator: esarac
date_created: 2023-07-14T12:03:48Z
date_updated: 2023-07-14T12:03:48Z
file_id: '13224'
file_name: CONCUR23.pdf
file_size: 755529
relation: main_file
success: 1
file_date_updated: 2023-07-14T12:03:48Z
has_accepted_license: '1'
intvolume: ' 279'
language:
- iso: eng
month: '09'
oa: 1
oa_version: Published Version
project:
- _id: 62781420-2b32-11ec-9570-8d9b63373d4d
call_identifier: H2020
grant_number: '101020093'
name: Vigilant Algorithmic Monitoring of Software
publication: 34th International Conference on Concurrency Theory
publication_identifier:
eissn:
- 1868-8969
isbn:
- '9783959772990'
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
status: public
title: Safety and liveness of quantitative automata
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: 279
year: '2023'
...
---
_id: '13292'
abstract:
- lang: eng
text: The operator precedence languages (OPLs) represent the largest known subclass
of the context-free languages which enjoys all desirable closure and decidability
properties. This includes the decidability of language inclusion, which is the
ultimate verification problem. Operator precedence grammars, automata, and logics
have been investigated and used, for example, to verify programs with arithmetic
expressions and exceptions (both of which are deterministic pushdown but lie outside
the scope of the visibly pushdown languages). In this paper, we complete the picture
and give, for the first time, an algebraic characterization of the class of OPLs
in the form of a syntactic congruence that has finitely many equivalence classes
exactly for the operator precedence languages. This is a generalization of the
celebrated Myhill-Nerode theorem for the regular languages to OPLs. As one of
the consequences, we show that universality and language inclusion for nondeterministic
operator precedence automata can be solved by an antichain algorithm. Antichain
algorithms avoid determinization and complementation through an explicit subset
construction, by leveraging a quasi-order on words, which allows the pruning of
the search space for counterexample words without sacrificing completeness. Antichain
algorithms can be implemented symbolically, and these implementations are today
the best-performing algorithms in practice for the inclusion of finite automata.
We give a generic construction of the quasi-order needed for antichain algorithms
from a finite syntactic congruence. This yields the first antichain algorithm
for OPLs, an algorithm that solves the ExpTime-hard language inclusion problem
for OPLs in exponential time.
acknowledgement: "This work was supported in part by the ERC-2020-AdG 101020093.\r\nWe
thank Pierre Ganty for early discussions and the anonymous reviewers for their helpful
comments.\r\n"
alternative_title:
- LIPIcs
article_processing_charge: Yes
arxiv: 1
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: Pavol
full_name: Kebis, Pavol
last_name: Kebis
- first_name: Nicolas Adrien
full_name: Mazzocchi, Nicolas Adrien
id: b26baa86-3308-11ec-87b0-8990f34baa85
last_name: Mazzocchi
- first_name: Naci E
full_name: Sarac, Naci E
id: 8C6B42F8-C8E6-11E9-A03A-F2DCE5697425
last_name: Sarac
citation:
ama: 'Henzinger TA, Kebis P, Mazzocchi NA, Sarac NE. Regular methods for operator
precedence languages. In: 50th International Colloquium on Automata, Languages,
and Programming. Vol 261. Schloss Dagstuhl - Leibniz-Zentrum für Informatik;
2023:129:1--129:20. doi:10.4230/LIPIcs.ICALP.2023.129'
apa: 'Henzinger, T. A., Kebis, P., Mazzocchi, N. A., & Sarac, N. E. (2023).
Regular methods for operator precedence languages. In 50th International Colloquium
on Automata, Languages, and Programming (Vol. 261, p. 129:1--129:20). Paderborn,
Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ICALP.2023.129'
chicago: Henzinger, Thomas A, Pavol Kebis, Nicolas Adrien Mazzocchi, and Naci E
Sarac. “Regular Methods for Operator Precedence Languages.” In 50th International
Colloquium on Automata, Languages, and Programming, 261:129:1--129:20. Schloss
Dagstuhl - Leibniz-Zentrum für Informatik, 2023. https://doi.org/10.4230/LIPIcs.ICALP.2023.129.
ieee: T. A. Henzinger, P. Kebis, N. A. Mazzocchi, and N. E. Sarac, “Regular methods
for operator precedence languages,” in 50th International Colloquium on Automata,
Languages, and Programming, Paderborn, Germany, 2023, vol. 261, p. 129:1--129:20.
ista: 'Henzinger TA, Kebis P, Mazzocchi NA, Sarac NE. 2023. Regular methods for
operator precedence languages. 50th International Colloquium on Automata, Languages,
and Programming. ICALP: International Colloquium on Automata, Languages, and Programming,
LIPIcs, vol. 261, 129:1--129:20.'
mla: Henzinger, Thomas A., et al. “Regular Methods for Operator Precedence Languages.”
50th International Colloquium on Automata, Languages, and Programming,
vol. 261, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023, p. 129:1--129:20,
doi:10.4230/LIPIcs.ICALP.2023.129.
short: T.A. Henzinger, P. Kebis, N.A. Mazzocchi, N.E. Sarac, in:, 50th International
Colloquium on Automata, Languages, and Programming, Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2023, p. 129:1--129:20.
conference:
end_date: 2023-07-14
location: Paderborn, Germany
name: 'ICALP: International Colloquium on Automata, Languages, and Programming'
start_date: 2023-07-10
date_created: 2023-07-24T15:11:41Z
date_published: 2023-07-05T00:00:00Z
date_updated: 2023-07-31T08:38:38Z
day: '05'
ddc:
- '000'
department:
- _id: GradSch
- _id: ToHe
doi: 10.4230/LIPIcs.ICALP.2023.129
ec_funded: 1
external_id:
arxiv:
- '2305.03447'
file:
- access_level: open_access
checksum: 5d4c8932ef3450615a53b9bb15d92eb2
content_type: application/pdf
creator: esarac
date_created: 2023-07-24T15:11:05Z
date_updated: 2023-07-24T15:11:05Z
file_id: '13293'
file_name: icalp23.pdf
file_size: 859379
relation: main_file
success: 1
file_date_updated: 2023-07-24T15:11:05Z
has_accepted_license: '1'
intvolume: ' 261'
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
page: 129:1--129:20
project:
- _id: 62781420-2b32-11ec-9570-8d9b63373d4d
call_identifier: H2020
grant_number: '101020093'
name: Vigilant Algorithmic Monitoring of Software
publication: 50th International Colloquium on Automata, Languages, and Programming
publication_identifier:
eissn:
- 1868-8969
isbn:
- '9783959772785'
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
status: public
title: Regular methods for operator precedence languages
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: 261
year: '2023'
...
---
_id: '11808'
abstract:
- lang: eng
text: In recent years, significant advances have been made in the design and analysis
of fully dynamic algorithms. However, these theoretical results have received
very little attention from the practical perspective. Few of the algorithms are
implemented and tested on real datasets, and their practical potential is far
from understood. Here, we present a quick reference guide to recent engineering
and theory results in the area of fully dynamic graph algorithms.
alternative_title:
- LIPIcs
article_number: '1'
article_processing_charge: No
arxiv: 1
author:
- first_name: Kathrin
full_name: Hanauer, Kathrin
last_name: Hanauer
- 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: Christian
full_name: Schulz, Christian
last_name: Schulz
citation:
ama: 'Hanauer K, Henzinger MH, Schulz C. Recent advances in fully dynamic graph
algorithms. In: 1st Symposium on Algorithmic Foundations of Dynamic Networks.
Vol 221. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2022. doi:10.4230/LIPIcs.SAND.2022.1'
apa: 'Hanauer, K., Henzinger, M. H., & Schulz, C. (2022). Recent advances in
fully dynamic graph algorithms. In 1st Symposium on Algorithmic Foundations
of Dynamic Networks (Vol. 221). Virtual: Schloss Dagstuhl - Leibniz-Zentrum
für Informatik. https://doi.org/10.4230/LIPIcs.SAND.2022.1'
chicago: Hanauer, Kathrin, Monika H Henzinger, and Christian Schulz. “Recent Advances
in Fully Dynamic Graph Algorithms.” In 1st Symposium on Algorithmic Foundations
of Dynamic Networks, Vol. 221. Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2022. https://doi.org/10.4230/LIPIcs.SAND.2022.1.
ieee: K. Hanauer, M. H. Henzinger, and C. Schulz, “Recent advances in fully dynamic
graph algorithms,” in 1st Symposium on Algorithmic Foundations of Dynamic Networks,
Virtual, 2022, vol. 221.
ista: 'Hanauer K, Henzinger MH, Schulz C. 2022. Recent advances in fully dynamic
graph algorithms. 1st Symposium on Algorithmic Foundations of Dynamic Networks.
SAND: Symposium on Algorithmic Foundations of Dynamic Networks, LIPIcs, vol. 221,
1.'
mla: Hanauer, Kathrin, et al. “Recent Advances in Fully Dynamic Graph Algorithms.”
1st Symposium on Algorithmic Foundations of Dynamic Networks, vol. 221,
1, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022, doi:10.4230/LIPIcs.SAND.2022.1.
short: K. Hanauer, M.H. Henzinger, C. Schulz, in:, 1st Symposium on Algorithmic
Foundations of Dynamic Networks, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2022.
conference:
end_date: 2022-03-30
location: Virtual
name: 'SAND: Symposium on Algorithmic Foundations of Dynamic Networks'
start_date: 2022-03-28
date_created: 2022-08-11T14:35:52Z
date_published: 2022-04-29T00:00:00Z
date_updated: 2023-02-14T08:14:41Z
day: '29'
doi: 10.4230/LIPIcs.SAND.2022.1
extern: '1'
external_id:
arxiv:
- '2102.11169'
intvolume: ' 221'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.4230/LIPIcs.SAND.2022.1
month: '04'
oa: 1
oa_version: Published Version
publication: 1st Symposium on Algorithmic Foundations of Dynamic Networks
publication_identifier:
eissn:
- 1868-8969
isbn:
- '9783959772242'
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Recent advances in fully dynamic graph algorithms
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 221
year: '2022'
...
---
_id: '12182'
abstract:
- lang: eng
text: 'Online algorithms make decisions based on past inputs, with the goal of being
competitive against an algorithm that sees also future inputs. In this work, we
introduce time-local online algorithms; these are online algorithms in which the
output at any given time is a function of only T latest inputs. Our main observation
is that time-local online algorithms are closely connected to local distributed
graph algorithms: distributed algorithms make decisions based on the local information
in the spatial dimension, while time-local online algorithms make decisions based
on the local information in the temporal dimension. We formalize this connection,
and show how we can directly use the tools developed to study distributed approximability
of graph optimization problems to prove upper and lower bounds on the competitive
ratio achieved with time-local online algorithms. Moreover, we show how to use
computational techniques to synthesize optimal time-local algorithms.'
acknowledgement: "This research has received funding from the German Research Foundation
(DFG), grant\r\n470029389 (FlexNets), 2021-2024, and the Marie Skłodowska-Curie
grant agreement No. 840605."
article_number: '52'
article_processing_charge: No
author:
- first_name: Maciej
full_name: Pacut, Maciej
last_name: Pacut
- first_name: Mahmoud
full_name: Parham, Mahmoud
last_name: Parham
- first_name: Joel
full_name: Rybicki, Joel
id: 334EFD2E-F248-11E8-B48F-1D18A9856A87
last_name: Rybicki
orcid: 0000-0002-6432-6646
- first_name: Stefan
full_name: Schmid, Stefan
last_name: Schmid
- first_name: Jukka
full_name: Suomela, Jukka
last_name: Suomela
- first_name: Aleksandr
full_name: Tereshchenko, Aleksandr
last_name: Tereshchenko
citation:
ama: 'Pacut M, Parham M, Rybicki J, Schmid S, Suomela J, Tereshchenko A. Brief announcement:
Temporal locality in online algorithms. In: 36th International Symposium on
Distributed Computing. Vol 246. Schloss Dagstuhl - Leibniz-Zentrum für Informatik;
2022. doi:10.4230/LIPIcs.DISC.2022.52'
apa: 'Pacut, M., Parham, M., Rybicki, J., Schmid, S., Suomela, J., & Tereshchenko,
A. (2022). Brief announcement: Temporal locality in online algorithms. In 36th
International Symposium on Distributed Computing (Vol. 246). Augusta, GA,
United States: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.DISC.2022.52'
chicago: 'Pacut, Maciej, Mahmoud Parham, Joel Rybicki, Stefan Schmid, Jukka Suomela,
and Aleksandr Tereshchenko. “Brief Announcement: Temporal Locality in Online Algorithms.”
In 36th International Symposium on Distributed Computing, Vol. 246. Schloss
Dagstuhl - Leibniz-Zentrum für Informatik, 2022. https://doi.org/10.4230/LIPIcs.DISC.2022.52.'
ieee: 'M. Pacut, M. Parham, J. Rybicki, S. Schmid, J. Suomela, and A. Tereshchenko,
“Brief announcement: Temporal locality in online algorithms,” in 36th International
Symposium on Distributed Computing, Augusta, GA, United States, 2022, vol.
246.'
ista: 'Pacut M, Parham M, Rybicki J, Schmid S, Suomela J, Tereshchenko A. 2022.
Brief announcement: Temporal locality in online algorithms. 36th International
Symposium on Distributed Computing. DISC: Symposium on Distributed Computing vol.
246, 52.'
mla: 'Pacut, Maciej, et al. “Brief Announcement: Temporal Locality in Online Algorithms.”
36th International Symposium on Distributed Computing, vol. 246, 52, Schloss
Dagstuhl - Leibniz-Zentrum für Informatik, 2022, doi:10.4230/LIPIcs.DISC.2022.52.'
short: M. Pacut, M. Parham, J. Rybicki, S. Schmid, J. Suomela, A. Tereshchenko,
in:, 36th International Symposium on Distributed Computing, Schloss Dagstuhl -
Leibniz-Zentrum für Informatik, 2022.
conference:
end_date: 2022-10-27
location: Augusta, GA, United States
name: 'DISC: Symposium on Distributed Computing'
start_date: 2022-10-25
date_created: 2023-01-13T11:06:28Z
date_published: 2022-10-17T00:00:00Z
date_updated: 2023-01-27T06:59:29Z
day: '17'
ddc:
- '000'
department:
- _id: DaAl
doi: 10.4230/LIPIcs.DISC.2022.52
ec_funded: 1
file:
- access_level: open_access
checksum: 11bbb56f68a00f2cf6bcce6cc7f5c5f9
content_type: application/pdf
creator: dernst
date_created: 2023-01-27T06:58:02Z
date_updated: 2023-01-27T06:58:02Z
file_id: '12409'
file_name: 2022_LIPICs_Pacut.pdf
file_size: 524804
relation: main_file
success: 1
file_date_updated: 2023-01-27T06:58:02Z
has_accepted_license: '1'
intvolume: ' 246'
language:
- iso: eng
month: '10'
oa: 1
oa_version: Published Version
project:
- _id: 26A5D39A-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '840605'
name: Coordination in constrained and natural distributed systems
publication: 36th International Symposium on Distributed Computing
publication_identifier:
eisbn:
- '9783959772556'
eissn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Brief announcement: Temporal locality in online algorithms'
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: 246
year: '2022'
...