Faster algorithms for the nonemptiness of streett automata and for communication protocol pruning
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.
Download
No fulltext has been uploaded. References only!
Conference Paper
| Published
| English
Scopus indexed
Author
Henzinger, MonikaISTA ;
Telle, Jan Arne
Series Title
LNCS
Abstract
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.
(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 𝑂(𝑚min{𝑚𝑙𝑜𝑔𝑛,‾‾‾‾‾‾√𝑘,𝑛}+𝑏𝑚𝑖𝑛{𝑙𝑜𝑔𝑛,𝑘}).
(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 𝑂(𝑙√∑𝑖𝑚1.5𝑖).
Publishing Year
Date Published
1996-07-01
Proceedings Title
5th Scandinavian Workshop on Algorithm Theory
Publisher
Springer Nature
Volume
1097
Page
16–27
Conference
SWAT: Scandinavian Workshop on Algorithm Theory
Conference Location
Reykjavik, Iceland
Conference Date
1996-07-03 – 1996-07-05
ISBN
ISSN
eISSN
IST-REx-ID
Cite this
Henzinger MH, Telle JA. Faster algorithms for the nonemptiness of streett automata and for communication protocol pruning. In: 5th Scandinavian Workshop on Algorithm Theory. Vol 1097. Springer Nature; 1996:16–27. doi:10.1007/3-540-61422-2_117
Henzinger, M. H., & Telle, J. A. (1996). Faster algorithms for the nonemptiness of streett automata and for communication protocol pruning. In 5th Scandinavian Workshop on Algorithm Theory (Vol. 1097, pp. 16–27). Reykjavik, Iceland: Springer Nature. https://doi.org/10.1007/3-540-61422-2_117
Henzinger, Monika H, and Jan Arne Telle. “Faster Algorithms for the Nonemptiness of Streett Automata and for Communication Protocol Pruning.” In 5th Scandinavian Workshop on Algorithm Theory, 1097:16–27. Springer Nature, 1996. https://doi.org/10.1007/3-540-61422-2_117.
M. H. Henzinger and J. A. Telle, “Faster algorithms for the nonemptiness of streett automata and for communication protocol pruning,” in 5th Scandinavian Workshop on Algorithm Theory, Reykjavik, Iceland, 1996, vol. 1097, pp. 16–27.
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.
Henzinger, Monika H., and Jan Arne Telle. “Faster Algorithms for the Nonemptiness of Streett Automata and for Communication Protocol Pruning.” 5th Scandinavian Workshop on Algorithm Theory, vol. 1097, Springer Nature, 1996, pp. 16–27, doi:10.1007/3-540-61422-2_117.