We explore the borderline between decidability and undecidability of the following question: “Let C be a class of codes. Given a machine of type X, is it decidable whether the language lies in C or not?” for codes in general, ω-codes, codes of finite and bounded deciphering delay, prefix, suffix and bi(pre)fix codes, and for finite automata equipped with different versions of push-down stores and counters.
In the last decade, formal methods have proved their interest when analyzing security protocols. Security protocols require in particular to reason about the attacker knowledge. Two standard notions are often considered in formal approaches: deducibility and indistinguishability relations. The first notion states whether an attacker can learn the value of a secret, while the latter states whether an attacker can notice some difference between protocol runs with different values of the secret. Several...
In the last decade, formal methods have proved their interest when analyzing security protocols. Security protocols require in particular to reason about the attacker knowledge. Two standard notions are often considered in formal approaches: deducibility and indistinguishability relations. The first notion states whether an attacker can learn the value of a secret, while the latter states whether an attacker can notice some difference between protocol runs with different values of the secret. Several...
The paper investigates the possibility of decomposing vibration signals into deterministic and nondeterministic parts, based on the Wold theorem. A short description of the theory of adaptive filters is presented. When an adaptive filter uses the delayed version of the input signal as the reference signal, it is possible to divide the signal into a deterministic (gear and shaft related) part and a nondeterministic (noise and rolling bearings) part. The idea of the self-adaptive filter (in the literature...
The paper presents one concept of decomposition methods dedicated to PAL-based CPLDs. The proposed approach is an alternative to the classical one, which is based on two-level minimization of separate single-output functions. The key idea of the algorithm is to search for free blocks that could be implemented in PAL-based logic blocks containing a limited number of product terms. In order to better exploit the number of product terms, two-stage decomposition and BDD-based decomposition are to be...
Spectral methods constitute a useful tool in the analysis and synthesis of Boolean functions, especially in cases when other methods reduce to brute-force search procedures. There is renewed interest in the application of spectral methods in this area, which extends also to the closely connected concept of the autocorrelation function, for which spectral methods provide fast calculation algorithms. This paper discusses the problem of spectral decomposition of Boolean functions using the Walsh transform...
The depth hierarchy results for monotone circuits of Raz and McKenzie [5] are extended to the case of monotone circuits of semi-unbounded fan-in. It follows that the inclusions are proper in the monotone setting, for every .
The depth hierarchy results for monotone circuits of Raz and McKenzie [5] are extended to the case of monotone circuits of semi-unbounded fan-in. It follows that the inclusions NCi ⊆ SACi ⊆ ACi are proper in the monotone setting, for every i ≥ 1.
An optimization method of the logic circuit of a Mealy finite-state machine is proposed. It is based on the transformation of object codes. The objects of the Mealy FSM are internal states and sets of microoperations. The main idea is to express the states as some functions of sets of microoperations (internal states) and tags. The application of this method is connected with the use of a special code converter in the logic circuit of an FSM. An example of application is given. The effectiveness...
A method of geometrical characterization of multidimensional data sets, including construction of the convex hull of the data and calculation of the volume of the convex hull, is described. This technique, together with the concept of minimum convex hull volume, can be used for detection of influential points or outliers in multiple linear regression. An approximation to the true concept is achieved by ordering the data into a linear sequence such that the volume of the convex hull of the first...
A movement analysis of objects contained in visual scenes can be performed by means of linear multidimensional filters, which have already been analyzed in the past. While the soundness of the results was convincing, interest in those systems declined due to the limited computational power of contemporary computers. Recent advances in design and implementation of integrated circuits and hardware architectures allow realizing velocity filters if the n-D system is carefully adapted to the analyzed...
Here, we present determinants of some square matrices of field elements. First, the determinat of 2 * 2 matrix is shown. Secondly, the determinants of zero matrix and unit matrix are shown, which are equal to 0 in the field and 1 in the field respectively. Thirdly, the determinant of diagonal matrix is shown, which is a product of all diagonal elements of the matrix. At the end, we prove that the determinant of a matrix is the same as the determinant of its transpose.