Search results for "Theoretical Computer Science"
showing 10 items of 1151 documents
Noise-tolerant efficient inductive synthesis of regular expressions from good examples
1997
We present an almost linear time method of inductive synthesis restoring simple regular expressions from one representative (good) example. In particular, we consider synthesis of expressions of star-height one, where we allow one union operation under each iteration, and synthesis of expressions without union operations from examples that may contain mistakes. In both cases we provide sufficient conditions defining precisely the class of target expressions and the notion of good examples under which the synthesis algorithm works correctly, and present the proof of correctness. In the case of expressions with unions the proof is based on novel results in the combinatorics of words. A genera…
On a class of languages with holonomic generating functions
2017
We define a class of languages (RCM) obtained by considering Regular languages, linear Constraints on the number of occurrences of symbols and Morphisms. The class RCM presents some interesting closure properties, and contains languages with holonomic generating functions. As a matter of fact, RCM is related to one-way 1-reversal bounded k-counter machines and also to Parikh automata on letters. Indeed, RCM is contained in L-NFCM but not in L-DFCM, and strictly includes L-CPA. We conjecture that L-DFCM subset of RCM
Filtering design for two-dimensional Markovian jump systems with state-delays and deficient mode information
2014
This paper is concerned with the problem of H"~ filtering for a class of two-dimensional Markovian jump linear systems described by the Fornasini-Marchesini local state-space model. The systems under consideration are subject to state-delays and deficient mode information in the Markov chain. The description of deficient mode information is comprehensive that simultaneously includes the exactly known, partially unknown and uncertain transition probabilities. By invoking the properties of the transition probability matrix, together with the convexification of uncertain domains, a new H"~ performance analysis criterion for the filtering error system is firstly derived. Then, via some matrix i…
Impact of chaotic dynamics on the performance of metaheuristic optimization algorithms : An experimental analysis
2022
Random mechanisms including mutations are an internal part of evolutionary algorithms, which are based on the fundamental ideas of Darwin's theory of evolution as well as Mendel's theory of genetic heritage. In this paper, we debate whether pseudo-random processes are needed for evolutionary algorithms or whether deterministic chaos, which is not a random process, can be suitably used instead. Specifically, we compare the performance of 10 evolutionary algorithms driven by chaotic dynamics and pseudo-random number generators using chaotic processes as a comparative study. In this study, the logistic equation is employed for generating periodical sequences of different lengths, which are use…
On the Calmness of a Class of Multifunctions
2002
The paper deals with the calmness of a class of multifunctions in finite dimensions. Its first part is devoted to various conditions for calmness, which are derived in terms of coderivatives and subdifferentials. The second part demonstrates the importance of calmness in several areas of nonsmooth analysis. In particular, we focus on nonsmooth calculus and solution stability in mathematical programming and in equilibrium problems. The derived conditions find a number of applications there.
On Horn spectra
1991
Abstract A Horn spectrum is a spectrum of a Horn sentence. We show that to solve Asser's problem, and consequently the EXPTIME = ? NEXPTIME question it suffices to consider the class of Horn spectra. We also pose the problem whether or not the generator of every Horn spectrum is a spectrum. We prove that from a negative solution of the generator problem, a negative answer for the EXPTIME = ? NEXPTIME question follows. Some other relations between the generator problem and Asser's problem are given. Finally, the relativized version of the generator problem is formulated and it is shown that it has an affirmative solution for some oracles, and a negative solution for some others.
Learning Molecular Classes from Small Numbers of Positive Examples Using Graph Grammars
2021
We consider the following problem: A researcher identified a small number of molecules with a certain property of interest and now wants to find further molecules sharing this property in a database. This can be described as learning molecular classes from small numbers of positive examples. In this work, we propose a method that is based on learning a graph grammar for the molecular class. We consider the type of graph grammars proposed by Althaus et al. [2], as it can be easily interpreted and allows relatively efficient queries. We identify rules that are frequently encountered in the positive examples and use these to construct a graph grammar. We then classify a molecule as being conta…
The identity type weak factorisation system
2008
We show that the classifying category C(T) of a dependent type theory T with axioms for identity types admits a non-trivial weak factorisation system. We provide an explicit characterisation of the elements of both the left class and the right class of the weak factorisation system. This characterisation is applied to relate identity types and the homotopy theory of groupoids.
Pattern classification using a new border identification paradigm: The nearest border technique
2015
Abstract There are many paradigms for pattern classification such as the optimal Bayesian, kernel-based methods, inter-class border identification schemes, nearest neighbor methods, nearest centroid methods, among others. As opposed to these, this paper pioneers a new paradigm, which we shall refer to as the nearest border (NB) paradigm. The philosophy for developing such a NB strategy is as follows: given the training data set for each class, we shall attempt to create borders for each individual class. However, unlike the traditional border identification (BI) methods, we do not undertake this by using inter-class criteria; rather, we attempt to obtain the border for a specific class in t…
Efficient learning of regular expressions from good examples
1994
We consider the problem of restoring regular expressions from expressive examples. We define the class of unambiguous regular expressions, the notion of the union number of an expression showing how many union operations can occur directly under any single iteration, and the notion of an expressive example. We present a polynomial time algorithm which tries to restore an unambiguous regular expression from one expressive example. We prove that if the union number of the expression is 0 or 1 and the example is long enough, then the algorithm correctly restores the original expression from one good example. The proof relies on original investigations in theory of covering symbol sequences (wo…