The Experts below are selected from a list of 3714 Experts worldwide ranked by ideXlab platform
Venkatesh Raman - One of the best experts on this subject based on the ideXlab platform.
-
On the Succinct Representation of Equivalence Classes
Algorithmica, 2017Co-Authors: Hicham El-zein, Venkatesh Raman, Maciej Lewenstein, J. Ian Munro, Timothy M. ChanAbstract:Given a partition of an n element set into equivalence classes, we study the problem of assigning unique labels to these elements in order to support the query that asks whether the elements corresponding to two given labels belong to the same equivalence class. This has various applications including for testing whether two vertices are in the same connected component in an undirected graph or in the same strongly connected component in a directed graph. We consider the problem in several models.Concerning labeling schemes where we assign labels to elements and the query is to be answered just by examining the labels of the queried elements (without any extra space): if each vertex is required to have a unique label, then we show that a label space of $$\sum _{i=1}^n \lfloor {n \over i} \rfloor $$∑i=1n⌊ni⌋ is necessary and sufficient. In other words, $$\lg n + \lg \lg n + O(1)$$lgn+lglgn+O(1) bits of space are necessary and sufficient for representing each of the labels. This slightly strengthens the known lower bound and is in contrast to the known necessary and sufficient bound of $$\lceil \lg n \rceil $$⌈lgn⌉ for the label length, if each vertex need not get a unique label.Concerning succinct data structures for the problem when the n elements are to be uniquely assigned labels from label set $$\{1,\ldots , n\}$${1,…,n}, we first show that $$\varTheta (\sqrt{n})$$Θ(n) bits are necessary and sufficient to represent the equivalence class information. This space includes the space for implicitly encoding the vertex labels. We can support the query in such a structure in O(1) time in the standard word RAM model. We also develop a dynamic structure that uses $$O(\sqrt{n} \lg n)$$O(nlgn) bits to support equivalence queries and unions in $$O(\lg n/\lg \lg n)$$O(lgn/lglgn) worst case time or $$O(\alpha (n))$$O(α(n)) expected amortized time where $$\alpha (n)$$α(n) is the inverse Ackermann function.Concerning succinct data structures for the problem when the n elements are to be uniquely assigned labels from label set $$\{1,\ldots , cn\}$${1,…,cn} for any constant $$c > 1$$c>1, we show that $$\varTheta (\lg n)$$Θ(lgn) bits are necessary and sufficient to represent the equivalence class information. Moreover, we can support the query in such a structure in O(1) time in the standard word RAM model. We believe that our work can trigger further work on tradeoffs between label space and auxiliary data structure space for other labeling problems.
-
succinct data structures for representing equivalence classes
International Symposium on Algorithms and Computation, 2013Co-Authors: Maciej Lewenstein, Ian J Munro, Venkatesh RamanAbstract:Given a partition of an n element set into equivalence classes, we consider time-space tradeoffs for representing it to support the query that asks whether two given elements are in the same equivalence class. This has various applications including for testing whether two vertices are in the same connected component in an undirected graph or in the same strongly connected component in a directed graph.
-
ISAAC - Succinct Data Structures for Representing Equivalence Classes
Algorithms and Computation, 2013Co-Authors: Maciej Lewenstein, J. Ian Munro, Venkatesh RamanAbstract:Given a partition of an n element set into equivalence classes, we consider time-space tradeoffs for representing it to support the query that asks whether two given elements are in the same equivalence class. This has various applications including for testing whether two vertices are in the same connected component in an undirected graph or in the same strongly connected component in a directed graph.
-
succinct data structures for representing equivalence classes
arXiv: Data Structures and Algorithms, 2013Co-Authors: Maciej Lewenstein, Ian J Munro, Venkatesh RamanAbstract:Given a partition of an n element set into equivalence classes, we consider time-space tradeoffs for representing it to support the query that asks whether two given elements are in the same equivalence class. This has various applications including for testing whether two vertices are in the same component in an undirected graph or in the same strongly connected component in a directed graph. We consider the problem in several models. -- Concerning labeling schemes where we assign labels to elements and the query is to be answered just by examining the labels of the queried elements (without any extra space): if each vertex is required to have a unique label, then we show that a label space of (\sum_{i=1}^n \lfloor {n \over i} \rfloor) is necessary and sufficient. In other words, \lg n + \lg \lg n + O(1) bits of space are necessary and sufficient for representing each of the labels. This slightly strengthens the known lower bound and is in contrast to the known necessary and sufficient bound of \lceil \lg n \rceil for the label length, if each vertex need not get a unique label. --Concerning succinct data structures for the problem when the n elements are to be uniquely assigned labels from label set {1, 2, ...n}, we first show that \Theta(\sqrt n) bits are necessary and sufficient to represent the equivalence class information. This space includes the space for implicitly encoding the vertex labels. We can support the query in such a structure in O(\lg n) time in the standard word RAM model. We then develop structures resulting in one where the queries can be supported in constant time using O({\sqrt n} \lg n) bits of space. We also develop space efficient structures where union operation along with the equivalence query can be answered fast.
Maciej Lewenstein - One of the best experts on this subject based on the ideXlab platform.
-
On the Succinct Representation of Equivalence Classes
Algorithmica, 2017Co-Authors: Hicham El-zein, Venkatesh Raman, Maciej Lewenstein, J. Ian Munro, Timothy M. ChanAbstract:Given a partition of an n element set into equivalence classes, we study the problem of assigning unique labels to these elements in order to support the query that asks whether the elements corresponding to two given labels belong to the same equivalence class. This has various applications including for testing whether two vertices are in the same connected component in an undirected graph or in the same strongly connected component in a directed graph. We consider the problem in several models.Concerning labeling schemes where we assign labels to elements and the query is to be answered just by examining the labels of the queried elements (without any extra space): if each vertex is required to have a unique label, then we show that a label space of $$\sum _{i=1}^n \lfloor {n \over i} \rfloor $$∑i=1n⌊ni⌋ is necessary and sufficient. In other words, $$\lg n + \lg \lg n + O(1)$$lgn+lglgn+O(1) bits of space are necessary and sufficient for representing each of the labels. This slightly strengthens the known lower bound and is in contrast to the known necessary and sufficient bound of $$\lceil \lg n \rceil $$⌈lgn⌉ for the label length, if each vertex need not get a unique label.Concerning succinct data structures for the problem when the n elements are to be uniquely assigned labels from label set $$\{1,\ldots , n\}$${1,…,n}, we first show that $$\varTheta (\sqrt{n})$$Θ(n) bits are necessary and sufficient to represent the equivalence class information. This space includes the space for implicitly encoding the vertex labels. We can support the query in such a structure in O(1) time in the standard word RAM model. We also develop a dynamic structure that uses $$O(\sqrt{n} \lg n)$$O(nlgn) bits to support equivalence queries and unions in $$O(\lg n/\lg \lg n)$$O(lgn/lglgn) worst case time or $$O(\alpha (n))$$O(α(n)) expected amortized time where $$\alpha (n)$$α(n) is the inverse Ackermann function.Concerning succinct data structures for the problem when the n elements are to be uniquely assigned labels from label set $$\{1,\ldots , cn\}$${1,…,cn} for any constant $$c > 1$$c>1, we show that $$\varTheta (\lg n)$$Θ(lgn) bits are necessary and sufficient to represent the equivalence class information. Moreover, we can support the query in such a structure in O(1) time in the standard word RAM model. We believe that our work can trigger further work on tradeoffs between label space and auxiliary data structure space for other labeling problems.
-
succinct data structures for representing equivalence classes
International Symposium on Algorithms and Computation, 2013Co-Authors: Maciej Lewenstein, Ian J Munro, Venkatesh RamanAbstract:Given a partition of an n element set into equivalence classes, we consider time-space tradeoffs for representing it to support the query that asks whether two given elements are in the same equivalence class. This has various applications including for testing whether two vertices are in the same connected component in an undirected graph or in the same strongly connected component in a directed graph.
-
ISAAC - Succinct Data Structures for Representing Equivalence Classes
Algorithms and Computation, 2013Co-Authors: Maciej Lewenstein, J. Ian Munro, Venkatesh RamanAbstract:Given a partition of an n element set into equivalence classes, we consider time-space tradeoffs for representing it to support the query that asks whether two given elements are in the same equivalence class. This has various applications including for testing whether two vertices are in the same connected component in an undirected graph or in the same strongly connected component in a directed graph.
-
succinct data structures for representing equivalence classes
arXiv: Data Structures and Algorithms, 2013Co-Authors: Maciej Lewenstein, Ian J Munro, Venkatesh RamanAbstract:Given a partition of an n element set into equivalence classes, we consider time-space tradeoffs for representing it to support the query that asks whether two given elements are in the same equivalence class. This has various applications including for testing whether two vertices are in the same component in an undirected graph or in the same strongly connected component in a directed graph. We consider the problem in several models. -- Concerning labeling schemes where we assign labels to elements and the query is to be answered just by examining the labels of the queried elements (without any extra space): if each vertex is required to have a unique label, then we show that a label space of (\sum_{i=1}^n \lfloor {n \over i} \rfloor) is necessary and sufficient. In other words, \lg n + \lg \lg n + O(1) bits of space are necessary and sufficient for representing each of the labels. This slightly strengthens the known lower bound and is in contrast to the known necessary and sufficient bound of \lceil \lg n \rceil for the label length, if each vertex need not get a unique label. --Concerning succinct data structures for the problem when the n elements are to be uniquely assigned labels from label set {1, 2, ...n}, we first show that \Theta(\sqrt n) bits are necessary and sufficient to represent the equivalence class information. This space includes the space for implicitly encoding the vertex labels. We can support the query in such a structure in O(\lg n) time in the standard word RAM model. We then develop structures resulting in one where the queries can be supported in constant time using O({\sqrt n} \lg n) bits of space. We also develop space efficient structures where union operation along with the equivalence query can be answered fast.
Mirko Fiacchini - One of the best experts on this subject based on the ideXlab platform.
-
Language constrained stabilization of discrete-time switched linear systems: an LMI approach
2018Co-Authors: Marc Jungers, Antoine Girard, Mirko FiacchiniAbstract:The goal of this paper is to study sufficient conditions to stabilize an autonomous discrete-time switched system, for which the switching law should belong to a constrained language characterized by a nondeterministic automaton. Based on a decomposition into strongly connected components of the automaton, it is shown that it suffices to consider only a nontrivial strongly connected component. Sufficient conditions are provided as a set of Linear Matrix Inequalities (LMIs) related to the automaton states and associated with a min-switching strategy. Equivalence with the periodic stabilization is investigated. A numerical example is provided to illustrate the main result.
-
Language constrained stabilization of discrete-time switched linear systems: a Lyapunov-Metzler inequalities approach
2016Co-Authors: Marc Jungers, Antoine Girard, Mirko FiacchiniAbstract:This paper addresses the issue of stabilizability of an autonomous discrete-time switched system via a switching law that is constrained to belong to a language generated by an nondeterministic finite state automaton. Firstly the automaton is decomposed into strongly connected components to reduce the problem to the stabilizability of each non trivial strongly connected component. Secondly the approach considering Lyapunov-Metzler inequalities taking into account the language constraint for a strongly connected component is proposed. Links with the current literature are discussed and a detailed example is given to illustrate our contributions.
-
CDC - Language constrained stabilization of discrete-time switched linear systems: a Lyapunov-Metzler inequalities approach
2016 IEEE 55th Conference on Decision and Control (CDC), 2016Co-Authors: Marc Jungers, Antoine Girard, Mirko FiacchiniAbstract:This paper addresses the issue of stabilizability of an autonomous discrete-time switched system via a switching law that is constrained to belong to a language generated by an nondeterministic finite state automaton. Firstly the automaton is decomposed into strongly connected components to reduce the problem to the stabilizability of each non trivial strongly connected component. Secondly the approach considering Lyapunov-Metzler inequalities taking into account the language constraint for a strongly connected component is proposed. Links with the current literature are discussed and a detailed example is given to illustrate our contributions.
Fabio Somenzi - One of the best experts on this subject based on the ideXlab platform.
-
An Algorithm for strongly connected component Analysis in n log n Symbolic Steps
Formal Methods in System Design, 2006Co-Authors: Roderick Bloem, Harold N. Gabow, Fabio SomenziAbstract:We present a symbolic algorithm for strongly connected component decomposition. The algorithm performs Θ( n log n ) image and preimage computations in the worst case, where n is the number of nodes in the graph. This is an improvement over the previously known quadratic bound. The algorithm can be used to decide emptiness of Büchi automata with the same complexity bound, improving Emerson and Lei's quadratic bound, and emptiness of Streett automata, with a similar bound in terms of nodes. It also leads to an improved procedure for the generation of nonemptiness witnesses.
-
FMCAD - An Algorithm for strongly connected component Analysis in n log n Symbolic Steps
2000Co-Authors: Roderick Bloem, Harold N. Gabow, Fabio SomenziAbstract:We present a symbolic algorithm for strongly connected component decomposition. The algorithm performs ?(n log n) image and preimage computations in the worst case, where n is the number of nodes in the graph. This is an improvement over the previously known quadratic bound. The algorithm can be used to decide emptiness of B?chi automata with the same complexity bound, improving Emerson and Lei's quadratic bound, and emptiness of Streett automata, with a similar bound in terms of nodes. It also leads to an improved procedure for the generation of nonemptiness witnesses.
Fabio Caccioli - One of the best experts on this subject based on the ideXlab platform.
-
Emergence of giant strongly connected components in continuum disk-spin percolation
Journal of Statistical Mechanics: Theory and Experiment, 2016Co-Authors: Francesco Caravelli, Marco Bardoscia, Fabio CaccioliAbstract:We propose a continuum model of percolation in two dimensions for overlapping disks with spin. In this model the existence of bonds is determined by the distance between the centers of the disks, and by the scalar product of the (randomly) directed spin with the direction of the vector connecting the centers of neighboring disks. The direction of a single spin is controlled by a "temperature", representing the amount of polarization of the spins in the direction of an external field. Our model is inspired by biological neuronal networks and aims to characterize their topological properties when axonal guidance plays a major role. We numerically study the phase diagram of the model observing the emergence of a giant strongly connected component, representing the portion of neurons that are causally connected. We provide strong evidence that the critical exponents depend on the temperature.
-
Emergence of giant strongly connected components in continuum disk-spin percolation
2016Co-Authors: Francesco Caravelli, Marco Bardoscia, Fabio CaccioliAbstract:We propose a continuum model of percolation in two dimensions for overlapping disks with spin. In this model the existence of bonds is determined by the distance between the centers of the disks, and by the scalar product of the (randomly) directed spin with the direction of the vector connecting the centers of neighboring disks. The direction of a single spin is controlled by a “temperature”, representing the amount of polarization of the spins in the direction of an external field. Our model is inspired by biological neuronal networks and aims to characterize their topological properties when axonal guidance plays a major role. We numerically study the phase diagram of the model observing the emergence of a giant strongly connected component, representing the portion of neurons that are causally connected. We provide strong evidence that the critical exponents depend on the temperature. ar X iv :1 51 1. 06 51 2v 2 [ co nd -m at .s ta tm ec h] 2 9 A pr 2 01 6 Emergence of giant SCC in continuum disk-spin percolation 2
