The number of DFAs for a given spanning tree

In the last few decades, several techniques to randomly generate a deterministic finite automaton have been developed. These techniques have implications in the enumeration and random generation of automata of size n. One of the ways to generate a finite automaton is to generate a random tree and to complete it to a deterministic finite automaton, assuming that the tree will be the automaton’s breadth-first spanning tree. In this paper we explore further this method, and the string representation of a tree, and use it to counting the number of automata having a tree as a breadth-first spanning subtrees. We introduce the notions of characteristic and difference sequence of a tree, and define the weight of a tree. We also present a recursive formula for this quantity in terms of the “derivative” of a tree. Finally, we analyze the implications of this formula in terms of exploring trees with the largest and smallest number of automata in the span of the tree and present simple applications for finding densities of subsets of DFAs.     

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.     

Reversible pushdown automata

Reversible pushdown automata are deterministic pushdown automata that are also backward deterministic. Therefore, they have the property that any configuration occurring in any computation has exactly one predecessor. In this paper, the computational capacity of reversible computations in pushdown automata is investigated and turns out to lie properly in between the regular and deterministic context-free languages. Furthermore, it is shown that a deterministic context-free language cannot be accepted reversibly if more than realtime is necessary for acceptance. Closure properties as well as decidability questions for reversible pushdown automata are studied. Finally, we show that the problem to decide whether a given nondeterministic or deterministic pushdown automaton is reversible is P-complete, whereas it is undecidable whether the language accepted by a given nondeterministic pushdown automaton is reversible.     

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.     

Linear regular sets

Summary The purpose of this paper is to give a characterization of the sets of words accepted by finite linear automata. Since every linear automaton is isomorphic to a parallel product of a nilpotent linear automaton and a nonsingular linear automaton, our characterization is presented for these two classes of automata.     

Reachability Problems on Regular Ground Tree Rewriting Graphs

We consider the transition graphs of regular ground tree (or term) rewriting systems. The vertex set of such a graph is a (possibly infinite) set of trees. Thus, with a finite tree automaton one can represent a regular set of vertices. It is known that the backward closure of sets of vertices under the rewriting relation preserves regularity, i.e., for a regular set T of vertices the set of vertices from which one can reach T can be accepted by a tree automaton. The main contribution of this paper is to lift this result to the recurrence problem, i.e., we show that the set of vertices from which one can reach infinitely often a regular set T is regular, too. Since this result is effective, it implies that the problem whether, given a tree t and a regular set T, there is a path starting in t that infinitely often reaches T, is decidable. Furthermore, it is shown that the problems whether all paths starting in t eventually (respectively, infinitely often) reach T, are undecidable. Based on the decidability result we define a fragment of temporal logic with a decidable model-checking problem for the class of regular ground tree rewriting graphs.     

A learning automata-based heuristic algorithm for solving the minimum spanning tree problem in stochastic graphs

During the last decades, a host of efficient algorithms have been developed for solving the minimum spanning tree problem in deterministic graphs, where the weight associated with the graph edges is assumed to be fixed. Though it is clear that the edge weight varies with time in realistic applications and such an assumption is wrong, finding the minimum spanning tree of a stochastic graph has not received the attention it merits. This is due to the fact that the minimum spanning tree problem becomes incredibly hard to solve when the edge weight is assumed to be a random variable. This becomes more difficult if we assume that the probability distribution function of the edge weight is unknown. In this paper, we propose a learning automata-based heuristic algorithm to solve the minimum spanning tree problem in stochastic graphs wherein the probability distribution function of the edge weight is unknown. The proposed algorithm taking advantage of learning automata determines the edges that must be sampled at each stage. As the presented algorithm proceeds, the sampling process is concentrated on the edges that constitute the spanning tree with the minimum expected weight. The proposed learning automata-based sampling method decreases the number of samples that need to be taken from the graph by reducing the rate of unnecessary samples. Experimental results show the superiority of the proposed algorithm over the well-known existing methods both in terms of the number of samples and the running time of algorithm.     

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.     

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.     

Inference of structures of models of probabilistic dependences from statistical data

Problems of reconstruction of structures of probabilistic dependence models in the class of directed (oriented) acyclic graphs (DAGs) and mono-flow graphs are considered. (Mono-flow graphs form a subclass of DAGs in which the cycles with one collider are prohibited.) The technique of induced (provoked) dependences is investigated and its application to the identification of structures of models is shown. The algorithm “Collifinder-M” is developed that identifies all collider variables (i.e., solves an intermediate problem of reconstruction of the structure of a mono-flow model). It is shown that a generalization of the technique of induced dependences makes it possible to strengthen well-known rules of identification of orientation of edges in a DAG model. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 6, pp. 19–31, November–December 2005.     

Derivatives of tree sets with applications to grammatical inference

