Search results for "online"
showing 10 items of 4526 documents
A graph theoretic approach to automata minimality
2012
AbstractThe paper presents a graph-theoretic approach to test the minimality of a deterministic automaton. In particular, we focus on problems concerning the dependence of the minimality of an automaton on the choice of the set F of final states or on the cardinality of the set F. We introduce different minimality conditions of an automaton and show that such conditions can be characterized in graph-theoretic terms.
Nondeterministic Moore Automata and Brzozowski’s Algorithm
2011
Moore automata represent a model that has many applications. In this paper we define a notion of coherent nondeterministic Moore automaton (NMA) and show that such a model has the same computational power of the classical deterministic Moore automaton. We consider also the problem of constructing the minimal deterministic Moore automaton equivalent to a given NMA. In this paper we propose an algorithm that is a variant of Brzozowski's algorithm in the sense that it is essentially structured as reverse operation and subset construction performed twice.
On Extremal Cases of Hopcroft’s Algorithm
2009
In this paper we consider the problem of minimization of deterministic finite automata (DFA) with reference to Hopcroft’s algorithm. Hopcroft’s algorithm has several degrees of freedom, so there can exist different sequences of refinements of the set of the states that lead to the final partition. We find an infinite family of binary automata for which such a process is unique. Some recent papers (cf. [3,7,1]) have been devoted to find families of automata for which Hopcroft’s algorithm has its worst execution time. They are unary automata associated to circular words. However, automata minimization can be achieved also in linear time when the alphabet has only one letter (cf. [14]), so in …
Online Scheduling of Task Graphs on Heterogeneous Platforms
2020
Modern computing platforms commonly include accelerators. We target the problem of scheduling applications modeled as task graphs on hybrid platforms made of two types of resources, such as CPUs and GPUs. We consider that task graphs are uncovered dynamically, and that the scheduler has information only on the available tasks, i.e., tasks whose predecessors have all been completed. Each task can be processed by either a CPU or a GPU, and the corresponding processing times are known. Our study extends a previous $4\sqrt{m/k}$ 4 m / k -competitive online algorithm by Amaris et al. [1] , where $m$ m is the number of CPUs and $k$ k the number of GPUs ( $m\geq k$ m ≥ k ). We prove that no online…
Theory of tailor automata
2019
Abstract In the paper, a fragment of the new theory of tailor automata is presented, within which a deterministic finite automaton was defined. The proposed automaton provides a theoretical model of an informally characterized biomolecular automaton. The idea of working of which is founded on the concept of alternating cut of some double-stranded fragments of DNA, with the use of a restriction enzyme and ligations of some double-stranded fragments of DNA, with the use of the ligase enzyme.
Energy localization in a nonlinear discrete system
1996
International audience; We show that, in the weak amplitude and slow time limits, the discrete equations describing the dynamics of a one-dimensional lattice can be reduced to a modified Ablowitz-Ladik equation. The stability of a continuous wave solution is then investigated without and with periodic boundary conditions; Energy localization via modulational instability is predicted. Our numerical simulations, performed on a cyclic system of six oscillators, agree with our theoretical predictions.
Modulational instability and two-dimensional dynamical structures
2008
A process of nonlinear structure formation on a two-dimensional lattice is proposed. The basic model consists of a two-dimensional lattice equipped at each node with a molecule or dipole rotating in the lattice plane. The interactions involved in the model are reduced to a periodic lattice. Such a discrete system can be applied to the problem of molecule adsorption on a substrate crystal surface, for instance. The continuum approximation of the model leads to a 2-D sine-Gordon system including nonlinear couplings, which itself can be reduced to a 2-D nonlinear Schrodinger equation in the low amplitude limit. Spatio-temporal structure formation is investigated by means of numerical simulatio…
Advanced Ultrasonic Structural Monitoring of Waveguides
2008
Ultrasonic Guided Waves (UGWs) are a useful tool in those structural health monitoring applications that can benefit from built-in transduction, moderately large inspection ranges and high sensitivity to small flaws. This paper describes two methods, based on linear and nonlinear acoustics for structural damage detection based on UGWs. The linear method combine the advantages of UGW inspection with the outcomes of the Discrete Wavelet Transform (DWT) that is used for extracting defect-sensitive features that can be combined to perform a multivariate diagnosis of damage. In particular, the DWT is exploited to generate a set of relevant wavelet coefficients to construct a uni-dimensional or m…
High Order Compact Finite Difference Schemes for A Nonlinear Black-Scholes Equation
2001
A nonlinear Black-Scholes equation which models transaction costs arising in the hedging of portfolios is discretized semi-implicitly using high order compact finite difference schemes. A new compact scheme, generalizing the compact schemes of Rigal [29], is derived and proved to be unconditionally stable and non-oscillatory. The numerical results are compared to standard finite difference schemes. It turns out that the compact schemes have very satisfying stability and non-oscillatory properties and are generally more efficient than the considered classical schemes.
Sample Preparation to Determine Pharmaceutical and Personal Care Products in an All-Water Matrix: Solid Phase Extraction
2020
© 2020 by the authors. Pharmaceuticals and personal care products (PPCPs) are abundantly used by people, and some of them are excreted unaltered or as metabolites through urine, with the sewage being the most important source to their release to the environment. These compounds are in almost all types of water (wastewater, surface water, groundwater, etc.) at concentrations ranging from ng/L to µg/L. The isolation and concentration of the PPCPs from water achieves the appropriate sensitivity. This step is mostly based on solid-phase extraction (SPE) but also includes other approaches (dispersive liquid-liquid microextraction (DLLME), buckypaper, SPE using multicartridges, etc.). In this rev…