Linear cellular automata and Fischer automata

We study the sizes of minimal finite state machines associated with linear cellular automata. In particular, we construct a class of binary linear cellular automata whose corresponding minimal automata exhibit full exponential blow-up. These cellular automata have Hamming distance 1 to a permutation automaton. Moreover, the corresponding minimal Fischer automata as well as the minimal DFAs have maximal complexity. By contrast, the complexity of higher iterates of a cellular automaton always stays below the theoretical upper bound.     

Sofic Tree-Shifts

We introduce the notion of sofic tree-shifts which corresponds to symbolic dynamical systems of infinite ranked trees accepted by finite tree automata. We show that, contrary to shifts of infinite sequences, there is no unique reduced deterministic irreducible tree automaton accepting an irreducible sofic tree-shift, but that there is a unique synchronized one, called the Fischer automaton of the tree-shift. We define the notion of almost of finite type tree-shift which are sofic tree-shifts accepted by a tree automaton which is both deterministic and co-deterministic with a finite delay. It is a meaningful intermediate dynamical class in between irreducible finite type tree-shifts and irreducible sofic tree-shifts. We characterize the Fischer automaton of an almost of finite type tree-shift and we design an algorithm to check whether a sofic tree-shift is almost of finite type. We prove that the Fischer automaton is a topological conjugacy invariant of the underlying irreducible sofic tree-shift.     

Security policies enforcement using finite and pushdown edit automata

Edit automata have been introduced by J.Ligatti et al. as a model for security enforcement mechanisms which work at run time. In a distributed interacting system, they play a role of a monitor that runs in parallel with a target program and transforms its execution sequence into a sequence that obeys the security property. In this paper, we characterize security properties which are enforceable by finite edit automata (i.e. edit automata with a finite set of states) and deterministic context-free edit automata (i.e. finite edit automata extended with a stack). We prove that the properties enforceable by finite edit automata are a sub-class of regular sets. Moreover, given a regular set $P$ , one can decide in time $O(n^2)$ , whether $P$ is enforceable by a finite edit automaton (where $n$ is the number of states of the finite automaton recognizing $P$ ) and we give an algorithm to synthesize the controller. Moreover, we prove that safety policies are always enforced by a deterministic context-free edit automaton. We also prove that it is possible to check if a policy is a safety policy in $O(n^4)$ . Finally, we give a topological condition on the deterministic automaton expressing a regular policy enforceable by a deterministic context-free edit automaton.     

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.     

Decision problems for lower/upper bound parametric timed automata

We investigate a class of parametric timed automata, called lower bound/upper bound (L/U) automata, where each parameter occurs in the timing constraints either as a lower bound or as an upper bound. For such automata, we show that basic decision problems, such as emptiness, finiteness and universality of the set of parameter valuations for which there is a corresponding infinite accepting run of the automaton, is Pspace-complete. We extend these results by allowing the specification of constraints on parameters as a linear system. We show that the considered decision problems are still Pspace-complete, if the lower bound parameters are not compared with the upper bound parameters in the linear system, and are undecidable in general. Finally, we consider a parametric extension of MITL\mathsf{MITL} _0,∞, and prove that the related satisfiability and model checking (w.r.t. L/U automata) problems are Pspace-complete.     

Synchronizing automata with finitely many minimal synchronizing words

A synchronizing word for a given synchronizing DFA is called minimal if none of its proper factors is synchronizing. We characterize the class of synchronizing automata having only finitely many minimal synchronizing words (the class of such automata is denoted by FG). Using this characterization we prove that any such automaton possesses a synchronizing word of length at most 3n-5. We also prove that checking whether a given DFA A is in FG is co-NP-hard and provide an algorithm for this problem which is exponential in the number of states A.     

On computing the entropy of cellular automata

We study the topological entropy of a particular class of dynamical systems: cellular automata. The topological entropy of a dynamical system (X,F) is a measure of the complexity of the dynamics of F over the space X. The problem of computing (or even approximating) the topological entropy of a given cellular automata is algorithmically undecidable (Ergodic Theory Dynamical Systems 12 (1992) 255). In this paper, we show how to compute the entropy of two important classes of cellular automata namely, linear and positively expansive cellular automata. In particular, we prove a closed formula for the topological entropy of D-dimensional (D1) linear cellular automata over the ring Z_m (m2) and we provide an algorithm for computing the topological entropy of positively expansive cellular automata.     

