A Büchi-Like Theorem for Weighted Tree Automata over Multioperator Monoids

A multioperator monoid A\mathcal{A} is a commutative monoid with additional operations on its carrier set. A weighted tree automaton over A\mathcal{A} is a finite state tree automaton of which each transition is equipped with an operation of A\mathcal{A}. We define M-expressions over A\mathcal{A} in the spirit of formulas of weighted monadic second-order logics and, as our main result, we prove that if A\mathcal{A} is absorptive, then the class of tree series recognizable by weighted tree automata over A\mathcal{A} coincides with the class of tree series definable by M-expressions over A\mathcal{A}. This result implies the known fact that for the series over semirings recognizability by weighted tree automata is equivalent with definability in syntactically restricted weighted monadic second-order logic. We prove this implication by providing two purely syntactical transformations, from M-expressions into formulas of syntactically restricted weighted monadic second-order logic, and vice versa.     

ROUGH FINITE-STATE AUTOMATA

The concept of a rough finite-state semi-automaton, in which the result of any transition is a rough set of states, is formulated and then extended to that of a rough finite-state automaton by adding the set of accepting states. The behavior of such an automaton is defined and turns out to be a rough set of input words.     

An automaton decomposition for learning system environments

A finite automaton two-component cascade decomposition is presented in which the first component has a synchronizer and the second component is a permutation automaton. The synchronizer corresponds to a primitive idempotent element e in the transition monoid M of the automaton. The state set of the second component is the range of e; each state of the first component is an image of this range under one of the transitions in M. The transition monoid of the second component is the group eMe. as a conceptual tool, the decomposition can be used to clarify the credit assignment problems faced by learning system reward schemes in finite automaton environments.     

Trace monoids with idempotent generators and measure-only quantum automata

In this paper, we analyze a model of 1-way quantum automaton where only measurements are allowed ( MON -1qfa). The automaton works on a compatibility alphabet (S, E)(\Sigma, E) of observables and its probabilistic behavior is a formal series on the free partially commutative monoid FI(S, E)\hbox{FI}(\Sigma, E) with idempotent generators. We prove some properties of this class of formal series and we apply the results to analyze the class LMO(S, E){\bf LMO}(\Sigma, E) of languages recognized by MON -1qfa’s with isolated cut point. In particular, we prove that LMO(S, E){\bf LMO}(\Sigma, E) is a boolean algebra of recognizable languages with finite variation, and that LMO(S, E){\bf LMO}(\Sigma, E) is properly contained in the recognizable languages, with the exception of the trivial case of complete commutativity.     

Distance automata having large finite distance or finite ambiguity

A distance automaton is a (nondeterministic finite) automaton which is equipped with a nonnegative cost function on its transitions. The distance of a word recognized by such a machine quantifies the expenses associated with the recognition of this word. The distance of a distance automaton is the maximal distance of a word recognized by this machine or is infinite, depending on whether or not a maximum exists. We present distance automata havingn states and distance 2 ⁿ – 2. As a by-product we obtain regular languages having exponential finite order. Given a finitely ambiguous distance automaton withn states, we show that either its distance is at most 3 ⁿ – 1, or the growth of the distance in this machine is linear in the input length. The infinite distance problem for these distance automata is NP-hard and solvable in polynomial space. The infinite-order problem for regular languages is PSPACE-complete.A preliminary version of this article appeared in theProceedings of the 15th Symposium on Mathematical Foundations of Computer Science, 1990.     

Computing Accumulated Delays in Real-time Systems

We present a verification algorithm for duration properties of real-time systems. While simple real-time properties constrain the total elapsed time between events, duration properties constrain the accumulated satisfaction time of state predicates. We formalize the concept of durations by introducing duration measures for timed automata. A duration measure assigns to each finite run of a timed automaton a real number —the duration of the run— which may be the accumulated satisfaction time of a state predicate along the run. Given a timed automaton with a duration measure, an initial and a final state, and an arithmetic constraint, the duration-bounded reachability problem asks if there is a run of the automaton from the initial state to the final state such that the duration of the run satisfies the constraint. Our main result is an (optimal) PSPACE decision procedure for the duration-bounded reachability problem.     

