The “equal last letter” predicate for words on infinite alphabets and classes of multitape automata

We consider the first-order theory of the free infinitely generated monoid with the usual predicates “prefix” and “equal length” along with the predicate “equal last letter”. The associated definable relations are related to the algebras of relations recognized by different types of multitape automata which are natural extensions of the famous Rabin–Scott multitape automata and the synchronous automata. We investigate these classes of automata and solve decision issues concerning them.     

Program equivalence checking by two-tape automata

This paper shows how two-tape automata can be employed to design efficient equivalence checking procedures for sequential programs. The semantics of sequential programs is defined in terms of dynamic logic structures. If a dynamic frame is acyclic (i.e., all program statements are irreversible), then it can be specified by means of a two-tape deterministic automaton. Then the equivalence checking problem for sequential programs in which the semantics of operators is determined by acyclic dynamic frames can be reduced to the emptiness problem for two-tape automata (compound machines).     

On probabilistic analog automata

We consider probabilistic automata on a general state space and study their computational power. The model is based on the concept of language recognition by probabilistic automata due to Rabin (Inform. Control 3 (1963) 230) and models of analog computation in a noisy environment suggested by Maass and Orponen (Neural Comput. 10 (1998) 1071), and Maass and Sontag (Neural Comput. 11 (1999) 771). Our main result is a generalization of Rabin's reduction theorem that implies that under very mild conditions, the computational power of such automata is limited to regular languages.     

Tree-stack automata

We introduce a new model of stack automata, the “tree-stack automata,” extending the linear stack to a tree-stack. A main subject of our investigations is to explore the relationship between tree-stack automata and stack automata. The main result of this paper is that tree-stack have the same recognition power as stack-pushdown automata, another (well-known) extension of stack automata. Therefore we obtain that the class of languages accepted by the one-way (linear) stack automata is a proper subset of the class of languages accepted by the one-way tree-stack automata and that two-way tree-stack automata have the same recognition power as two-way (linear) stack automata. As a special case of tree-stack automata we consider tree-pushdown automata. As opposed to stack automata the tree-pushdown storage does not extend the recognition power of one-way (resp. two-way) pushdown automata.     

Algorithmic probabilistic game semantics

We present a detailed account of a translation from probabilistic call-by-value programs with procedures to Rabin’s probabilistic automata. The translation is fully abstract in that programs exhibit the same computational behaviour if and only if the corresponding automata are language-equivalent. Since probabilistic language equivalence is decidable, we can apply the translation to analyse the behaviour of probabilistic programs and protocols. We illustrate our approach on a number of case studies.     

On stateless multihead automata: Hierarchies and the emptiness problem

We look at stateless multihead finite automata in their two-way and one-way, deterministic and nondeterministic variations. The transition of a k-head automaton depends solely on the symbols currently scanned by its k heads, and every such transition moves each head one cell left or right, or instructs it to stay. We show that stateless (k+4)-head two-way automata are more powerful than stateless k-head two-way automata. In the one-way case, we prove a tighter result: stateless (k+1)-head one-way automata are more powerful than stateless k-head one-way automata. Finally, we show that the emptiness problem for stateless 2-head two-way automata is undecidable.     

Timed tree automata with an application to temporal logic

Finite automata on -sequences and -trees were introduced in the sixties by Büchi, McNaughton and Rabin. Finite automata on timed -sequences were introduced by Alur and Dill. In this paper we extend the theory of timed -sequences to -trees. The main motivation is the introduction of a new way to specify real-time systems and to study, using automata-theoretic techniques, branching-time temporal logics with timing constraints. We study closure properties and decision problems for the obtained classes of timed -tree languages. In particular, we show the decidability of the emptiness problem. As an application of the introduced theory, we give a new decidable branching time temporal logic (STCTL) whose semantics is based upon timed -trees. Received: 8 September 1997 / 27 June 2001     

Multihead Two-Way Probabilistic Finite Automata

