Search results for "Regular"
showing 10 items of 855 documents
Efficient algorithm for learning simple regular expressions from noisy examples
1994
We present an efficient algorithm for finding approximate repetitions in a given sequence of characters. First, we define a class of simple regular expressions which are of star-height one and do not contain union operations, and a stochastic mutation process of a given length over a string of characters. Then, assuming that a given string of characters is obtained corrupted by the defined mutation process from some long enough word generated by a simple regular expression, we try to restore the expression. We prove that to within some reasonable accuracy it is always possible if the length of the mutation process is bounded comparing to the length of the example. We provide an algorithm by…
Compound conditionals, Fr\'echet-Hoeffding bounds, and Frank t-norms
2021
Abstract In this paper we consider compound conditionals, Frechet-Hoeffding bounds and the probabilistic interpretation of Frank t-norms. By studying the solvability of suitable linear systems, we show under logical independence the sharpness of the Frechet-Hoeffding bounds for the prevision of conjunctions and disjunctions of n conditional events. In addition, we illustrate some details in the case of three conditional events. We study the set of all coherent prevision assessments on a family containing n conditional events and their conjunction, by verifying that it is convex. We discuss the case where the prevision of conjunctions is assessed by Lukasiewicz t-norms and we give explicit s…
Countably compact weakly Whyburn spaces
2015
The weak Whyburn property is a generalization of the classical sequential property that was studied by many authors. A space X is weakly Whyburn if for every non-closed set \({A \subset X}\) there is a subset \({B \subset A}\) such that \({\overline{B} \setminus A}\) is a singleton. We prove that every countably compact Urysohn space of cardinality smaller than the continuum is weakly Whyburn and show that, consistently, the Urysohn assumption is essential. We also give conditions for a (countably compact) weakly Whyburn space to be pseudoradial and construct a countably compact weakly Whyburn non-pseudoradial regular space, which solves a question asked by Angelo Bella in private communica…
Polynomial Smoothing Splines
2014
Interpolating splines is a perfect tool for approximation of a continuous-time signal \(f(t)\) in the case when samples \(x[k]=f(k),\;k\in \mathbb {Z}\) are available. However, frequently, the samples are corrupted by random noise. In such case, the so-called smoothing splines provide better approximation. In this chapter we describe periodic smoothing splines in one and two dimensions. The SHA technique provides explicit expression of such splines and enables us to derive optimal values of the regularization parameters.
The Star Height One Problem for Irreducible Automata
1993
The star height of a regular expression is, informally, the maximum number of nested stars in the expression. The star height of a regular language is the minimal star height of a regular expression denoting this language. The notion of star height indicates in a certain sense the “loop complexity” of a regular expression and thus it gives a measure of the complexity of a regular language.
A dual of 4-regular graph forG × C2n
2003
Abstract A graph is said h-decomposable if its edge-set is decomposable into edge-disjoint hamiltonian cycles. Jha [3] conjectured that if G is a non-bipartite h-decomposable graph on even number of vertices, then G × K2 is h-decomposable. We use the notion of dual graph defined in [4], we prove that if G = Q1,2 ⊕ C3,4 is a 4-regular non-bipartite h-decomposable graph and the dual graphs relative to Q1,2 and C3,4 are connected then G × K 2 and G × C 2n are h-decomposable (where C 2n is an even cycle).
Probabilities to Accept Languages by Quantum Finite Automata
1999
We construct a hierarchy of regular languages such that the current language in the hierarchy can be accepted by 1-way quantum finite automata with a probability smaller than the corresponding probability for the preceding language in the hierarchy. These probabilities converge to 1/2.
Graph Connectivity, Monadic NP and built-in relations of moderate degree
1995
It has been conjectured [FSV93] that an existential secondoder formula, in which the second-order quantification is restricted to unary relations (i.e. a Monadic NP formula), cannot express Graph Connectivity even in the presence of arbitrary built-in relations.
Sharpness of Rickman’s Picard theorem in all dimensions
2015
We show that given \({n \geqslant 3}\), \({q \geqslant 1}\), and a finite set \({\{y_1, \ldots, y_q \}}\) in \({\mathbb{R}^n}\) there exists a quasiregular mapping \({\mathbb{R}^n\to \mathbb{R}^n}\) omitting exactly points \({y_1, \ldots, y_q}\).
Optimal Control Under Fuzzy Conditions for Dynamical Systems Associated with the Second Order Linear Differential Equations
2020
This paper is devoted to an optimal trajectory planning problem with uncertainty in location conditions considered as a problem of constrained optimal control for dynamical systems. Fuzzy numbers are used to incorporate uncertainty of constraints into the classical setting of the problem under consideration. The proposed approach applied to dynamical systems associated with the second order linear differential equations allows to find an optimal control law at each \(\alpha \)-level using spline-based methods developed in the framework of the theory of splines in convex sets. The solution technique is illustrated by numerical examples.