---
OA_place: publisher
OA_type: gold
_id: '22922'
abstract:
- lang: eng
  text: In this note, we recall the history and our motivation behind the development
    of Strategy Logic and we discuss some of the work that ensued from its introduction.
acknowledgement: " Krishnendu Chatterjee: Supported in part by the Austrian Science
  Fund (FWF) COE\r\ngrant 10.55776/COE12 and the ERC CoG 863818 (ForM-SMArt).\r\nThomas
  A. Henzinger: Supported in part by the ERC AdG 101020093 (VAMOS) and the FWF\r\nSFB
  grant F8502 (SPyCoDe).\r\nNir Piterman: Supported in part by the Swedish research
  council (VR) project no. 2025-05419 and\r\nthe Wallenberg AI, Autonomous Systems
  and Software Program (WASP) funded by the Knut and\r\nAlice Wallenberg Foundation.\r\nAcknowledgements
  We thank the jury that our paper introducing Strategy Logic at the Conference\r\non
  Concurrency Theory (CONCUR) 2007 [10] was chosen for a CONCUR Test-of-Time Award
  at\r\nCONCUR 2026."
alternative_title:
- LIPIcs
article_number: 6:1-6:7
article_processing_charge: Yes
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: Nir
  full_name: Piterman, Nir
  last_name: Piterman
citation:
  ama: 'Chatterjee K, Henzinger TA, Piterman N. A look back at strategy logic. In:
    <i>37th International Conference on Concurrency Theory</i>. Vol 391. Schloss Dagstuhl
    - Leibniz-Zentrum für Informatik; 2026. doi:<a href="https://doi.org/10.4230/LIPIcs.CONCUR.2026.6">10.4230/LIPIcs.CONCUR.2026.6</a>'
  apa: 'Chatterjee, K., Henzinger, T. A., &#38; Piterman, N. (2026). A look back at
    strategy logic. In <i>37th International Conference on Concurrency Theory</i>
    (Vol. 391). Liverpool, United Kingdom: Schloss Dagstuhl - Leibniz-Zentrum für
    Informatik. <a href="https://doi.org/10.4230/LIPIcs.CONCUR.2026.6">https://doi.org/10.4230/LIPIcs.CONCUR.2026.6</a>'
  chicago: Chatterjee, Krishnendu, Thomas A Henzinger, and Nir Piterman. “A Look Back
    at Strategy Logic.” In <i>37th International Conference on Concurrency Theory</i>,
    Vol. 391. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026. <a href="https://doi.org/10.4230/LIPIcs.CONCUR.2026.6">https://doi.org/10.4230/LIPIcs.CONCUR.2026.6</a>.
  ieee: K. Chatterjee, T. A. Henzinger, and N. Piterman, “A look back at strategy
    logic,” in <i>37th International Conference on Concurrency Theory</i>, Liverpool,
    United Kingdom, 2026, vol. 391.
  ista: 'Chatterjee K, Henzinger TA, Piterman N. 2026. A look back at strategy logic.
    37th International Conference on Concurrency Theory. CONCUR: Conference on Concurrency
    Theory, LIPIcs, vol. 391, 6:1-6:7.'
  mla: Chatterjee, Krishnendu, et al. “A Look Back at Strategy Logic.” <i>37th International
    Conference on Concurrency Theory</i>, vol. 391, 6:1-6:7, Schloss Dagstuhl - Leibniz-Zentrum
    für Informatik, 2026, doi:<a href="https://doi.org/10.4230/LIPIcs.CONCUR.2026.6">10.4230/LIPIcs.CONCUR.2026.6</a>.
  short: K. Chatterjee, T.A. Henzinger, N. Piterman, in:, 37th International Conference
    on Concurrency Theory, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026.
conference:
  end_date: 2026-09-04
  location: Liverpool, United Kingdom
  name: 'CONCUR: Conference on Concurrency Theory'
  start_date: 2026-09-01
corr_author: '1'
das_tickbox: '0'
date_created: 2026-09-13T22:01:54Z
date_published: 2026-08-24T00:00:00Z
date_updated: 2026-09-22T05:54:30Z
day: '24'
ddc:
- '000'
department:
- _id: KrCh
- _id: ToHe
doi: 10.4230/LIPIcs.CONCUR.2026.6
ec_funded: 1
file:
- access_level: open_access
  checksum: f3995df175701f56a702bdb012e4f710
  content_type: application/pdf
  creator: dernst
  date_created: 2026-09-22T05:53:16Z
  date_updated: 2026-09-22T05:53:16Z
  file_id: '22977'
  file_name: 2026_LIPIcsCONCUR_Chatterjee.pdf
  file_size: 517651
  relation: main_file
  success: 1
file_date_updated: 2026-09-22T05:53:16Z
fulldoi: https://doi.org/10.4230/LIPIcs.CONCUR.2026.6
has_accepted_license: '1'
intvolume: '       391'
keyword:
- Strategy Logic
- Games
- Automata
language:
- iso: eng
month: '08'
oa: 1
oa_version: Published Version
project:
- _id: 4029cfc7-b034-11f1-9e55-88ab2ff3b6ee
  grant_number: COE12
  name: Bilateral Artificial Intelligence (Chatterjee)
- _id: 0599E47C-7A3F-11EA-A408-12923DDC885E
  call_identifier: H2020
  grant_number: '863818'
  name: 'Formal Methods for Stochastic Models: Algorithms and Applications'
- _id: 62781420-2b32-11ec-9570-8d9b63373d4d
  call_identifier: H2020
  grant_number: '101020093'
  name: Vigilant Algorithmic Monitoring of Software