We present properties of multihead two-way probabilistic finite automata that parallel those of their deterministic and nondeterministic counterparts. We define multihead probabilistic finite automata withlogspace constructible transition probabilities, and we describe a technique to simulate these automata by standard logspace probabilistic Turing machines. Next, we represent logspace probabilistic complexity classes as proper hierarchies based on corresponding multihead two-way probabilistic finite automata, and we show their (deterministic logspace) reducibility to the second levels of these hierarchies. We obtain a simple formula for the maximum inherent bandwidth of the configuration transition matrices associated with thek-head probabilistic finite automata processing a length-n input string. (The inherent bandwidth of the configuration transition matrices associated with an automaton processing a length-n input string is the smallest bandwidth we can get by changing the enumeration order of the automaton’s configurations.) Partially based on this relation, we find an apparently easier logspace complete problem forPL (the class of languages recognized by logspace unbounded-error probabilistic Turing machines), and we discuss possibilities for a space-efficient deterministic simulation of probabilistic automata. This research was supported by the National Science Foundation under Grant No. CDA 8822724 while the author was at the University of Rochester. An extended abstract of this paper appeared in Proceedings, Second Latin American Symposium, LATIN ’95: Theoretical Informatics, Valparaiso, Chile, April 1995.     

Multihead two-way probabilistic finite automata

We present properties of multihead two-way probabilistic finite automata that parallel those of their deterministic and nondeterministic counterparts. We define multihead probabilistic finite automata withlogspace constructible transition probabilities, and we describe a technique to simulate these automata by standard logspace probabilistic Turing machines. Next, we represent logspace probabilistic complexity classes as proper hierarchies based on corresponding multihead two-way probabilistic finite automata, and we show their (deterministic logspace) reducibility to the second levels of these hierarchies. We obtain a simple formula for the maximum inherent bandwidth of the configuration transition matrices associated with thek-head probabilistic finite automata processing a length-n input string. (The inherent bandwidth of the configuration transition matrices associated with an automaton processing a length-n input string is the smallest bandwidth we can get by changing the enumeration order of the automaton’s configurations.) Partially based on this relation, we find an apparently easier logspace complete problem forPL (the class of languages recognized by logspace unbounded-error probabilistic Turing machines), and we discuss possibilities for a space-efficient deterministic simulation of probabilistic automata.     

From LTL to deterministic automata

We present a new algorithm to construct a (generalized) deterministic Rabin automaton for an LTL formula \(\varphi \). The automaton is the product of a co-Büchi automaton for \(\varphi \) and an array of Rabin automata, one for each \({\mathbf {G}}\)-subformula of \(\varphi \). The Rabin automaton for \({\mathbf {G}}\psi \) is in charge of recognizing whether \({\mathbf {F}}{\mathbf {G}}\psi \) holds. This information is passed to the co-Büchi automaton that decides on acceptance. As opposed to standard procedures based on Safra’s determinization, the states of all our automata have a clear logical structure, which allows for various optimizations. Experimental results show improvement in the sizes of the resulting automata compared to existing methods.     

Cyclic closure properties of automata on a two-dimensional tape

In this paper, we investigate cyclic closure properties of several types of automata on a two-dimensional tape. It is shown that (1) the classes of sets accepted by two-dimensional finite automata, deterministic one-way parallel/sequential array automata, and two-dimensional deterministic on-line tessellation acceptors are not closed under row or column cyclic closure, and (2) the class of sets accepted by two-way parallel-sequential array automata is not closed under row cyclic closure.     

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.     

Equivalence of data flow schemas

The notion of logic-term equivalence of data flow schemas is introduced and its decidability is proved for some subclasses of schemas. A comparison with sequential schemas and two-tape automata is carried out.Translated from Kibernetika, No. 3 pp. 1–10, May–June, 1989.     

Learning two-tape automata from queries and counterexamples

