Networks of evolutionary processors: the power of subregular filters

In this paper, we propose a hierarchy of families of languages generated by networks of evolutionary processors where the filters belong to several special classes of regular sets. More precisely, we show that the use of filters from the class of ordered, non-counting, power-separating, circular, suffix-closed regular, union-free, definite, and combinational languages is as powerful as the use of arbitrary regular languages and yields networks that can generate all the recursively enumerable languages. On the other hand, the use of filters that are only finite languages allows only the generation of regular languages, but not every regular language can be generated. If we use filters that are monoids, nilpotent languages, or commutative regular languages, we obtain one and the same family of languages which contains non-context-free languages but not all regular languages. These results seem to be of interest because they provide both upper and lower bounds on the families of languages that one can use as filters in a network of evolutionary processors in order to obtain a complete computational model.     

Accepting Networks of Evolutionary Processors with Subregular Filters

We propose a new variant of Accepting Networks of Evolutionary Processors, in which the operations are applied at arbitrary positions to the processed words (rather than at the ends of words only) and where the filters are languages from several special classes of regular sets. More precisely, we show that the use of filters from the class of non-counting, ordered, power-separating, suffix-closed regular, union-free, definite and combinational languages is as powerful as the use of arbitrary regular languages and yields networks that can accept all the recursively enumerable languages. On the other hand, by using filters that are only finite languages, monoids, nilpotent languages, commutative regular languages, or circular regular languages, one cannot generate all recursively enumerable languages. These results seem interesting as they provide both upper and lower bounds on the classes of languages that one can use as filters in an accepting network of evolutionary processors in order to obtain a complete computational model.     

The role of evolutionary operations in accepting hybrid networks of evolutionary processors

In this paper, we investigate the role of evolutionary operations in accepting hybrid networks of evolutionary processors (AHNEP for short) in the following way. We consider AHNEPs with all the nodes specialized in only one evolutionary operation (substitution, insertion, or deletion) or in two operations out of these three. The considered variants differ in two respects: filters that are used to control the exchange of information (we use random context conditions and regular languages as filters) and the way of accepting the input word (at least one output node or all output nodes are non-empty at some moment in the computation). The computational power of all these variants is studied.     

On regular realizability problems for context-free languages

We consider regular realizability problems, which consist in verifying whether the intersection of a regular language which is the problem input and a fixed language (filter) which is a parameter of the problem is nonempty. We study the algorithmic complexity of regular realizability problems for context-free filters. This characteristic is consistent with the rational dominance relation of CF languages. However, as we prove, it is more rough. We also give examples of both P-complete and NL-complete regular realizability problems for CF filters. Furthermore, we give an example of a subclass of CF languages for filters of which the regular realizability problems can have an intermediate complexity. These are languages with polynomially bounded rational indices.     

