The Experts below are selected from a list of 303 Experts worldwide ranked by ideXlab platform
Jérôme Leroux - One of the best experts on this subject based on the ideXlab platform.
-
Reachability in Two-Dimensional Vector Addition Systems with States: One Test is for Free
arXiv: Logic in Computer Science, 2020Co-Authors: Jérôme Leroux, Grégoire SutreAbstract:Vector Addition system with states is an ubiquitous model of computation with extensive applications in computer science. The reachability problem for Vector Addition systems is central since many other problems reduce to that question. The problem is decidable and it was recently proved that the dimension of the Vector Addition system is an important parameter of the complexity. In fixed dimensions larger than two, the complexity is not known (with huge complexity gaps). In dimension two, the reachability problem was shown to be PSPACE-complete by Blondin et al. in 2015. We consider an extension of this model, called 2-TVASS, where the first counter can be tested for zero. This model naturally extends the classical model of one counter automata (OCA). We show that reachability is still solvable in polynomial space for 2-TVASS. As in the work Blondin et al., our approach relies on the existence of small reachability certificates obtained by concatenating polynomially many cycles.
-
Reachability in Vector Addition Systems is Primitive-Recursive in Fixed Dimension
2019Co-Authors: Jérôme Leroux, Sylvain SchmitzAbstract:The reachability problem in Vector Addition systems is a central question, not only for the static verification of these systems, but also for many inter-reducible decision problems occurring in various fields. The currently best known upper bound on this problem is not primitive-recursive, even when considering systems of fixed dimension. We provide significant refinements to the classical decomposition algorithm of Mayr, Kosaraju, and Lambert and to its termination proof, which yield an ACKERMANN upper bound in the general case, and primitive-recursive upper bounds in fixed dimension. While this does not match the currently best known TOWER lower bound for reachability, it is optimal for related problems.
-
LICS - Reachability in Vector Addition Systems is Primitive-Recursive in Fixed Dimension
2019 34th Annual ACM IEEE Symposium on Logic in Computer Science (LICS), 2019Co-Authors: Jérôme Leroux, Sylvain SchmitzAbstract:The reachability problem in Vector Addition systems is a central question, not only for the static verification of these systems, but also for many inter-reducible decision problems occurring in various fields. The currently best known upper bound on this problem is not primitive-recursive, even when considering systems of fixed dimension. We provide significant refinements to the classical decomposition algorithm of Mayr, Kosaraju, and Lambert and to its termination proof, which yield an ACKERMANN upper bound in the general case, and primitive-recursive upper bounds in fixed dimension. While this does not match the currently best known TOWER lower bound for reachability, it is optimal for related problems.
-
Polynomial Vector Addition Systems With States
2018Co-Authors: Jérôme LerouxAbstract:The reachability problem for Vector Addition systems is one of the most difficult and central problem in theoretical computer science. The problem is known to be decidable, but despite instance investigations during the last four decades, the exact complexity is still open. For some sub-classes, the complexity of the reachability problem is known. Structurally bounded Vector Addition systems, the class of Vector Addition systems with finite reachability sets from any initial configuration, is one of those classes. In fact, the reachability problem was shown to be polynomial-space complete for that class by Praveen and Lodaya in 2008. Surprisingly, extending this property to Vector Addition systems with states is open. In fact, there exist Vector Addition systems with states that are structurally bounded but with Ackermannian large sets of reachable configurations. It follows that the reachability problem for that class is between exponential space and Ackermannian. In this paper we introduce the class of polynomial Vector Addition systems with states, defined as the class of Vector Addition systems with states with size of reachable configurations bounded polynomially in the size of the initial ones. We prove that the reachability problem for polynomial Vector Addition systems is exponential-space complete. Additionally, we show that we can decide in polynomial time if a Vector Addition system with states is polynomial. This characterization introduces the notion of iteration scheme with potential applications to the reachability problem for general Vector Addition systems.
-
Ideal Decompositions for Vector Addition Systems
2016Co-Authors: Jérôme Leroux, Sylvain SchmitzAbstract:Vector Addition systems, or equivalently Petri nets, are one of the most popular formal models for the representation and the analysis of parallel processes. Many problems for Vector Addition systems are known to be decidable thanks to the theory of well-structured transition systems. Indeed, Vector Addition systems with configurations equipped with the classical point-wise ordering are well-structured transition systems. Based on this observation, problems like coverability or termination can be proven decidable. However, the theory of well-structured transition systems does not explain the decidability of the reachability problem. In this presentation, we show that runs of Vector Addition systems can also be equipped with a well quasi-order. This observation provides a unified understanding of the data structures involved in solving many problems for Vector Addition systems, including the central reachability problem.
Sylvain Schmitz - One of the best experts on this subject based on the ideXlab platform.
-
RP - Coverability Is Undecidable in One-Dimensional Pushdown Vector Addition Systems with Resets
Lecture Notes in Computer Science, 2019Co-Authors: Sylvain Schmitz, Georg ZetzscheAbstract:We consider the model of pushdown Vector Addition systems with resets. These consist of Vector Addition systems that have access to a pushdown stack and have instructions to reset counters. For this model, we study the coverability problem. In the absence of resets, this problem is known to be decidable for one-dimensional pushdown Vector Addition systems, but decidability is open for general pushdown Vector Addition systems. Moreover, coverability is known to be decidable for reset Vector Addition systems without a pushdown stack. We show in this note that the problem is undecidable for one-dimensional pushdown Vector Addition systems with resets.
-
Reachability in Vector Addition Systems is Primitive-Recursive in Fixed Dimension
2019Co-Authors: Jérôme Leroux, Sylvain SchmitzAbstract:The reachability problem in Vector Addition systems is a central question, not only for the static verification of these systems, but also for many inter-reducible decision problems occurring in various fields. The currently best known upper bound on this problem is not primitive-recursive, even when considering systems of fixed dimension. We provide significant refinements to the classical decomposition algorithm of Mayr, Kosaraju, and Lambert and to its termination proof, which yield an ACKERMANN upper bound in the general case, and primitive-recursive upper bounds in fixed dimension. While this does not match the currently best known TOWER lower bound for reachability, it is optimal for related problems.
-
LICS - Reachability in Vector Addition Systems is Primitive-Recursive in Fixed Dimension
2019 34th Annual ACM IEEE Symposium on Logic in Computer Science (LICS), 2019Co-Authors: Jérôme Leroux, Sylvain SchmitzAbstract:The reachability problem in Vector Addition systems is a central question, not only for the static verification of these systems, but also for many inter-reducible decision problems occurring in various fields. The currently best known upper bound on this problem is not primitive-recursive, even when considering systems of fixed dimension. We provide significant refinements to the classical decomposition algorithm of Mayr, Kosaraju, and Lambert and to its termination proof, which yield an ACKERMANN upper bound in the general case, and primitive-recursive upper bounds in fixed dimension. While this does not match the currently best known TOWER lower bound for reachability, it is optimal for related problems.
-
The complexity of reachability in Vector Addition systems
ACM SIGLOG News, 2016Co-Authors: Sylvain SchmitzAbstract:The program of the 30th Symposium on Logic in Computer Science held in 2015 in Kyoto included two contributions on the computational complexity of the reachability problem for Vector Addition systems: Blondin, Finkel, Goller, Haase, and McKenzie [2015] attacked the problem by providing the first tight complexity bounds in the case of dimension 2 systems with states, while Leroux and Schmitz [2015] proved the first complexity upper bound in the general case. The purpose of this column is to present the main ideas behind these two results, and more generally survey the current state of affairs.
-
Ideal Decompositions for Vector Addition Systems
2016Co-Authors: Jérôme Leroux, Sylvain SchmitzAbstract:Vector Addition systems, or equivalently Petri nets, are one of the most popular formal models for the representation and the analysis of parallel processes. Many problems for Vector Addition systems are known to be decidable thanks to the theory of well-structured transition systems. Indeed, Vector Addition systems with configurations equipped with the classical point-wise ordering are well-structured transition systems. Based on this observation, problems like coverability or termination can be proven decidable. However, the theory of well-structured transition systems does not explain the decidability of the reachability problem. In this presentation, we show that runs of Vector Addition systems can also be equipped with a well quasi-order. This observation provides a unified understanding of the data structures involved in solving many problems for Vector Addition systems, including the central reachability problem.
A S Krishnakumar - One of the best experts on this subject based on the ideXlab platform.
-
reachability and recurrence in extended finite state machines modular Vector Addition systems
Computer Aided Verification, 1993Co-Authors: A S KrishnakumarAbstract:In this paper, a formal model of Extended Finite State Machines (EFSMs) is proposed and an approach to their analysis is suggested. The state of an EFSM is captured by its configuration. A class of EFSMs, called Modular Vector Addition Systems (MVAS), is defined and analyzed. Modular Vector Addition Systems cover a significant subset of models used in communication protocols and behavioral synthesis of hardware. For this class of EFSMs, an algorithm to compute the set of configurations reachable from an initial configuration is presented. This algorithm may also be used to compute the set of recurrent configurations. Knowledge of these sets is useful in verification, testing, and optimization of EFSM models. A compact representation of these sets and a simple test for membership for such representations are also presented.
-
CAV - Reachability and Recurrence in Extended Finite State Machines: Modular Vector Addition Systems
Computer Aided Verification, 1993Co-Authors: A S KrishnakumarAbstract:In this paper, a formal model of Extended Finite State Machines (EFSMs) is proposed and an approach to their analysis is suggested. The state of an EFSM is captured by its configuration. A class of EFSMs, called Modular Vector Addition Systems (MVAS), is defined and analyzed. Modular Vector Addition Systems cover a significant subset of models used in communication protocols and behavioral synthesis of hardware. For this class of EFSMs, an algorithm to compute the set of configurations reachable from an initial configuration is presented. This algorithm may also be used to compute the set of recurrent configurations. Knowledge of these sets is useful in verification, testing, and optimization of EFSM models. A compact representation of these sets and a simple test for membership for such representations are also presented.
Habibollah Abiri - One of the best experts on this subject based on the ideXlab platform.
-
Rotational Vector Addition Theorem and Its Effect on T-Matrix
IEEE Transactions on Antennas and Propagation, 2011Co-Authors: M. S. Khajeahsani, Farzad Mohajeri, Habibollah AbiriAbstract:Translation is a degree of freedom used in the analysis of random media scattering. An analytical method is presented for rotational degree of freedom in such problems. Vector Addition theorem for rotation of a Vector spherical wave with zero divergence has been proved through the use of a Vector rotation operator. The relation between T-matrices for an object in two different concentric coordinate systems is formulated by applying the Addition theorem. The relationship between the two coordinate systems is also shown by Euler angles.
M. S. Khajeahsani - One of the best experts on this subject based on the ideXlab platform.
-
Rotational Vector Addition Theorem and Its Effect on T-Matrix
IEEE Transactions on Antennas and Propagation, 2011Co-Authors: M. S. Khajeahsani, Farzad Mohajeri, Habibollah AbiriAbstract:Translation is a degree of freedom used in the analysis of random media scattering. An analytical method is presented for rotational degree of freedom in such problems. Vector Addition theorem for rotation of a Vector spherical wave with zero divergence has been proved through the use of a Vector rotation operator. The relation between T-matrices for an object in two different concentric coordinate systems is formulated by applying the Addition theorem. The relationship between the two coordinate systems is also shown by Euler angles.
-
Rotational Vector Addition Theorem and Its Effect on T-matrix
2010Co-Authors: M. S. Khajeahsani, Farzad MohajeriAbstract:In this paper we prove the Vector Addition theorem for rotation of Vector spherical wave with zero divergence by the use of Vector rotation operator. In this theorem a rotated Vector spherical wave function is extended by fixed Vector spherical wave functions. Then by the use of this theorem the relation between T-matrices for one object in two different concentric coordinate systems is formulated. Also, the relation between two coordinate systems is considered by Euler angles.