On dynamics of automata with a stack

In this paper we introduce a new dynamical system of a pushdown automaton, called automaton with a stack (AS). We prove that every AS has a periodic configuration by construction of it. Next, we define a special case of an AS, called AS with finite memory and we prove that the AS has a finite memory if and only if it is positively expansive. Furthermore, we prove that every AS with finite memory has shadowing property. Having these two properties, we set a finite-to-one map between an AS with finite memory and some vertex subshift, which gives us a semi-conjugacy between these two systems. Additionally, we define an algorithm to decide if a given graph G describes some AS with finite memory and to calculate maximal depth of a stack.     

Resolution approach to testing compatibility of interacting automata

Conclusion The notion of compatibility of automata was proposed in [1] for formalization of requirements that must be met by interacting partial automata. Testing the compatibility of automata is of essential importance for the design of systems that interact with the environment, especially when we use declarative specificatio of the system to be designed. Under the assumptions of this article for the automaton that models the environment, partiality of the specified automaton is a source of possible incompatibility with the environment. When declarative specification is used, we can never decide in advance if the specified automaton is partial or not. Moreover, even a specification thata priori describes a completely defined automaton may be altered by the actions of the designer in the process of design (especially if these actions are incorrect) so that the specified automaton becomes partial. Therefore the initial specification, and each successive specification produced by human intervention in the design process, must be tested for compatibility with the environment. In the methodology of verification design of automata, compatibility testing is used to solve two problems: a) generating the specification of the class of all automata that satisfy the initial specification and are compatible with the specification of the environment; b) testing for correctness the designer's decisions that alter the current specification of the automaton being designed. The results of this article have led to the development of an efficient resolution procedure for testing the compatibility of automaton specification with the specification of the environment. this procedure has been implemented in the system for verification design of automata from their logical specifications. The efficiency of the developed procedure is based on the results of compatibility analysis of automata from [1] and on the restricted resolution strategy whose completeness and correctness have been proved in [2]. Translated from Kibernetika i Sistemnyi Analiz, No. 6, pp. 36–50, November–December, 1994.     

Task automata: Schedulability,decidability and undecidability

We present a model, task automata, for real time systems with non-uniformly recurring computation tasks. It is an extended version of timed automata with asynchronous processes that are computation tasks generated (or triggered) by timed events. Compared with classical task models for real time systems, task automata may be used to describe tasks (1) that are generated non-deterministically according to timing constraints in timed automata, (2) that may have interval execution times representing the best case and the worst case execution times, and (3) whose completion times may influence the releases of task instances. We generalize the classical notion of schedulability to task automata. A task automaton is schedulable if there exists a scheduling strategy such that all possible sequences of events generated by the automaton are schedulable in the sense that all associated tasks can be computed within their deadlines. Our first technical result is that the schedulability for a given scheduling strategy can be checked algorithmically for the class of task automata when the best case and the worst case execution times of tasks are equal. The proof is based on a decidable class of suspension automata: timed automata with bounded subtraction in which clocks may be updated by subtractions within a bounded zone. We shall also study the borderline between decidable and undecidable cases. Our second technical result shows that the schedulability checking problem will be undecidable if the following three conditions hold: (1) the execution times of tasks are intervals, (2) the precise finishing time of a task instance may influence new task releases, and (3) a task is allowed to preempt another running task.     

Infinity problems and countability problems for ω-automata

The infinity problem for ω-automata is to decide if the ω-language recognized by a given automaton is infinite; the countability problem is to decide if a given automaton recognizes a countable ω-language. We prove that these problems are NLogspace-complete for (nondeterministic) Büchi, generalized Büchi, Muller, Rabin and parity automata.     

Representation of reversible cellular automata with block permutations

We demonstrate the structural invertibility of all reversible one- and two-dimensional cellular automata. More precisely, we prove that every reversible two-dimensional cellular automaton can be expressed as a combination of four block permutations, and some shift-like mappings. Block permutations are very simple functions that uniformly divide configurations into rectangular regions of equal size and apply a fixed permutation on all regions.     

Inductive inference of logic programs based on algebraic semantics

