An elementary proof of the completeness of PDL

We give an elementary proof of the completeness of the Segerberg axions for Propositional Dynamic Logic.     

Computability by finite automata and pisot bases

We prove that the function of normalization in base , which maps any -representation of a real number onto its -development, obtained by a greedy algorithm, is a function computable by a finite automaton over any alphabet if and only if is a Pisot number.Christiane Frougny was supported in part by the PRC Mathématiques et Informatique of the Ministère de la Recherche et de l'Espace.     

An alternate proof of Statmanʼs finite completeness theorem

Statman?s finite completeness theorem says that for every pair of non-equivalent terms of simply-typed lambda-calculus there is a model that separates them. A direct method of constructing such a model is provided using a simple induction on the Böhm tree of the term.     

An application of quantum finite automata to interactive proof systems

Quantum finite automata have been studied intensively since their introduction in late 1990s as a natural model of a quantum computer working with finite-dimensional quantum memory space. This paper seeks their direct application to interactive proof systems in which a mighty quantum prover communicates with a quantum-automaton verifier through a common communication cell. Our quantum interactive proof systems are juxtaposed to Dwork–Stockmeyer's classical interactive proof systems whose verifiers are two-way probabilistic finite automata. We demonstrate strengths and weaknesses of our systems by studying how various restrictions on the behaviors of quantum-automaton verifiers affect the power of quantum interactive proof systems.     

Solving nonlinear eigenvalue problems by algorithmic differentiation

The eigenvalues of a matrixA(λ), the elements of which are complex functions of a complex variable λ, can be found with a zero finding method applied to the determinant function detA(λ). It is proposed to evaluate the derivatives of det (λ) used in the zero finding method by algorithmic differentiation. This leads to a simple and lucid algorithm. Program listings and numerical examples are given.     

Surjective multidimensional cellular automata are non-wandering: A combinatorial proof

A combinatorial proof that surjective D-dimensional CA are non-wandering is given. This answers an old open question stated in Blanchard and Tisseur (2000) [3]. Moreover, an explicit upper bound for the return time is given.     

Boundary properties of graphs for algorithmic graph problems

The notion of a boundary graph property was recently introduced as a relaxation of that of a minimal property and was applied to several problems of both algorithmic and combinatorial nature. In the present paper, we first survey recent results related to this notion and then apply it to two algorithmic graph problems: Hamiltonian cycle and vertexk-colorability. In particular, we discover the first two boundary classes for the Hamiltonian cycle problem and prove that for any k>3 there is a continuum of boundary classes for vertexk-colorability.     

Unsolvability of some algorithmic problems for straight-line programs

We show that the problems of one-equivalence, equivalence, and simplification are undecidable for two classes of straight-line programs with a limited set of simple operations and a limited number of input and local variables.Translated from Kibernetika, No. 1, pp. 63–66, January–February, 1989.     

Yet another proof of the cascade decomposition theorem for finite automata

We give here a short proof that each finite automaton can be built as a cascade of permutation automata and identity-reset automata.This paper was presented at the Conference on the Algebraic Theory of Machines, Languages and Semigroups, 29 August–8 September 1966, at Asilomar, California, organized by the Krohn-Rhodes Research Institute.     

Polynomial complete problems in automata theory

Kozen (1977) proved that the emptiness problem for regular languages intersection is polynomial complete. In this paper we show that many other problems concerning deterministic finite state automata are polynomial complete and therefore intractable for solution. On the other hand, simplified versions of these problems can be solved in polynomial time by deterministic algorithms. This work is a part of the research on automata theory carried out at the Institute of Cybernetics headed by academician V.M. Glushkov.     

Exact complexity of problems of incompletely specified automata

This paper is devoted to the study ofreduction of incompletely specified automata (RISA). A variant of this problem consists in having a set of initial states (instead of a unique initial state) and is denoted by RISS. The problemk-RISA ^r (resp.k-RISS ^r ) is the restricted version in which the number of states of the reduced automaton,k, and the size of the input alphabet,r, are fixed. We prove thatk-RISA ^r is in P, whereask-RISS ^r is NP-complete (and even linearly equivalent to SAT) fork 11 andr 2, thus completing the study of computational complexity of problems of reduction of incompletely specified automata and structures.