The Experts below are selected from a list of 315 Experts worldwide ranked by ideXlab platform
Pan Zheng - One of the best experts on this subject based on the ideXlab platform.
-
on the computational power of spiking neural p systems with self organization
Scientific Reports, 2016Co-Authors: Xun Wang, Tao Song, Faming Gong, Pan ZhengAbstract:Neural-like computing models are versatile computing mechanisms in the field of artificial intelligence. Spiking neural P systems (SN P systems for short) are one of the recently developed spiking neural network models inspired by the way neurons communicate. The communications among neurons are essentially achieved by spikes, i. e. short electrical pulses. In terms of motivation, SN P systems fall into the third generation of neural network models. In this study, a novel variant of SN P systems, namely SN P systems with self-organization, is introduced, and the computational power of the system is investigated and evaluated. It is proved that SN P systems with self-organization are capable of computing and accept the family of sets of Turing computable natural numbers. Moreover, with 87 neurons the system can compute any Turing computable Recursive Function, thus achieves Turing universality. These results demonstrate promising initiatives to solve an open problem arisen by Gh Păun.
Tao Song - One of the best experts on this subject based on the ideXlab platform.
-
on the computational power of spiking neural p systems with self organization
Scientific Reports, 2016Co-Authors: Xun Wang, Tao Song, Faming Gong, Pan ZhengAbstract:Neural-like computing models are versatile computing mechanisms in the field of artificial intelligence. Spiking neural P systems (SN P systems for short) are one of the recently developed spiking neural network models inspired by the way neurons communicate. The communications among neurons are essentially achieved by spikes, i. e. short electrical pulses. In terms of motivation, SN P systems fall into the third generation of neural network models. In this study, a novel variant of SN P systems, namely SN P systems with self-organization, is introduced, and the computational power of the system is investigated and evaluated. It is proved that SN P systems with self-organization are capable of computing and accept the family of sets of Turing computable natural numbers. Moreover, with 87 neurons the system can compute any Turing computable Recursive Function, thus achieves Turing universality. These results demonstrate promising initiatives to solve an open problem arisen by Gh Păun.
Alexander Krauss - One of the best experts on this subject based on the ideXlab platform.
-
Partial and Nested Recursive Function Definitions in Higher-order Logic
Journal of Automated Reasoning, 2010Co-Authors: Alexander KraussAbstract:Based on inductive definitions, we develop a tool that automates the definition of partial Recursive Functions in higher-order logic (HOL) and provides appropriate proof rules for reasoning about them. Termination is modeled by an inductive domain predicate which follows the structure of the recursion. Since a partial induction rule is available immediately, partial correctness properties can be proved before termination is established. It turns out that this modularity also facilitates termination arguments for total Functions, in particular for nested recursions. Our tool is implemented as a definitional package extending Isabelle/HOL. Various extensions provide convenience to the user: pattern matching, default values, tail recursion, mutual recursion and currying.
-
automating Recursive definitions and termination proofs in higher order logic
2009Co-Authors: Alexander KraussAbstract:The aim of this thesis is to provide an infrastructure for general Recursive Function definitions in a proof assistant based on higher-order logic (HOL) that has no native support for recursion or pattern matching. In the first part we develop a tool that automates Recursive Function definitions and provides appropriate proof rules for them. Compared to previous work, our package supports the definition of partial Functions, modeling the domain of the Function by an inductive domain predicate. An automatically-generated partial induction rule makes partial correctness proofs independent from termination proofs. This modularity considerably facilitates termination arguments for nested recursions. The second part addresses the problem of automatically solving the termination proof obligations that arise from Function definitions. Methods from the literature can be applied, but require significant adaptation to the specific needs of our setting: They must produce full formal proofs and work relative to a rich interactive theory. Our approach encompasses a rule-based selection of measure Functions, a simple control-flow analysis inspired by the dependency-pairs approach, and a modified version of the size-change principle based on certificates. A formalization of the full size-change principle is also provided. In the third part we discuss how pattern matching, which occurs frequently in Functional programming, can be supported in HOL Function definitions. We present a very general form of pattern matching, where arbitrary expressions can serve as patterns. We show how such patterns can be encoded using a custom matching combinator and how their consistency can be expressed in proof obligations. We also study the problem of transforming ML-style sequential pattern matching into minimal sets of independent equations, such that they are consistent in HOL. We relate the problem to the minimization problem for propositional DNF formulas and show that it is $\Sigma_2^P$-complete. We then develop a concrete algorithm that computes minimal patterns. As another application of the new set of tools, we show how user-specified induction schemes can be generated from simpler properties, which often makes their proofs fully automatic.
Eduardo D Sontag - One of the best experts on this subject based on the ideXlab platform.
-
on the computational power of neural nets
Journal of Computer and System Sciences, 1995Co-Authors: Hava T Siegelmann, Eduardo D SontagAbstract:This paper deals with finite size networks which consist of interconnections of synchronously evolving processors. Each processor updates its state by applying a "sigmoidal" Function to a linear combination of the previous states of all units. We prove that one may simulate all Turing machines by such nets. In particular, one can simulate any multi-stack Turing machine in real time, and there is a net made up of 886 processors which computes a universal partial-Recursive Function. Products (high order nets) are not required, contrary to what had been stated in the literature. Non-deterministic Turing machines can be simulated by non-deterministic rational nets, also in real time. The simulation result has many consequences regarding the decidability, or more generally the complexity, of questions about Recursive nets.
-
on the computational power of neural nets
Conference on Learning Theory, 1992Co-Authors: Hava T Siegelmann, Eduardo D SontagAbstract:This paper deals with finite networks which consist of interconnections of synchronously evolving processors. Each processor updates its state by applying a “sigmoidal” scalar nonlinearity to a linear combination of the previous states of all units. We prove that one may simulate all Turing Machines by rational nets. In particular, one can do this in linear time, and there is a net made up of about 1,000 processors which computes a universal partial-Recursive Function. Products (high order nets) are not required, contrary to what had been stated in the literature. Furthermore, we assert a similar theorem about non-deterministic Turing Machines. Consequences for undecidability and complexity issues about nets are discussed too.
Peter Altenbernd - One of the best experts on this subject based on the ideXlab platform.
-
Complete Worst-Case Execution Time Analysis of Straight-line Hard Real-Time Programs
1997Co-Authors: Friedhelm Stappert, Peter AltenberndAbstract:In this article, the problem of finding a tight estimate on the worst-case execution time (WCET) of a hard realtime program is addressed. The analysis is focused on straight-line code (without loops and Recursive Function calls) which is quite commonly found in synthesised code for embedded systems. A comprehensive timing analysis system covering both low-level (assembler instruction level) as well as high-level aspects (programming language level) is presented. The low-level analysis covers all speed-up mechanisms used for modern superscalar processors: pipelining, instruction-level parallelism and caching. The high-level analysis uses the results from the low-level to compute the final estimate on the WCET. This is done by a heuristic for searching the longest really executable path in the control flow, based on the Functional dependencies between various program parts
-
Complete Worst-Case Execution Time Analysis of Straight-line Hard Real-Time Programs
1997Co-Authors: Friedhelm Stappert, Peter Altenbernd, Straight-line Hard, Real-time ProgramsAbstract:In this article, the problem of finding a tight estimate on the worst-case execution time (WCET) of a real-time program is addressed. The analysis is focused on straight-line code (i.e. code without loops and Recursive Function calls) which is quite commonly found in synthesised code of hard real-time embedded systems. The analysis exploits the very simple structure of these programs, resulting in a considerable processing time improvement compared to general-case analysis techniques. A comprehensive timing analysis system, called the Program Timing Analyser (PTA), covering low-level aspects (on the assembler instruction level) as well as high-level aspects (on the programming language level) is presented. On one hand the low-level analysis covers all speed-up mechanisms used for modern superscalar processors: pipelining, instruction-level parallelism and caching. It can handle a unified cache as well as separate caches for data and instructions. The pipelined and parallel execution of..
