---
_id: '11804'
abstract:
- lang: eng
  text: "This paper shows how a general technique, called lock-step search, used in
    dynamic graph algorithms, can be used to improve the running time of two problems
    arising in program verification and communication protocol design.\r\n(1)We consider
    the nonemptiness problem for Streett automata: We are given a directed graph G
    = (V, E) with n = ¦V¦ and m = ¦E¦, and a collection of pairs of subsets of vertices,
    called Streett pairs,〈L i , U i 〉, i = 1.k. The question is whether G has a cycle
    (not necessarily simple) which, for each 1 ≤ i ≤ k, if it contains a vertex from
    L i then it also contains a vertex of U i . Let b=Σ i=1..k |L i |+|U i |. The
    previously best algorithm takes time O((m + b) min{n, k}). We present an algorithm
    that takes time \U0001D442(\U0001D45Amin{\U0001D45A\U0001D459\U0001D45C\U0001D454\U0001D45B,‾‾‾‾‾‾√\U0001D458,\U0001D45B}+\U0001D44F\U0001D45A\U0001D456\U0001D45B{\U0001D459\U0001D45C\U0001D454\U0001D45B,\U0001D458}).\r\n(2)In
    communication protocol pruning we are given a directed graph G = (V, E) with l
    special vertices. The problem is to efficiently maintain the strongly-connected
    components of the special vertices on a restricted set of edge deletions. Let
    m i be the number of edges in the strongly connected component of the ith special
    vertex. The previously best algorithm repeatedly recomputes the strongly-connected
    components which leads to a running time of O(Σ i m 2i). We present an algorithm
    with time \U0001D442(\U0001D459√∑\U0001D456\U0001D45A1.5\U0001D456)."
alternative_title:
- LNCS
article_processing_charge: No
author:
- 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: Jan Arne
  full_name: Telle, Jan Arne
  last_name: Telle
citation:
  ama: 'Henzinger MH, Telle JA. Faster algorithms for the nonemptiness of streett
    automata and for communication protocol pruning. In: <i>5th Scandinavian Workshop
    on Algorithm Theory</i>. Vol 1097. Springer Nature; 1996:16–27. doi:<a href="https://doi.org/10.1007/3-540-61422-2_117">10.1007/3-540-61422-2_117</a>'
  apa: 'Henzinger, M. H., &#38; Telle, J. A. (1996). Faster algorithms for the nonemptiness
    of streett automata and for communication protocol pruning. In <i>5th Scandinavian
    Workshop on Algorithm Theory</i> (Vol. 1097, pp. 16–27). Reykjavik, Iceland: Springer
    Nature. <a href="https://doi.org/10.1007/3-540-61422-2_117">https://doi.org/10.1007/3-540-61422-2_117</a>'
  chicago: Henzinger, Monika H, and Jan Arne Telle. “Faster Algorithms for the Nonemptiness
    of Streett Automata and for Communication Protocol Pruning.” In <i>5th Scandinavian
    Workshop on Algorithm Theory</i>, 1097:16–27. Springer Nature, 1996. <a href="https://doi.org/10.1007/3-540-61422-2_117">https://doi.org/10.1007/3-540-61422-2_117</a>.
  ieee: M. H. Henzinger and J. A. Telle, “Faster algorithms for the nonemptiness of
    streett automata and for communication protocol pruning,” in <i>5th Scandinavian
    Workshop on Algorithm Theory</i>, Reykjavik, Iceland, 1996, vol. 1097, pp. 16–27.
  ista: 'Henzinger MH, Telle JA. 1996. Faster algorithms for the nonemptiness of streett
    automata and for communication protocol pruning. 5th Scandinavian Workshop on
    Algorithm Theory. SWAT: Scandinavian Workshop on Algorithm Theory, LNCS, vol.
    1097, 16–27.'
  mla: Henzinger, Monika H., and Jan Arne Telle. “Faster Algorithms for the Nonemptiness
    of Streett Automata and for Communication Protocol Pruning.” <i>5th Scandinavian
    Workshop on Algorithm Theory</i>, vol. 1097, Springer Nature, 1996, pp. 16–27,
    doi:<a href="https://doi.org/10.1007/3-540-61422-2_117">10.1007/3-540-61422-2_117</a>.
  short: M.H. Henzinger, J.A. Telle, in:, 5th Scandinavian Workshop on Algorithm Theory,
    Springer Nature, 1996, pp. 16–27.
conference:
  end_date: 1996-07-05
  location: Reykjavik, Iceland
  name: 'SWAT: Scandinavian Workshop on Algorithm Theory'
  start_date: 1996-07-03
date_created: 2022-08-11T13:42:42Z
date_published: 1996-07-01T00:00:00Z
date_updated: 2023-02-14T07:52:17Z
day: '01'
doi: 10.1007/3-540-61422-2_117
extern: '1'
intvolume: '      1097'
language:
- iso: eng
month: '07'
oa_version: None
page: 16–27
publication: 5th Scandinavian Workshop on Algorithm Theory
publication_identifier:
  eisbn:
  - '9783540685296'
  eissn:
  - 1611-3349
  isbn:
  - '9783540614227'
  issn:
  - 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Faster algorithms for the nonemptiness of streett automata and for communication
  protocol pruning
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 1097
year: '1996'
...