---
_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>.
    Institute of Electrical and Electronics Engineers; 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: Institute of Electrical and Electronics
    Engineers. <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. Institute of Electrical and Electronics Engineers,
    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: Symposium on 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>, Institute of Electrical and Electronics Engineers, 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, Institute of Electrical and Electronics Engineers,
    2021, pp. 1–13.
conference:
  end_date: 2021-07-02
  location: Rome, Italy
  name: 'LICS: Symposium on 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: 2025-07-14T09:10:08Z
day: '07'
department:
- _id: KrCh
doi: 10.1109/LICS52264.2021.9470595
ec_funded: 1
external_id:
  arxiv:
  - '2104.07278'
  isi:
  - '000947350400036'
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: Institute of Electrical and Electronics Engineers
quality_controlled: '1'
scopus_import: '1'
status: public
title: Stochastic processes with expected stopping time
type: conference
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
year: '2021'
...
---
_id: '10045'
abstract:
- lang: eng
  text: "Given a fixed finite metric space (V,μ), the {\\em minimum 0-extension problem},
    denoted as 0-Ext[μ], is equivalent to the following optimization problem: minimize
    function of the form minx∈Vn∑ifi(xi)+∑ijcijμ(xi,xj) where cij,cvi are given nonnegative
    costs and fi:V→R are functions given by fi(xi)=∑v∈Vcviμ(xi,v). The computational
    complexity of 0-Ext[μ] has been recently established by Karzanov and by Hirai:
    if metric μ is {\\em orientable modular} then 0-Ext[μ] can be solved in polynomial
    time, otherwise 0-Ext[μ] is NP-hard. To prove the tractability part, Hirai developed
    a theory of discrete convex functions on orientable modular graphs generalizing
    several known classes of functions in discrete convex analysis, such as L♮-convex
    functions. We consider a more general version of the problem in which unary functions
    fi(xi) can additionally have terms of the form cuv;iμ(xi,{u,v}) for {u,v}∈F, where
    set F⊆(V2) is fixed. We extend the complexity classification above by providing
    an explicit condition on (μ,F) for the problem to be tractable. In order to prove
    the tractability part, we generalize Hirai's theory and define a larger class
    of discrete convex functions. It covers, in particular, another well-known class
    of functions, namely submodular functions on an integer lattice. Finally, we improve
    the complexity of Hirai's algorithm for solving 0-Ext on orientable modular graphs.\r\n"
article_number: '2109.10203'
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: Vladimir
  full_name: Kolmogorov, Vladimir
  id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
  last_name: Kolmogorov
citation:
  ama: Dvorak M, Kolmogorov V. Generalized minimum 0-extension problem and discrete
    convexity. <i>arXiv</i>. doi:<a href="https://doi.org/10.48550/arXiv.2109.10203">10.48550/arXiv.2109.10203</a>
  apa: Dvorak, M., &#38; Kolmogorov, V. (n.d.). Generalized minimum 0-extension problem
    and discrete convexity. <i>arXiv</i>. <a href="https://doi.org/10.48550/arXiv.2109.10203">https://doi.org/10.48550/arXiv.2109.10203</a>
  chicago: Dvorak, Martin, and Vladimir Kolmogorov. “Generalized Minimum 0-Extension
    Problem and Discrete Convexity.” <i>ArXiv</i>, n.d. <a href="https://doi.org/10.48550/arXiv.2109.10203">https://doi.org/10.48550/arXiv.2109.10203</a>.
  ieee: M. Dvorak and V. Kolmogorov, “Generalized minimum 0-extension problem and
    discrete convexity,” <i>arXiv</i>. .
  ista: Dvorak M, Kolmogorov V. Generalized minimum 0-extension problem and discrete
    convexity. arXiv, 2109.10203.
  mla: Dvorak, Martin, and Vladimir Kolmogorov. “Generalized Minimum 0-Extension Problem
    and Discrete Convexity.” <i>ArXiv</i>, 2109.10203, doi:<a href="https://doi.org/10.48550/arXiv.2109.10203">10.48550/arXiv.2109.10203</a>.
  short: M. Dvorak, V. Kolmogorov, ArXiv (n.d.).
date_created: 2021-09-27T10:48:23Z
date_published: 2021-09-21T00:00:00Z
date_updated: 2023-05-03T10:40:16Z
day: '21'
ddc:
- '004'
department:
- _id: GradSch
- _id: VlKo
doi: 10.48550/arXiv.2109.10203
external_id:
  arxiv:
  - '2109.10203'