- _id: 34a1b658-11ca-11ed-8bc3-c75229f0241e
  grant_number: F8502
  name: Interface Theory for Security and Privacy
publication: 37th International Conference on Concurrency Theory
publication_identifier:
  isbn:
  - '9783959774475'
  issn:
  - 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
researchdata_availability: no
scopus_import: '1'
status: public
supplementarymaterial: no
title: A look back at strategy logic
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: 391
year: '2026'
...
---
_id: '10004'
abstract:
- lang: eng
  text: 'Markov chains are the de facto finite-state model for stochastic dynamical
    systems, and Markov decision processes (MDPs) extend Markov chains by incorporating
    non-deterministic behaviors. Given an MDP and rewards on states, a classical optimization
    criterion is the maximal expected total reward where the MDP stops after T steps,
    which can be computed by a simple dynamic programming algorithm. We consider a
    natural generalization of the problem where the stopping times can be chosen according
    to a probability distribution, such that the expected stopping time is T, to optimize
    the expected total reward. Quite surprisingly we establish inter-reducibility
    of the expected stopping-time problem for Markov chains with the Positivity problem
    (which is related to the well-known Skolem problem), for which establishing either
    decidability or undecidability would be a major breakthrough. Given the hardness
    of the exact problem, we consider the approximate version of the problem: we show
    that it can be solved in exponential time for Markov chains and in exponential
    space for MDPs.'
acknowledgement: We are grateful to the anonymous reviewers of LICS 2021 and of a
  previous version of this paper for insightful comments that helped improving the
  presentation. This research was partially supported by the grant ERC CoG 863818
  (ForM-SMArt).
article_processing_charge: No
arxiv: 1
author:
- first_name: Krishnendu
  full_name: Chatterjee, Krishnendu
  id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
  last_name: Chatterjee
  orcid: 0000-0002-4561-241X
- first_name: Laurent
  full_name: Doyen, Laurent
  last_name: Doyen
citation:
  ama: 'Chatterjee K, Doyen L. Stochastic processes with expected stopping time. In:
    <i>Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science</i>.
    IEEE; 2021:1-13. doi:<a href="https://doi.org/10.1109/LICS52264.2021.9470595">10.1109/LICS52264.2021.9470595</a>'
  apa: 'Chatterjee, K., &#38; Doyen, L. (2021). Stochastic processes with expected
    stopping time. In <i>Proceedings of the 36th Annual ACM/IEEE Symposium on Logic
    in Computer Science</i> (pp. 1–13). Rome, Italy: IEEE. <a href="https://doi.org/10.1109/LICS52264.2021.9470595">https://doi.org/10.1109/LICS52264.2021.9470595</a>'
  chicago: Chatterjee, Krishnendu, and Laurent Doyen. “Stochastic Processes with Expected
    Stopping Time.” In <i>Proceedings of the 36th Annual ACM/IEEE Symposium on Logic
    in Computer Science</i>, 1–13. IEEE, 2021. <a href="https://doi.org/10.1109/LICS52264.2021.9470595">https://doi.org/10.1109/LICS52264.2021.9470595</a>.
  ieee: K. Chatterjee and L. Doyen, “Stochastic processes with expected stopping time,”
    in <i>Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science</i>,
    Rome, Italy, 2021, pp. 1–13.
  ista: 'Chatterjee K, Doyen L. 2021. Stochastic processes with expected stopping
    time. Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science.
    LICS: Logic in Computer Science, 1–13.'
  mla: Chatterjee, Krishnendu, and Laurent Doyen. “Stochastic Processes with Expected
    Stopping Time.” <i>Proceedings of the 36th Annual ACM/IEEE Symposium on Logic
    in Computer Science</i>, IEEE, 2021, pp. 1–13, doi:<a href="https://doi.org/10.1109/LICS52264.2021.9470595">10.1109/LICS52264.2021.9470595</a>.
  short: K. Chatterjee, L. Doyen, in:, Proceedings of the 36th Annual ACM/IEEE Symposium
    on Logic in Computer Science, IEEE, 2021, pp. 1–13.
conference:
  end_date: 2021-07-02
  location: Rome, Italy
  name: 'LICS: Logic in Computer Science'
  start_date: 2021-06-29
date_created: 2021-09-12T22:01:25Z
date_published: 2021-07-07T00:00:00Z
date_updated: 2026-08-12T06:39:27Z
day: '07'
department:
- _id: KrCh
doi: 10.1109/LICS52264.2021.9470595
ec_funded: 1
external_id:
  arxiv:
  - '2104.07278'
  isi:
  - '000947350400036'
fulldoi: https://doi.org/10.1109/LICS52264.2021.9470595
isi: 1
keyword:
- Computer science
- Heuristic algorithms
- Memory management
- Automata
- Markov processes
- Probability distribution
- Complexity theory
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/2104.07278
month: '07'
oa: 1
oa_version: Preprint
page: 1-13
project:
- _id: 0599E47C-7A3F-11EA-A408-12923DDC885E
  call_identifier: H2020
  grant_number: '863818'
  name: 'Formal Methods for Stochastic Models: Algorithms and Applications'
publication: Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer
  Science
publication_identifier:
  eisbn:
  - 978-1-6654-4895-6
  isbn:
  - 978-1-6654-4896-3
  issn:
  - 1043-6871
publication_status: published
publisher: IEEE
quality_controlled: '1'
related_material:
  record:
  - id: '18630'
    relation: later_version
    status: public
scopus_import: '1'
status: public
title: Stochastic processes with expected stopping time
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2021'
...