In this paper we present a new inductive inference algorithm for a class of logic programs, calledlinear monadic logic programs. It has several unique features not found in Shapiro’s Model Inference System. It has been proved that a set of trees isrational if and only if it is computed by a linear monadic logic program, and that the rational set of trees is recognized by a tree automaton. Based on these facts, we can reduce the problem of inductive inference of linear monadic logic programs to the problem of inductive inference of tree automata. Further several efficient inference algorithms for finite automata have been developed. We extend them to an inference algorithm for tree automata and use it to get an efficient inductive inference algorithm for linear monadic logic programs. The correctness, time complexity and several comparisons of our algorithm with Model Inference System are shown.     

新型一维偏移耦合映像格系统及其动态特性

混沌系统具有复杂的动力学行为,但在数字系统中运行时会出现动力学特性退化的问题。元胞自动机在时间、空间上都具有离散性,能够有效减弱混沌系统在有限精度下的动力学退化问题。基于元胞自动机,提出了一种一维偏移耦合映像格系统,利用初等元胞自动机每次更新的不同状态,动态产生每个格子的耦合索引偏移量,再根据偏移量对混沌序列施加不同的扰动,然后交替切换元胞自动机的迭代规则。最后,对混沌系统的动力学特性进行对比分析以及对该系统产生的时间序列进行量化和随机性检测,仿真实验结果表明,该混沌系统周期更长,遍历性更好,产生的序列随机性更佳,在序列密码算法中有很大的应用价值。     

Complexity of control on finite automata

We consider control questions for finite automata viewed as input/output systems. In particular, we find estimates of the minimal number of states of an automaton able to control a given automaton. We prove that, on average, feedback closed-loop control automata do not have fewer states than open-loop control automata when the control objective is to steer the controlled automaton to a target state. We compare our approach to other ways of formalizing of formalizing analogous control objectives.     

On groups whose word problem is solved by a˜counter automaton

We prove that a group G has a word problem that is accepted by a deterministic counter automaton with a weak inverse property if and only if G is virtually abelian. We extend this result to larger classes of groups by considering a generalization of finite state automata, counter automata and pushdown automata. Natural corollaries of our general result include a restricted version of Herbst's classification of groups for which the word problem is a one counter language and a new classification of automata that accept context-free word problems.     

Recognition of directed acyclic graphs by spanning tree automata

In this paper, we study tree automata for directed acyclic graphs (DAGs). We define the movement of a tree automaton on a DAG so that a DAG is accepted by a tree automaton if and only if the DAG has a spanning tree accepted by the tree automaton. We call this automaton a spanning tree automaton. The NP-completeness of the membership problem of DAGs for spanning tree automata is shown. However, if inputs are restricted to series–parallel graphs or generalized series–parallel graphs, it is shown that the membership problem for spanning tree automata is solvable in linear time.     

Finite state automata representing two-dimensional subshifts

A new type of two-dimensional automaton has been defined to recognize a class of two-dimensional shifts of finite type having the property that every admissible block found within the related local picture language can be extended to a point of the subshift. Here it is shown that this automaton accurately represents the image of the represented two-dimensional shift of finite type under a block code. It is then shown that these automata can be used to check for a certain type of two-dimensional transitivity in the factor language of the corresponding shift space and how this relates to periodicity in the two-dimensional case. The paper closes with a notion of “follower sets” that are used to reduce the size of the automata representing two-dimensional sofic shifts.     

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.     

Power of interconnections and of nondeterminism in regularY-tree systolic automata

The increase of computational power due to additions of some horizontal interconnections between neighboring nodes of binary trees is investigated using the concept of systolic automata over so-called 7-trees with one-directional, bottom-to-root, flow of computation.Y-trees are obtained from binary trees by connecting some neighboring pairs of nodes at the same level that are not brothers.We introduce the concept of systolic automata on regularY-trees in column normal form and prove that any systolic automaton on regularY-trees is equivalent to one in the column normal form. We then fully characterize those regularY-trees over which the class of languages recognized by nondeterministic automata is the same as for deterministic automata. An analogous result is obtained for stability. Furthermore, we show that superstable deterministic systolic automata over regularY-trees recognize only regular languages. Finally, several closure properties of and relations between classes of languages accepted by systolic automata over differentY-trees are studied.The preliminary version of this paper was presented at the 2nd International Colloquium on Words, Languages, and Combinatorics in Kyoto, Japan, August 1992. This work has been partially supported by the Ministero dell' Universitá e della Ricerca Scientifica e Tecnologica of Italy and by a grant from the Slovak Academy of Sciences, Bratislava, Slovakia. The second author is on a leave of absence from the Institute of Informatics, Slovak Academy of Sciences, Bratislava, Slovakia.