Arithmetic Complexity, Kleene Closure, and Formal Power Series

The aim of this paper is to use formal power series techniques to study the structure of small arithmetic complexity classes such as GapNC ¹ and GapL. More precisely, we apply the formal power series operations of inversion and root extraction to these complexity classes. We define a counting version of Kleene closure and show that it is intimately related to inversion and root extraction within GapNC ¹ and GapL. We prove that Kleene closure, inversion, and root extraction are all hard operations in the following sense: there is a language in AC ⁰ for which inversion and root extraction are GapL-complete and Kleene closure is NLOG-complete, and there is a finite set for which inversion and root extraction are GapNC ¹ -complete and Kleene closure is NC ¹ -complete, with respect to appropriate reducibilities. The latter result raises the question of classifying finite languages so that their inverses fall within interesting subclasses of GapNC ¹ , such as GapAC ⁰ . We initiate work in this direction by classifying the complexity of the Kleene closure of finite languages. We formulate the problem in terms of finite monoids and relate its complexity to the internal structure of the monoid. Some results in this paper show properties of complexity classes that are interesting independent of formal power series considerations, including some useful closure properties and complete problems for GapL.     

Formal Power Series

We present a formalization of the topological ring of formal power series in Isabelle/HOL. We also formalize formal derivatives, division, radicals, composition and reverses. As an application, we show how formal elementary and hyper-geometric series yield elegant proofs for some combinatorial identities. We easily derive a basic theory of polynomials. Then, using a generic formalization of the fraction field of an integral domain, we obtain formal Laurent series and rational functions for free.     

On Aperiodic and Star-Free Formal Power Series in Partially Commuting Variables

Formal power series over non-commuting variables have been investigated as representations of the behavior of automata with multiplicities. Here we introduce and investigate the concepts of aperiodic and of star-free formal power series over semirings and partially commuting variables. We prove that if the semiring K is idempotent and commutative, or if K is idempotent and the variables are non-commuting, then the product of any two aperiodic series is again aperiodic. We also show that if K is idempotent and the matrix monoids over K have a Burnside property (satisfied, e.g. by the tropical semiring), then the aperiodic and the star-free series coincide. This generalizes a classical result of Schützenberger (Inf. Control 4:245–270, 1961) for aperiodic regular languages and subsumes a result of Guaiana et al. (Theor. Comput. Sci. 97:301–311, 1992) on aperiodic trace languages. This work partly supported by the DAAD-PROCOPE project Temporal and Quantitative Analysis of Distributed Systems.     

Generic Complexity of Presburger Arithmetic

Fischer and Rabin proved in (Proceedings of the SIAM-AMS Symposium in Applied Mathematics, vol. 7, pp. 27–41, 1974) that the decision problem for Presburger Arithmetic has at least double exponential worst-case complexity (for deterministic and for nondeterministic Turing machines). In Kapovich et al. (J. Algebra 264(2):665–694, 2003) a theory of generic-case complexity was developed, where algorithmic problems are studied on “most” inputs instead of set of all inputs. A question rises about existing of more efficient (say, polynomial) generic algorithm deciding Presburger Arithmetic on a set of closed formulas of asymptotic density 1. We prove in this paper that there is not an exponential generic decision algorithm working correctly on an input set of asymptotic density exponentially converging to 1 (so-called strongly generic sets).     

快速包络线算法的设计和实现

通过对包络线求取过程的分析,得出快速包络线算法原理,讨论了该算法应该注意的一些问题,并提出了辅助算法,解决了芯片和IC生产线图像诊断系统中不能准确快速求取包络线的难题.     

快速包络线算法的设计和实现

通过对包络线求取过程的分析,得出快速包络线算法原理，讨论了该算法应该注意的一些问题，并提出了辅助算法，解决了芯片和IC生产线图像诊断系统中不能准确快速求取包络线的难题。     

Extension Complexity of Formal Languages

Theory of Computing Systems - In this article we undertake a study of extension complexity from the perspective of formal languages. We define a natural way to associate a family of polytopes with...     

The Arithmetic Complexity of Tensor Contraction

We investigate the algebraic complexity of tensor calculus. We consider a generalization of iterated matrix product to tensors and show that the resulting formulas exactly capture VP, the class of polynomial families efficiently computable by arithmetic circuits. This gives a natural and robust characterization of this complexity class that despite its naturalness is not very well understood so far.     

Dijkstra, Floyd and Warshall meet Kleene