file:
- access_level: open_access
  checksum: e7e83065f7bc18b9c188bf93b5ca5db6
  content_type: application/pdf
  creator: mdvorak
  date_created: 2021-09-27T10:54:51Z
  date_updated: 2021-09-27T10:54:51Z
  file_id: '10046'
  file_name: Generalized-0-Ext.pdf
  file_size: 603672
  relation: main_file
  success: 1
file_date_updated: 2021-09-27T10:54:51Z
has_accepted_license: '1'
keyword:
- minimum 0-extension problem
- metric labeling problem
- discrete metric spaces
- metric extensions
- computational complexity
- valued constraint satisfaction problems
- discrete convex analysis
- L-convex functions
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: ' https://doi.org/10.48550/arXiv.2109.10203'
month: '09'
oa: 1
oa_version: Preprint
publication: arXiv
publication_status: submitted
status: public
title: Generalized minimum 0-extension problem and discrete convexity
type: preprint
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2021'
...
---
_id: '4317'
article_processing_charge: No
author:
- first_name: Nicholas H
  full_name: Barton, Nicholas H
  id: 4880FE40-F248-11E8-B48F-1D18A9856A87
  last_name: Barton
  orcid: 0000-0002-8548-5240
citation:
  ama: 'Barton NH. Speciation. In: Myers A, Giller P, eds. <i>Analytical Biogeography:
    An Integrated Approach to the Study of Animal and Plant Distributions</i>. 1st
    ed. Springer; 1988:185-218. doi:<a href="https://doi.org/10.1007/978-94-009-0435-4">10.1007/978-94-009-0435-4</a>'
  apa: 'Barton, N. H. (1988). Speciation. In A. Myers &#38; P. Giller (Eds.), <i>Analytical
    biogeography: An integrated approach to the study of animal and plant distributions</i>
    (1st ed., pp. 185–218). Springer. <a href="https://doi.org/10.1007/978-94-009-0435-4">https://doi.org/10.1007/978-94-009-0435-4</a>'
  chicago: 'Barton, Nicholas H. “Speciation.” In <i>Analytical Biogeography: An Integrated
    Approach to the Study of Animal and Plant Distributions</i>, edited by Alan Myers
    and Paul Giller, 1st ed., 185–218. Springer, 1988. <a href="https://doi.org/10.1007/978-94-009-0435-4">https://doi.org/10.1007/978-94-009-0435-4</a>.'
  ieee: 'N. H. Barton, “Speciation,” in <i>Analytical biogeography: An integrated
    approach to the study of animal and plant distributions</i>, 1st ed., A. Myers
    and P. Giller, Eds. Springer, 1988, pp. 185–218.'
  ista: 'Barton NH. 1988.Speciation. In: Analytical biogeography: An integrated approach
    to the study of animal and plant distributions. , 185–218.'
  mla: 'Barton, Nicholas H. “Speciation.” <i>Analytical Biogeography: An Integrated
    Approach to the Study of Animal and Plant Distributions</i>, edited by Alan Myers
    and Paul Giller, 1st ed., Springer, 1988, pp. 185–218, doi:<a href="https://doi.org/10.1007/978-94-009-0435-4">10.1007/978-94-009-0435-4</a>.'
  short: 'N.H. Barton, in:, A. Myers, P. Giller (Eds.), Analytical Biogeography: An
    Integrated Approach to the Study of Animal and Plant Distributions, 1st ed., Springer,
    1988, pp. 185–218.'
date_created: 2018-12-11T12:08:13Z
date_published: 1988-01-01T00:00:00Z
date_updated: 2022-02-08T09:19:50Z
day: '01'
doi: 10.1007/978-94-009-0435-4
edition: '1'
editor:
- first_name: Alan
  full_name: Myers, Alan
  last_name: Myers
- first_name: Paul
  full_name: Giller, Paul
  last_name: Giller
extern: '1'
keyword:
- biogeography
- biology
- complexity
- distribution
- evolution
- geology
language:
- iso: eng
main_file_link:
- url: https://link.springer.com/book/10.1007/978-94-009-0435-4#toc
month: '01'
oa_version: None
page: 185 - 218
publication: 'Analytical biogeography: An integrated approach to the study of animal
  and plant distributions'
publication_identifier:
  eissn:
  - 978-94-009-0435-4
  isbn:
  - 978-0-412-40050-6
publication_status: published
publisher: Springer
publist_id: '1736'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Speciation
type: book_chapter
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
year: '1988'
...