We investigate the learning problem of two-tape deterministic finite automata (2-tape DFAs) from queries and counterexamples. Instead of accepting a subset of ∑*, a 2-tape DFA over an alphabet ∑ accepts a subset of ∑* × ∑*, and therefore, it can specify a binary relation on ∑*. In [3] Angluin showed that the class of deterministic finite automata (DFAs) is learnable in polynomial time from membership queries and equivalence queries, namely, from a minimally adequate teacher (MAT). In this article we show that the class of 2-tape DFAs is learnable in polynomial time from MAT. More specifically, we show an algorithm that, given any languageL accepted by an unknown 2-tape DFAM, learns from MAT a two-tape nonde-terministic finite automaton (2-tape NFA)M′ acceptingL in time polynomial inn andl, wheren is the size ofM andl is the maximum length of any counterexample provided during the learning process. This work was supported in part by Grants-in-Aid for Scientific Research No. 04229105 from the Ministry of Education, Science, and Culture, Japan.     

An improvement on valiant's decision procedure for equivalence of deterministic finite turn pushdown machines

Valiant has shown that the equivalence problem for deterministic finite turn pushdown machines is decidable. In this paper we show that his partial procedure for equivalence can be made constructive. To test equivalence for two given machines it suffices to construct one pda and test for emptiness. It is also shown that the time complexity of the algorithm is bounded by a double exponential function of the size of the input. The algorithm can be applied to deterministic two-tape automata and in this case the time complexity is exponential.     

On multi-head automata with restricted nondeterminism

In this work, we consider deterministic two-way multi-head automata, the input heads of which are nondeterministically initialised, i.e., in every computation each input head is initially located at some nondeterministically chosen position of the input word. This model serves as an instrument to investigate restricted nondeterminism of two-way multi-head automata. Our result is that, in terms of expressive power, two-way multi-head automata with nondeterminism in form of nondeterministically initialising the input heads or with restricted nondeterminism in the classical way, i.e., in every accepting computation the number of nondeterministic steps is bounded by a constant, do not yield an advantage over their completely deterministic counter-parts with the same number of input heads. We conclude this paper with a brief application of this result.     

Stable trace automata vs. full trace automata

Trace automata provide a well-studied model for systems with concurrent behavior, which is usually given by associated domains of finite or infinite computation systems. Several authors in the literature have characterized order-theoretically these domains which are typically particular Scott domains. In most of these investigations, the question remain open when such a domain can be obtained from some finite automaton. In this paper it is shown that finite stable trace automata and finite full trace automata give rise to the same class of coherent dI-domains. The proof of this result involves combinatorial means from graph theory (colorings) and Ramsey's theorem.     

Alternating two-way AC-tree automata

We explore the notion of alternating two-way tree automata modulo the theory of finitely many associative-commutative (AC) symbols. This was prompted by questions arising in cryptographic protocol verification, in particular in modeling group key agreement schemes based on Diffie-Hellman-like functions, where the emptiness question for intersections of such automata is fundamental. This also has independent interest. We show that the use of general push clauses, or of alternation, leads to undecidability, already in the case of one AC symbol, with only functions of arity zero. On the other hand, emptiness is decidable in the general case of several function symbols, including several AC symbols, provided push clauses are unconditional and intersection clauses are final. This class of automata is also shown to be closed under intersection.     

PSL构造双向交换自动机及非确定自动机的方法

PSL(property specification language)是一种用于描述并行系统的属性规约语言,包括线性时序逻辑FL(foundation language)和分支时序逻辑OBE(optional branching extension)两部分.由于OBE就是CTL(computation tree logic),并且具有时钟声明的公式很容易改写成非时钟公式,因此重点研究了非时钟FL逻辑.为便于进行模型检验,每个FL公式必须转化成为一种可验证形式,通常是自动机(非确定自动机).构造非确定自动机的过程主要是通过中间构建交换自动机来实现.详细给出了由非时钟FL构造双向交换自动机的构造规则.构造规则的核心逻辑不仅仅局限于是在LTL(linear temporal logic)基础上的正规表达式,而且全面而充分地考虑了各种FL操作算子的可能性.并且给出了将双向交换自动机转化为非确定自动机的一种方法.最后,编写了将PSL转化为上述自动机的实现工具.FL双向交换自动机的构造规则计算复杂度仅是FL公式长度的线性表达式,验证了构造规则的正确性.在此基础上,证明了双向交换自动机与其转化的等价的非确定自动机接受的语言相同.上述工作对解决复杂并行系统建模和模型验证问题具有重要的理论意义和应用价值.