Decomposition theorems for finite sequential machines

In this work we present a different proof of results by K.B. Krohn and J. L. Rhodes [1], and give a new result on the same lines. These authors proved that every function computed by a finite state machine can be constructed by “elementary operations” on a set of “prime functions.” By extending the scope of elementary operations, we now show that all functions computed by finite machines are built from a single function. This work is based on a M.Sc. Thesis prepared at the Hebrew University of Jerusalem under the supervision of Professor M. Rabin. The author is deeply indebted to Professor M. Rabin for his interest and help in this work, and to Professor E. Shamir for his help in preparing this work for publication. Partially supported by ONR Information Systems Branch Contract No. F 61052-67-0055.     

基于模糊乘积有限自动机的覆盖关系

对Mealy-型模糊有限自动机乘积结构作了进一步的研究,并且对覆盖关系作了细致的刻画,推广了原有的覆盖概念.针对Mealy-型这类模糊有限自动机,通过性质考察了此覆盖概念的合理有效性,新的覆盖概念在乘积自动机间建立了更多的联系.特别证明了直积、级联积、圈积三种乘积之间的覆盖关系.得到了一些乘积自动机覆盖关系的传递性质.     

On the optimality of algorithms for finite state sequential decision processes

A finite state sequential decision process (sdp) is a model which is able to represent a wide variety of combinatorial optimization problems. Four known and two new algorithms for obtaining optimal policies of three subclasses of sdp's, r-lmsdp, r-pmsdp, and r-psmsdp, are considered, and their optimality in the sense of minimizing the number of evaluations of cost functions associated with state transitions is proved.     

Intuitionistic fuzzy finite state machines

Using the notion of intuitionistic fuzzy sets, the concepts of intuitionistic fuzzy finite state machines (iffsm), intuitionistic successor s, intuitionistic subsystems, intuitionistic submachines, intuitionisticq-twins, and intuitionistic retrievable iffsm are introduce d, and related properties are studied. Relations between intuitionisticq-twins and intuitionisticq-related iffsm are given. A characterization of an intuitionistic retrievable iffsm is provided.     

模糊有限自动机的kronecker积

在矩阵理论框架下,引入了模糊有限自动机转移矩阵,变换矩阵半群以及覆盖概念.定义了模糊有限自动机Kronecker积,讨论了其转移矩阵性质及变换矩阵半群间的覆盖关系.     

A similarity transform for linear finite state machines

A practical algorithm in terms of ease of implementation and speed is presented to find a similarity transform between any two similar linear finite state machines (LFSMs). The transform is based on the external-XOR LFSR companion matrix instead of the more usual internal-XOR LFSR companion matrix. The complexity of the algorithm amounts to that of inverting an n×n matrix, where n is the LFSM size.     

幺半环上模糊有限状态机的一些性质

状态机的很多性质在计算机等方面有着广泛的应用,因此对状态机的研究具有重要的意义.本文给出了幺半环上模糊有限状态机的概念,对状态之间的等价进行了定义,引入了同态的概念,得到同态定理和满同态分解定理,讨论了幺半环上模糊有限状态机在同态下的交换性质和连通性以及子状态机的可分离性.     

Asymptotic sequential Rademacher complexity of a finite function class

For a finite function class, we describe the large sample limit of the sequential Rademacher complexity in terms of the viscosity solution of a G-heat equation. In the language of Peng’s sublinear expectation theory, the same quantity equals to the expected value of the largest order statistics of a multidimensional G-normal random variable. We illustrate this result by deriving upper and lower bounds for the asymptotic sequential Rademacher complexity.     

Weak sequential completeness in Banach $$$$-modules of finite multiplicity

A well known result of Lozanovsky states that a Banach lattice is weakly sequentially complete if and only if it does not contain a copy of \(c_{0}\). In the current paper we extend this result to the class of Banach \(C(K)\)-modules of finite multiplicity and, as a special case, to finitely generated Banach \(C(K)\)-modules. Moreover, we prove that such a module is weakly sequentially complete if and only if each cyclic subspace of the module is weakly sequentially complete.     

On the finite axiomatizability of

The question of whether the bounded arithmetic theories and are equal is closely connected to the complexity question of whether is equal to . In this paper, we examine the still open question of whether the prenex version of , , is equal to . We give new dependent choice‐based axiomatizations of the ‐consequences of and . Our dependent choice axiomatizations give new normal forms for the ‐consequences of and . We use these axiomatizations to give an alternative proof of the finite axiomatizability of and to show new results such as is finitely axiomatized and that there is a finitely axiomatized theory, , containing and contained in . On the other hand, we show that our theory for splits into a natural infinite hierarchy of theories. We give a diagonalization result that stems from our attempts to separate the hierarchy for .     