Around 1960, Dijkstra, Floyd and Warshall published papers on algorithms for solving single-source and all-sources shortest path problems, respectively. These algorithms, nowadays named after their inventors, are well known and well established. This paper sheds an algebraic light on these algorithms. We combine the shortest path problems with Kleene algebra, also known as Conway’s regular algebra. This view yields a purely algebraic version of Dijkstra’s shortest path algorithm and the one by Floyd/Warshall. Moreover, the algebraic abstraction yields applications of these algorithms to structures different from graphs and pinpoints the mathematical requirements on the underlying cost algebra that ensure their correctness.     

Kleene Algebra and Bytecode Verification

Most standard approaches to the static analysis of programs, such as the popular worklist method, are first-order methods that inductively annotate program points with abstract values. In [6] we introduced a second-order approach based on Kleene algebra. In this approach, the primary objects of interest are not the abstract data values, but the transfer functions that manipulate them. These elements form a left-handed Kleene algebra. The dataflow labeling is not achieved by inductively labeling the program with abstract values, but rather by computing the star (Kleene closure) of a matrix of transfer functions. In this paper we show how this general framework applies to the problem of Java bytecode verification. We show how to specify transfer functions arising in Java bytecode verification in such a way that the Kleene algebra operations (join, composition, star) can be computed efficiently. We also give a hybrid dataflow analysis algorithm that computes the closure of a matrix on a cutset of the control flow graph, thereby avoiding the recalculation of dataflow information when there are cycles in the graph. This method could potentially improve the performance over the standard worklist algorithm when a small cutset can be found.     

Kleene modules and linear languages

A Kleene algebra (K, +, ·, *, 0, 1) is an idempotent semiring with an iteration * as axiomatised by Kozen. We consider left semiring modules (A, +, 0, :) over Kleene algebras. We call such a left semiring module a Kleene module if each linear equation x = a + r : x has a least solution, where : is the product from K × A to A. The linear context-free languages can be viewed as a Kleene module A over a Kleene algebra R of binary regular word relations. Thus, the simultaneous linear fixed-point operator μ on languages can be reduced to iteration * on R and the scalar product :.     

电力变压器综合保护算法与实现

针对常规继电保护装置功能单一的缺点,应用DSP,开发了集测量、控制和保护一体化的电力变压器计算机综合保护系统。在保护算法方面,综合考虑了算法的精确性、可靠性、计算量及响应速度后,决定以相关算法作为主要的算法。该算法利用变压器两侧电流的互相关函数值来判别变压器的各种运行状态。该系统已应用到某石化公司的25000 kVA电力变压器上,经过两年的运行,保护动作的正确率大于98%以上。     

Kleene chain completeness and fixedpoint properties

Let L denote the nonscalar complexity in k(x₁,…, x_n). We prove $\text{L(?,??/?x}{}_1\text{,…,??/?x}{}_{\mathrm{n}}\text{)?3L(?)}$. Using this we determine the complexity of single power sums, single elementary symmetric functions, the resultant and the discriminant as root functions, up to order of magnitude. Also we linearly reduce matrix inversion to computing the determinant.     

Formal Solutions of Linear Ordinary Differential Equations Containing m-Hypergeometric Series

Let a linear homogeneous ordinary differential equation with polynomial coefficients over a field be given. For a singular point of the equation, the fundamental system of formal solutions that contain a finite number of power series with coefficients belonging to the algebraic extension of can be constructed by known algorithms. In this paper, an algorithm is suggested for construction of a space of formal solutions such that all series containing in these solutions have m-hypergeometric coefficients. The implementation of the algorithm in the computer algebra system Maple is discussed.     

On the Power of Las Vegas for One-Way Communication Complexity, OBDDs, and Finite Automata

The study of the computational power of randomized computations is one of the central tasks of complexity theory. The main goal of this paper is the comparison of the power of Las Vegas computation and deterministic respectively nondeterministic computation. We investigate the power of Las Vegas computation for the complexity measures of one-way communication, ordered binary decision diagrams, and finite automata.(i) For the one-way communication complexity of two-party protocols we show that Las Vegas communication can save at most one half of the deterministic one-way communication complexity. We also present a language for which this gap is tight.(ii) The result (i) is applied to show an at most polynomial gap between determinism and Las Vegas for ordered binary decision diagrams.(iii) For the size (i.e., the number of states) of finite automata we show that the size of Las Vegas finite automata recognizing a language L is at least the square root of the size of the minimal deterministic finite automaton recognizing L. Using a specific language we verify the optimality of this lower bound.