Temporal determinization of mutating finite automata: Reconstructing or restructuring

A mutating finite automaton (MFA) is a nondeterministic finite automaton (NFA) that changes its morphology over discrete time by a sequence of mutations. This results in a sequence of NFAs, the initial NFA, and one mutated NFA for each mutation. Some application domains, including model-based diagnosis of discrete-event systems in artificial intelligence and model-based testing in software engineering, require temporal determinization of MFAs. Determinizing an MFA temporally means generating a deterministic finite automaton (DFA) that is equivalent to the mutated NFA as soon as a mutation occurs. Since, in computation time, the classical Subset Construction determinization algorithm may be less than optimal when applied to MFAs, a conservative algorithm is proposed, called Subset Restructuring, which, instead of constructing the new DFA from scratch based on the mutated NFA, generates the new DFA by updating the previous DFA based on the mutation occurred. Subset Restructuring is sound and complete, thereby yielding the same DFA generated by Subset Construction. Results from massive experimentation indicate the viability of Subset Restructuring, especially so when large MFAs change by small mutations.     

Analysis for an Effective Operation of a General Automaton: Recursive Methods Applied to a Graph Model

Abstract

With many there is a general agreement that the problems arising from large and complex systems in society are interdisciplinary in nature and that pending solutions require contributions from all concerned who are willing to view the problems in full perspective. There is a need for the development of a general theory which can serve as a basis for establishing theoretical concepts fundamental to the various disciplines. Such a theory could then be used directly in the modeling and studying of a specific physical system or system component.

In [1], we first identified a component of general system and treated it as a general automaton. That work concluded with a graph model for a general automaton. The natural extension presented here is the development and application of recursive methods for determining properties of these graphs that reflect the effective operation of the general automaton. The recursive methods provide a means of studying a component of such a system by a computer.

The key result from applying the recursive methods is an effective operation function for each graph in the model in the form of a sequence describing a unique path in each graph. This path describes the effective operation of the automaton with respect to the type of graph.     

On conditional optimality of a class of learning automata in random environments

In this paper, we develop a new class of learning automata to operate in a random environment with a finite number of responses, called a Q-model, and investigate its asymptotic behavior from the viewpoint of conditional optimality. It is shown that this class contains as a particular case the β-model automaton introduced by Luce, which is available for an environment with binary responses, called a P-model. Making use of the martingale convergence theorem for the asymptotic analysis of the automata, we show that the automata are conditionally optimal, i.e., the automata converge optimally under the restrictions on the probability distributions that characterize the environment. The usefulness of the result is illustrated by its application to two simple automata: the β-model automaton and another one which is also applied to a P-model environment. Then, extending the idea underlying the second automaton, we develop a design method for an effective and structurally simple automaton for any Q-model environment. The conditional optimality of the resulting automaton is also investigated.     

Marker versus inkdot over three-dimensional patterns

A multi-marker automaton is a finite automaton which keeps marks as pebbles in the finite control, and cannot rewrite any input symbols but can make marks on its input with the restriction that only a bounded number of these marks can exist at any given time. An improvement of picture recognizability of the finite automaton is the reason why the multi-marker automaton was introduced. On the other hand, a multi-inkdot automaton is a conventional automaton capable of dropping an inkdot on a given input tape for a landmark, but unable to further pick it up. This paper deals with marker versus inkdot over threedimensional input tapes, and investigates some properties. This work was presented in part at the 13th International Symposium on Artificial Life and Robotics, Oita, Japan, January 31–February 2, 2008     

THE LOGIC OF AUTOMATA

Automata are the prime example of general systems over discrete spaces, and yet the theory of automata is fragmentary and it is not clear what makes a general structure an automaton. This paper investigates the logical foundations of automata relating it to the semantics of our notions of uncertainty, state and state-determined. A single framework is established for the conventional spectrum of automata: deterministic, probabilistic, fuzzy, and non-deterministic, which shows this set to be, in some sense, complete. Counter-examples are then developed to show that this spectrum alone is inadequate to describe the behaviour of certain forms of uncertain system. Finally a general formulation is developed based on the fundamental semantics of our notion of a state that shows that the logical Structure of an automaton must be at least a positive ordered semiring. The role of probability logic, its relationship to fuzzy logic, the rotes of topological models of automata, and the symmetry between inputs and outputs in hyperstate/hyperinput-determinedsystems are also discussed.     