Model matching of input/state switched asynchronous sequential machines with the external switching signal

This article investigates the input/state model matching problem of switched asynchronous sequential machines (ASMs) with the external switching signal in the framework of corrective control theory. The considered switched ASM is governed by the external switching signal that arbitrarily changes the mode of the switched ASM, prompting the active submachine into unpredictable state drift. We address the existence condition and design procedure for a proper corrective controller that matches the stable-state behavior of the closed-loop system to that of a reference model under any switching sequence. An illustrative example is provided for demonstrating the synthesis procedure of the proposed corrective controller. Compared with the prior work, the subject of this study is more challenging since rather than manipulated in favor of attaining model matching, the switching signal inflicts adversarial dynamic constraint that must be overcome by the controller.     

On the convergence of sequential minimization algorithms

This note discusses the conditions for convergence of algorithms for finding the minimum of a function of several variables which are based on solving a sequence of one-variable minimization problems. Theorems are given which contrast the weakest conditions for convergence of gradient-related algorithms with those for more general algorithms, including those which minimize in turn along a sequence of uniformly linearly independent search directions.The senior author benefited greatly from discussion of this problem with various participants at the NATO Summer School on Mathematical Programming in Theory and Practice held at Figueira da Foz, Portugal, June 1972, and in particular with M. J. D. Powell, who, in continuing correspondence, has produced a series of examples and counterexamples for various versions of the theorems.     

On sequential estimation of the shift parameter

The problem is considered of estimating the minimal sample size that guarantees the required accuracy, with confidence level fixed, of the estimate of the expectation. Translated fromStatisticheskie Metody Otsenivaniya i Proverki Gipotez, pp. 32–36, Perm, 1991.     

On the convergence of sequential minimization algorithms

This note gives a proof of convergence of a class of gradient-related minimization algorithms under slightly weaker conditions than were used in a recent paper (see Ref. 1) on the same subject.     

Performance analysis of assembly systems with unreliable machines and finite buffers

An unreliable assembly system is studied in which different types of components are processed by two separate work centers before merging to an assembly station with random breakdown. Blocking at the work centers and starvation at the assembly station may occur because of finite buffer sizes and uncertainties in job arriving times and processing/assembly times. We derive the system stability condition, and obtain formulas for the system state probabilities, blocking probabilities, starvation probability, stockout probability, system availability in the steady state. We also obtain the distributions of blocking times and first failure times, respectively. Through numerical examples, we elaborate on the monotonous properties of the performance measures, and draw the insights into the impacts of the system parameters on its various performance indices, which provide important guidance for design of assembly systems.     

On sequential density estimation

We consider the problem of sequential estimation of a density function f at a point x ₀ which may be known or unknown. Let T _n be a sequence of estimators of x ₀ . For two classes of density estimators f _n , namely the kernel estimates and a recursive modification of these, we show that if N(d) is a sequence of integer-valued random variables and n(d) a sequence of constants with N(d)/n(d) 1 in probability as d 0, then f _N(d) (T _N(d) -f(x ₀) is asymptotically normally distributed (when properly normed). We also propose two new classes of stopping rules based on the ideas of fixed-width interval estimation and show that for these rules, N(d)/n(d) 1 almost surely and EN(d)/n(d) 1 as d 0. One of the stopping rules is itself asymptotically normally distributed when properly normed and yields a confidence interval for f(x ₀) of fixed-width and prescribed coverage probability.     

Approximate reasoning and finite state machines to the detection of actions in video sequences

In this paper a novel approach for recognizing actions in video sequences is presented, where the information obtained from the segmentation and tracking algorithms is used as input data. First of all, the fuzzification of input data is done and this process allows to successfully manage the uncertainty inherent to the information obtained from low-level and medium-level vision tasks, to unify the information obtained from different vision algorithms into a homogeneous representation and to aggregate the characteristics of the analyzed scenario and the objects in motion. Another contribution is the novelty of representing actions by means of an automaton and the generation of input symbols for the finite automaton depending on the comparison process between objects and actions, i.e., the main reasoning process is based on the operation of automata with capability to manage fuzzy representations of all video data. The experiments on several real traffic video sequences demonstrate encouraging results, especially when no training algorithms to obtain predefined actions to be identified are required.