Tree automata generalize the notion of a finite automaton working on strings to that of a finite automaton operating on trees. Most results for finite automata have been extended to tree automata. In this paper we introduce tree derivatives which extend the concept of Brzozowski's string derivatives. We use tree derivatives for minimizing and characterizing tree automata. Tree derivatives are used as a basis of inference of tree automata from finite samples of trees. Our method compares tree derivative sets and infers a tree automaton based on the amount of overlap between the derivative sets. Several of the limitations present in the tree inference techniques by Brayer and Fu and Edwards, Gonzalez, and Thomason are not imposed by our algorithm.     

Context-free languages over infinite alphabets

In this paper we introduce context-free grammars and pushdown automata over infinite alphabets. It is shown that a language is generated by a context-free grammar over an infinite alphabet if and only if it is accepted by a pushdown automaton over an infinite alphabet. Also the generated (accepted) languages possess many of the properties of the ordinary context-free languages: decidability, closure properties, etc.. This provides a substantial evidence for considering context-free grammars and pushdown automata over infinite alphabets as a natural extension of the classical ones. Received November 27, 1995 / March 4, 1997     

On finite automata with limited nondeterminism

We develop a new algorithm for determining if a given nondeterministic finite automaton is limited in nondeterminism. From this, we show that the number of nondeterministic moves of a finite automaton, if limited, is bounded by where is the number of states. If the finite automaton is over a one-letter alphabet, using Gohon's result the number of nondeterministic moves, if limited, is less than . In both cases, we present families of finite automata demonstrating that the upper bounds obtained are almost tight. We also show that the limitedness problem of the number of nondeterministic moves of finite automata is PSPACE-hard. Since the problem is already known to be in PSPACE, it is therefore PSPACE-complete. Received: 14 June 1994 / 3 December 1997     

Using DAG transformations to verify Euler/Venn homogeneous and Euler/Venn FOL heterogeneous rules of inference

In this paper we will present a graph-transformation based method for the verification of heterogeneous first order logic (FOL) and Euler/Venn proofs. In previous work, it has been shown that a special collection of directed acyclic graphs (DAGs) can be used interchangeably with Euler/Venn diagrams in reasoning processes. Thus, proofs which include Euler/Venn diagrams can be thought of as proofs with DAGs where steps involving only Euler/Venn diagrams can be treated as particular DAG transformations. Here we will show how the characterization of these manipulations can be used to verify Euler/Venn proofs. Also, a method for verifying the use of heterogeneous Euler/Venn and FOL reasoning rules will be presented that is also based upon DAG transformations .     

Emptiness and Finiteness for Tree Automata with Global Reflexive Disequality Constraints

In recent years, several extensions of tree automata have been considered. Most of them are related with the capability of testing equality or disequality of certain subterms of the term evaluated by the automaton. In particular, tree automata with global constraints are able to test equality and disequality of subterms depending on the state to which they are evaluated. The emptiness problem is known decidable for this kind of automata, but with a non-elementary time complexity, and the finiteness problem remains unknown. In this paper, we consider the particular case of tree automata with global constraints when the constraint is a conjunction of disequalities between states, and the disequality predicate is forced to be reflexive. This restriction is significant in the context of XML definitions with monadic key constraints. We prove that emptiness and finiteness are decidable in triple exponential time for this kind of automata.     

一种测试语言包含的算法

在积自动机基础上,利用互模拟关系引出商自动机,用以解决积自动机的状态组合爆炸问题。进而提出一个自然的测试语言包含的算法,这种算法的空间复杂度与规范自动机的状态目呈指数关系即O（2^k),其中K是规范自动机的状态数目。     

Using DAG Transformations to Verify Euler/Venn Homogeneous and Euler/Venn FOL Heterogeneous Rules of Inference

In this paper we will present a graph-transformation based method for the verification of heterogeneous first order logic (FOL) and Euler/Venn proofs. It has been shown that a special collection of directed acyclic graphs (DAGs) can be used interchangeably with Euler/Venn diagrams in reasoning processes [4]. Thus, proofs which include Euler/Venn diagrams can be thought of as proofs with DAGs where steps involving only Euler/Venn diagrams can be treated as particular DAG transformations. In the work reported here, we will show how the characterization of these manipulations can be used to verify Euler/Venn proofs. Also, a method for verifying the use of heterogeneous Euler/Venn and FOL reasoning rules will be presented that is also based upon DAG transformations.     

A note on rebound automata

It was unknown whether there exists a context-free language not accepted by any deterministic rebound automaton. This paper solves this problem, and shows that there exists a context-free language not accepted by any nondeterministic rebound automaton. This paper also investigates closure properties of the class of rebound automata.     

有限自动机可识别语言的基数

利用有向图的邻接矩阵研究有限自动机的可识别语言的基数问题。通过建立有限自动机的可识别语言与其有向图中从初始结点（有限自动机的初始状态）到终止结点（有限自动机的终止状态）的路的一一对应关系,利用邻接矩阵给出了有限自动机的可识别语言的基数公式,研究了两个自动机不等价的充分条件。