In this paper we establish how alphabet size, treewidth and maximum degree of the underlying graph are key parameters which influence the overall computational complexity of finite freezing automata networks. First, w...
详细信息
In this paper we establish how alphabet size, treewidth and maximum degree of the underlying graph are key parameters which influence the overall computational complexity of finite freezing automata networks. First, we define a general decision problem, called Specification Checking Problem, that captures many classical decision problems such as prediction, nilpotency, predecessor, asynchronous reachability. Then, we present a fast -parallel algorithm that solves the general model checking problem when the three parameters are bounded, hence showing that the problem is in NC. Moreover, we show that the problem is in XP on the parameters tree -width and maximum degree. Finally, we show that these problems are hard from two different perspectives. First, the general problem is W[2] -hard when taking either treewidth or alphabet as single parameter and fixing the others. Second, the classical problems are hard in their respective classes when restricted to families of graph with sufficiently large treewidth. (c) 2024 Elsevier Inc. All rights reserved.
In this paper we study the family of two-state Totalistic Freezing Cellular Automata (TFCA) defined over the triangular and square grids with von Neumann neighborhoods. We say that a Cellular Automaton is Freezing and...
详细信息
In this paper we study the family of two-state Totalistic Freezing Cellular Automata (TFCA) defined over the triangular and square grids with von Neumann neighborhoods. We say that a Cellular Automaton is Freezing and Totalistic if the active cells remain unchanged, and the new value of an inactive cell depends only on the sum of its active neighbors. We classify all the Cellular Automata in the class of TFCA, grouping them in five different classes: the Trivial rules, Turing Universal rules, Algebraic rules, Topological rules and Fractal Growing rules. At the same time, we study in this family the STABILITY problem, consisting in deciding whether an inactive cell becomes active, given an initial configuration. We exploit the properties of the automata in each group to show that: For Algebraic and Topological Rules the STABILITY problem is in NC. For Turing Universal rules the STABILITY problem is P-Complete. (C) 2020 Elsevier Inc. All rights reserved.
AC/DC converters are important components in many industrial applications. Their optimal operation is thus of growing relevance in the recent years. In the state of the art, optimal (nonlinear) control of AC/DC conver...
详细信息
AC/DC converters are important components in many industrial applications. Their optimal operation is thus of growing relevance in the recent years. In the state of the art, optimal (nonlinear) control of AC/DC converters frequently focuses on finite set or explicit model predictive control (MPC) strategies. The main drawback is that their computational effort exponentially increases with the length of the prediction horizon and thus, only very short horizons (2 or 3-times the sampling time) are practically feasible. This can yield a significant limitation of the achievable control accuracy. Thus, in this paper a nonlinear MPC strategy is proposed, which allows for rather long prediction horizons while keeping the computational effort low. Furthermore, the MPC strategy is formulated in a way that it is tailored to the implementation on FPGAs, utilizing its inherent parallel computation capabilities. It is shown by means of simulation results that a high control accuracy and robustness to external disturbances can be achieved. Furthermore, it is discussed that the proposed MPC allows for computation times in the lower mu s range on an FPGA. (C) 2019, IFAC (International Federation of Automatic Control) Hosting by Elsevier Ltd. All rights reserved.
AC/DC converters are important components in many industrial applications. Their optimal operation is thus of growing relevance in the recent years. In the state of the art, optimal (nonlinear) control of AC/DC conver...
详细信息
AC/DC converters are important components in many industrial applications. Their optimal operation is thus of growing relevance in the recent years. In the state of the art, optimal (nonlinear) control of AC/DC converters frequently focuses on finite set or explicit model predictive control (MPC) strategies. The main drawback is that their computational effort exponentially increases with the length of the prediction horizon and thus, only very short horizons (2 or 3-times the sampling time) are practically feasible. This can yield a significant limitation of the achievable control accuracy. Thus, in this paper a nonlinear MPC strategy is proposed, which allows for rather long prediction horizons while keeping the computational effort low. Furthermore, the MPC strategy is formulated in a way that it is tailored to the implementation on FPGAs, utilizing its inherent parallel computation capabilities. It is shown by means of simulation results that a high control accuracy and robustness to external disturbances can be achieved. Furthermore, it is discussed that the proposed MPC allows for computation times in the lower µ s range on an FPGA.
Positive semidefinite programs are an important subclass of semidefinite programs in which all matrices involved in the specification of the problem are positive semidefinite and all scalars involved are non-negative....
详细信息
ISBN:
(纸本)9780769545714
Positive semidefinite programs are an important subclass of semidefinite programs in which all matrices involved in the specification of the problem are positive semidefinite and all scalars involved are non-negative. We present a parallel algorithm, which given an instance of a positive semidefinite program of size N and an approximation factor epsilon > 0, runs in (parallel) time poly(1/epsilon) . polylog (N), using poly(N) processors, and outputs a value which is within multiplicative factor of (1 + epsilon) to the optimal. Our result generalizes analogous result of Luby and Nisan [10] for positive linear programs and our algorithm is inspired by the algorithm of [10].
Using recent absolute irreducibility testing algorithms, we derive new irreducibility forms. These are integer polynomials in variables which are the generic coefficients of a multivariate polynomial of a given degree...
详细信息
Using recent absolute irreducibility testing algorithms, we derive new irreducibility forms. These are integer polynomials in variables which are the generic coefficients of a multivariate polynomial of a given degree. A (multivariate) polynomial over a specific field is said to be absolutely irreducible if it is irreducible over the algebraic closure of its coefficient field. A specific polynomial of a certain degree is absolutely irreducible, if and only if all the corresponding irreducibility forms vanish when evaluated at the coefficients of the specific polynomial. Our forms have much smaller degrees and coefficients than the forms derived originally by Emmy Noether. We can also apply our estimates to derive more effective versions of irreducibility theorems by Ostrowski and Deuring and of the Hilbert irreducibility theorem. We also give an effective estimate on the diameter of the neighborhood of an absolutely irreducible polynomial with respect to the coefficient space in which absolute irreducibility is preserved. Furthermore, we can apply the effective estimates to derive several factorization results in parallel computational complexity theory: we show how to compute arbitrary high precision approximations of the complex factors of a multivariate integral polynomial and how to count the number of absolutely irreducible factors of a multivariate polynomial with coefficients in a rational function field, both in the complexity class NC. The factorization results also extend to the case where the coefficient field is a function field. (C) 1995 Academic Press, Inc.
A fast algorithm for Linear Quadratic (LQ) control with linear equality constraints is derived and exploited for stabilizing predictive control synthesis. The algorithm requires only O ( Nn ) computations for an n th ...
详细信息
A fast algorithm for Linear Quadratic (LQ) control with linear equality constraints is derived and exploited for stabilizing predictive control synthesis. The algorithm requires only O ( Nn ) computations for an n th order plant and N -steps prediction horizon, and possesses a remarkable numerical accuracy.
暂无评论