THE LOGIC OF AUTOMATA

Automata are the prime example of general systems over discrete spaces, and yet the theory of automata is fragmentary and it is not clear what makes a general structure an automaton. This paper investigates the logical foundations of automata relating it to the semantics of our notions of uncertainty, state and state-determined. A single framework is established for the conventional spectrum of automata: deterministic, probabilistic, fuzzy, and non-deterministic, which shows this set to be, in some sense, complete. Counter-examples are then developed to show that this spectrum alone is inadequate to describe the behaviour of certain forms of uncertain system. Finally a general formulation is developed based on the fundamental semantics of our notion of a state that shows that the logical structure of an automaton must be at least a positive ordered semiring. The role of probability logic, its relationship to fuzzy logic, the roles of topological models of automata, and the symmetry between inputs and outputs in hyperstate/hyperinput-determined systems are also discussed.     

Spigot Algorithm and Root Computing

The word spigot indicates that the "digits" (generally in a widened meaning) of the result number are extracted successively from left to right (as if pumped through a spigot) by using only integer arithmetic, as opposed to the iterative approach, where the result number as the whole is improved after each iteration step by using (high-precision) floating-point arithmetic. The approach of spigot computing as used in papers by S. Kamal Abdaly (Comm. ACM 13(1970)), S. Rabinowitz and S. Wagon (American Mathematical Monthly 102(3) (1995)), A. H. J. Sale (Comput. J. 11(1968)) is now systematized and correctness is formally proved; the way for achieving an arbitrary accuracy is shown.Then a method for computing roots of arbitrary rational numbers is developed. If a root is not rational, spigot approach is used to compute its decimal approximation with an arbitrary given accuracy; if the root is rational, its numerator and denominator are computed exactly. This method for root computing is absolutely reliable: it is both formally proved and tested by numerical examples.     

Faster Approximate String Matching

We present a new algorithm for on-line approximate string matching. The algorithm is based on the simulation of a nondeterministic finite automaton built from the pattern and using the text as input. This simulation uses bit operations on a RAM machine with word length w = Ω (log n) bits, where n is the text size. This is essentially similar to the model used in Wu and Manber's work, although we improve the search time by packing the automaton states differently. The running time achieved is O(n) for small patterns (i.e., whenever mk = O(log n)) , where m is the pattern length and k<m is the number of allowed errors. This is in contrast with the result of Wu and Manber, which is O(kn) for m=O(log n) . Longer patterns can be processed by partitioning the automaton into many machine words, at O(mk/w n) search cost. We allow generalizations in the pattern, such as classes of characters, gaps, and others, at essentially the same search cost. We then explore other novel techniques to cope with longer patterns. We show how to partition the pattern into short subpatterns which can be searched with less errors using the simple automaton, to obtain an average cost close to . Moreover, we allow the superimposition of many subpatterns in a single automaton, obtaining near average complexity (σ is the alphabet size). We perform a complete analysis of all the techniques and show how to combine them in an optimal form, also obtaining new tighter bounds for the probability of an approximate occurrence in random text. Finally, we show experimental results comparing our algorithms against previous work. These experiments show that our algorithms are among the fastest for typical text searching, being the fastest in some cases. Although we aim mainly at text searching, we believe that our ideas can be successfully applied to other areas such as computational biology. Received November 22, 1996; revised October 13 and December 5, 1997.     

Automaton recognition of doubly connected labyrinths with finite cyclic diameter

The problem of existence of a recognizing automaton for a subclass of an infinite class of chess labyrinths (denoted as C ₀) is studied. It is proved in [1] that, for C ₀, there does not exist a recognizing automaton. In [2], it is proved that there exists a recognizing collective of type (1, 1) (collective consisting of an automaton and stone). In this paper, it is proved that there exists a recognizing automaton for some subclass of the class of chess labyrinths with finite cyclic diameter.     