Coherence checking and propagation of lower probability bounds

 In this paper we use imprecise probabilities, based on a concept of generalized coherence (g-coherence), for the management of uncertain knowledge and vague information. We face the problem of reducing the computational difficulties in g-coherence checking and propagation of lower conditional probability bounds. We examine a procedure, based on linear systems with a reduced number of unknowns, for the checking of g-coherence. We propose an iterative algorithm to determine the reduced linear systems. Based on the same ideas, we give an algorithm for the propagation of lower probability bounds. We also give some theoretical results that allow, by suitably modifying our algorithms, the g-coherence checking and propagation by working with a reduced set of variables and/or with a reduced set of constraints. Finally, we apply our algorithms to some examples. RID="*" ID="*" This paper is a revised and substantially extended version of a previous paper by the same authors, appeared in the Proc. of the 5th Workshop on Uncertainty Processing (WUPES'2000), Jindřichu̇v Hradec, Czech Republic, June 21–24, 1–13, 2000.     

Regular languages and stone duality

We give a new account of the relationships among varieties of regular languages, varieties of finite semigroups, and their characterization in terms of “implicit identities.” Our development, which is essentially topological in character, is based on the duality (established by Stone) between Boolean algebras and certain topological spaces (which are now called “Stone spaces”). This duality does not seem to have been recognized in the literature on regular languages, even though it is well known that the regular languages over a fixed alphabet form a Boolean algebra and that the “implicit operations” with a fixed number of operands form a Stone space. This research was partially supported by an NSERC Operating Grant.     

Permutation rewriting and algorithmic verification

We propose a natural subclass of regular languages (Alphabetic Pattern Constraints, APC) which is effectively closed under permutation rewriting, i.e., under iterative application of rules of the form ab → ba. It is well-known that regular languages do not have this closure property, in general. Our result can be applied for example to regular model checking, for verifying properties of parametrized linear networks of regular processes, and for modeling and verifying properties of asynchronous distributed systems. We also consider the complexity of testing membership in APC and show that the question is complete for PSPACE when the input is an NFA, and complete for NLOGSPACE when it is a DFA. Moreover, we show that both the inclusion problem and the question of closure under permutation rewriting are PSPACE-complete when we restrict to the class APC.     

Computational ludics

We reformulate the theory of ludics introduced by J.-Y. Girard from a computational point of view. We introduce a handy term syntax for designs, the main objects of ludics. Our syntax also incorporates explicit cuts for attaining computational expressivity. In addition, we consider design generators that allow for finite representation of some infinite designs. A normalization procedure in the style of Krivine’s abstract machine directly works on generators, giving rise to an effective means of computation over infinite designs.The acceptance relation between machines and words, a basic concept in computability theory, is well expressed in ludics by the orthogonality relation between designs. Fundamental properties of ludics are then discussed in this concrete context. We prove three characterization results that clarify the computational powers of three classes of designs. (i) Arbitrary designs may capture arbitrary sets of finite data. (ii) When restricted to finitely generated ones, designs exactly capture the recursively enumerable languages. (iii) When further restricted to cut-free ones as in Girard’s original definition, designs exactly capture the regular languages.We finally describe a way of defining data sets by means of logical connectives, where the internal completeness theorem plays an essential role.     

The Kleinman Iteration for Nonstabilizable Systems

 We consider the computation of Hermitian nonnegative definite solutions of algebraic Riccati equations. These solutions are the limit, P=lim_{i →∞} P _i, of a sequence of matrices obtained by solving a sequence of Lyapunov equations. The procedure parallels the well-known Kleinman technique but the stabilizability condition on the underlying linear time-invariant system is removed. The convergence of the constructed sequence {P _i }_i≥1 is guaranteed by the minimality of P _i in the set of Hermitian nonnegative definite solutions of the Lyapunov equation in the ith iteration step. Date received: October 21, 1999. Date revised: February 14, 2002. RID="*" ID="*"This work was supported by the Acciones Integradas programme of Deutscher Akademischer Austauschdienst (Germany) and Dirección General de Infraestructura y Relaciones Internacionales (Spain).     

A new neural network technique for the design of multilayered microwave shielded bandpass filters

In this work, we propose a novel technique based on neural networks, for the design of microwave filters in shielded printed technology. The technique uses radial basis function neural networks to represent the non linear relations between the quality factors and coupling coefficients, with the geometrical dimensions of the resonators. The radial basis function neural networks are employed for the first time in the design task of shielded printed filters, and permit a fast and precise operation with only a limited set of training data. Thanks to a new cascade configuration, a set of two neural networks provide the dimensions of the complete filter in a fast and accurate way. To improve the calculation of the geometrical dimensions, the neural networks can take as inputs both electrical parameters and physical dimensions computed by other neural networks. The neural network technique is combined with gradient based optimization methods to further improve the response of the filters. Results are presented to demonstrate the usefulness of the proposed technique for the design of practical microwave printed coupled line and hairpin filters. © 2008 Wiley Periodicals, Inc. Int J RF and Microwave CAE, 2009.     

Backstepping in Infinite Dimension for a Class of Parabolic Distributed Parameter Systems

 In this paper a family of stabilizing boundary feedback control laws for a class of linear parabolic PDEs motivated by engineering applications is presented. The design procedure presented here can handle systems with an arbitrary finite number of open-loop unstable eigenvalues and is not restricted to a particular type of boundary actuation. Stabilization is achieved through the design of coordinate transformations that have the form of recursive relationships. The fundamental difficulty of such transformations is that the recursion has an infinite number of iterations. The problem of feedback gains growing unbounded as the grid becomes infinitely fine is resolved by a proper choice of the target system to which the original system is transformed. We show how to design coordinate transformations such that they are sufficiently regular (not continuous but L _∞). We then establish closed-loop stability, regularity of control, and regularity of solutions of the PDE. The result is accompanied by a simulation study for a linearization of a tubular chemical reactor around an unstable steady state. Date received: June 22, 2001. Date revised: January 17, 2002. RID="*" ID="*"This work was supported by grants from AFOSR, ONR, and NSF.     

(DNA) computing by carving

 Inspired by the experiments reported recently in the emerging area of DNA computing, we consider a somewhat unusual type of a computation strategy: generate a (large) set of candidate solutions of a problem, then remove the non-solutions such that what remains is the set of solutions. We call this a computation by carving. This leads both to a speculation with possible important consequences and to interesting theoretical computer science (formal language) questions. The speculation is that in this way we can “compute” non-recursively enumerable languages, because the family of recursively enumerable languages is not closed under complementation. The formal language theory questions concern sequences of languages with certain regularities, needed as languages to be extracted from the total language of candidate solutions of a problem. Specifically, we consider sequences of languages obtained by starting from a given regular language and iteratively applying to it a given finite state sequential transducer (a gsm). Computing by carving with respect to such a sequence of languages can identify all context-sensitive languages and can also lead to non-recursively enumerable languages (but not all recursively enumerable languages can be obtained in this way). In practical circumstances, the carving process should be finite, hence, in general, approximations of the desired language are obtained. We also briefly discuss this aspect.     

On some operations on strings suggested by gene assembly in ciliates

We define three operations on strings and languages suggested by the process of gene assembly in hypotrichous ciliates. This process is considered to be a prine example of DNA computing in vivo. This paper is devoted to some computational aspects of these operations from a formal language point of view. The closure of the classes of regular and context-free languages under these operations is settled. Then, we consider theld-macronuclear language of a given languageL, which consists of allld-macronuclear strings obtained from the strings ofL by iteratively applying the loop-direct repeat-excision. Finally, we discuss some open problems and further directions of research. Rudolf Freund: He received his master and doctor degree in computer science from the Vienna University of Technology, Austria, in 1980 and 1982, respectively. In 1986, he received his master degree in mathematics and physics from the University Vienna, Austria. In 1988 he joined the Vienna University of Technology in Austria, where he became an Associate Professor in September 1995. He has given various lectures in theoretical computer science, especially on formal languages and automata. His research interests include array and graph grammars, regulated rewritung, infinite words, syntactic pattern recognition, neural networks, and especially models and systems for biological computing. In these fields he is author of more than sixty scientific papers. Carlos Martín-Vide: He is Professor and Head of the Research Group on Mathematical Linguistics at Rovira i Virgili University, Tarragona, Spain. His specialities are formal language theory and mathematical linguistics. His last volume edited is Where Mathematics, Computer Science, Linguistics and Biology Meet (Kluwer, 2001, with V. Mitrana). He published 150 papers in conference proceedings and journals such as: Acta Informatica, BioSystems. Computational Linguistics, Computers and Artificial Intelligence, Information Processing Letters, Information Sciences, International Journal of Computer Mathematics, New Generation Computing, Publicationes Mathematicae Debrecen, and Theoretical Computer Science. He is the editor-in-chief of the journal Grammars (Kluwer), and the chairman of the 1st International PhD School in Formal Languages and Applications (2001–2003). Victor Mitrana, Ph.D.: He is Professor of Computer Science at the Faculty of Mathematics, University of Bucharest. He received his MSc and PhD from the University of Bucharest in 1986 and 1993, respectively. In 1999 he was awarded with the “Gheorghe Lazar” Prize for Mathematics of the Romanian Academy. His research interests include: formal language theory and applications, combinatorics on words, computational models inspired from biology, mathematical linguistics. In these areas, he published three books, more than 100 papers, and edited two books. He is an associate editor of “The Korean Journal of Computational and Applied Mathematics” and an editor of “Journal of Universal Computer Science”.     

Circuit Complexity of Regular Languages

We survey the current state of knowledge on the circuit complexity of regular languages and we prove that regular languages that are in AC⁰ and ACC⁰ are all computable by almost linear size circuits, extending the result of Chandra et al. (J. Comput. Syst. Sci. 30:222–234, 1985). As a consequence we obtain that in order to separate ACC⁰ from NC¹ it suffices to prove for some ε>0 an Ω(n ^1+ε ) lower bound on the size of ACC⁰ circuits computing certain NC¹-complete functions. Partially supported by grant GA ČR 201/07/P276, project No. 1M0021620808 of MŠMT ČR and Institutional Research Plan No. AV0Z10190503.     

On the computation of quotients and factors of regular languages

Quotients and factors are important notions in the design of various computational procedures for regular languages and for the analysis of their logical properties. We propose a new representation of regular languages, by linear systems of language equations, which is suitable for the following computations: language reversal, left quotients and factors, right quotients and factors, and factor matrices. We present algorithms for the computation of all these notions, and indicate an application of the factor matrix to the computation of solutions of a particular language reconstruction problem. The advantage of these algorithms is that they all operate only on linear systems of language equations, while the design of the same algorithms for other representations often require translation to other representations.     

LARS: A learning algorithm for rewriting systems

Whereas there is a number of methods and algorithms to learn regular languages, moving up the Chomsky hierarchy is proving to be a challenging task. Indeed, several theoretical barriers make the class of context-free languages hard to learn. To tackle these barriers, we choose to change the way we represent these languages. Among the formalisms that allow the definition of classes of languages, the one of string-rewriting systems (SRS) has outstanding properties. We introduce a new type of SRS’s, called Delimited SRS (DSRS), that are expressive enough to define, in a uniform way, a noteworthy and non trivial class of languages that contains all the regular languages, , , the parenthesis languages of Dyck, the language of Lukasiewicz, and many others. Moreover, DSRS’s constitute an efficient (often linear) parsing device for strings, and are thus promising candidates in forthcoming applications of grammatical inference. In this paper, we pioneer the problem of their learnability. We propose a novel and sound algorithm (called LARS) which identifies a large subclass of them in polynomial time (but not data). We illustrate the execution of our algorithm through several examples, discuss the position of the class in the Chomsky hierarchy and finally raise some open questions and research directions. This work was supported in part by the IST Program of the European Community, under the PASCAL Network of Excellence, IST-2002-506778. This publication only reflects the authors’ views. Editor: Georgios Paliouras and Yasubumi Sakakibara     

A characterization of (regular) circular languages generated by monotone complete splicing systems

Circular splicing systems are a formal model of a generative mechanism of circular words, inspired by a recombinant behaviour of circular DNA. Some unanswered questions are related to the computational power of such systems, and finding a characterization of the class of circular languages generated by circular splicing systems is still an open problem. In this paper we solve this problem for monotone complete systems, which are finite circular splicing systems with rules of a simpler form. We show that a circular language L is generated by a monotone complete system if and only if the set Lin(L) of all words corresponding to L is a pure unitary language generated by a set closed under the conjugacy relation. The class of pure unitary languages was introduced by A. Ehrenfeucht, D. Haussler, G. Rozenberg in 1983, as a subclass of the class of context-free languages, together with a characterization of regular pure unitary languages by means of a decidable property. As a direct consequence, we characterize (regular) circular languages generated by monotone complete systems. We can also decide whether the language generated by a monotone complete system is regular. Finally, we point out that monotone complete systems have the same computational power as finite simple systems, an easy type of circular splicing system defined in the literature from the very beginning, when only one rule of a specific type is allowed. From our results on monotone complete systems, it follows that finite simple systems generate a class of languages containing non-regular languages, showing the incorrectness of a longstanding result on simple systems.