Fuzzy Sets and Neural Networks

Abstract

It is possible that a better model for the behavior of a nerve cell may be provided by what might be called a fuzzy neuron, which is a generalization of the McCulloch-Pitts model. The concept of a fuzzy neuron employs some of the concepts and techniques of the theory of fuzzy sets which was introduced by Zadeh [2, 3] and applied to the theory of automaton by Wee and Fu [6], Tanaka et al. [7], Santo [8] and others. In effect, the introduction of fuzziness into the model of a neuron makes it better adapted to the study of the behavior of systems which are imprecisely defined by virtue of their high degree of complexity. Many of the biological systems, economic systems, urban systems and more generally, large-scale systems fall into this category.

In the nearly three decades since its publication, the pioneering work of McCulloch and Pitts [1], has had a profound influence on the development of the theory of neural nets, in addition to stimulating much of the early work in automata theory and regular events.

Although the McCulloch-Pitts model of a neuron has contributed a great deal to the understanding of the behavior of neural-like systems, it fails to reflect the fact that the behavior of even the simplest type of nerve cell exhibits not only randomness but, more importantly, a type of imprecision which is associated with the lack of sharp transition from the occurrence of an event to its non-occurrence.

In this paper, some basic properties of fuzzy neural networks as well as their applications to the synthesis of fuzzy automata are investigated. It is shown that any n-state minimal fuzzy automaton can be realized by a network of m fuzzy neurons, where ┌log₂ n┐ ? m ? 2n. Examples are given to illustrate the procedure. As an example of application, a realization of λ-fuzzy language recognizer using a fuzzy neural network is presented. The techniques described in this paper may be of use in the study of neural networks as well as in formal languages, pattern recognition, and learning.     

Simultaneously One-Turn Two-Pushdown Automata

Consider two consecutive moves, $m_{1}$ and $m_{2}$ , made by a two-pushdown automaton, M , whose pushdowns are denoted by $\pi_{1}$ and $\pi_{2}$ . If during $m_{1}$ M does not shorten $\pi_{i}$ , for some $i = 1, 2$ , while during $m_{2}$ it shortens $\pi_{i}$ , then M makes a turn in $\pi_{i}$ during $m_{2}$ . If M makes a turn in both $\pi_{1}$ and $\pi_{2}$ during $m_{2}$ , this turn is simultaneous . A two-pushdown automaton is one-turn if it makes no more than one turn in either of its pushdowns during any computation. A two-pushdown automaton is simultaneously one-turn if it makes either no turn or one simultaneous turn in its pushdowns during any computation. This paper demonstrates that every recursively enumerable language is accepted by a simultaneously one-turn two-pushdown automaton. Consequently, every recursively enumerable language is accepted by a one-turn two-pushdown automaton.     

Reformulation of Global Constraints Based on Constraints Checkers

This article deals with global constraints for which the set of solutions can be recognized by an extended finite automaton whose size is bounded by a polynomial in n, where n is the number of variables of the corresponding global constraint. By reducing the automaton to a conjunction of signature and transition constraints we show how to systematically obtain an automaton reformulation. Under some restrictions on the signature and transition constraints, this reformulation maintains arc-consistency. An implementation based on some constraints as well as on the metaprogramming facilities of SICStus Prolog is available. For a restricted class of automata we provide an automaton reformulation for the relaxed case, where the violation cost is the minimum number of variables to unassign in order to get back to a solution.     

The Garden of Eden theorem for cellular automata on group sets

ABSTRACT

We prove the Garden of Eden theorem for big-cellular automata with finite set of states and finite neighbourhood on right amenable left homogeneous spaces with finite stabilisers. It states that the global transition function of such an automaton is surjective if and only if it is pre-injective. Pre-Injectivity means that two global configurations that differ at most on a finite subset and have the same image under the global transition function must be identical. The theorem is proven by showing that the global transition function of an automaton as above is surjective if and only if its image has maximal entropy and that its image has maximal entropy if and only if it is pre-injective. Entropy of a subset of global configurations measures the asymptotic growth rate of the number of finite patterns with growing domains that occur in the subset.