Complementing two-way finite automata

We study the relationship between the sizes of two-way finite automata accepting a language and its complement. In the deterministic case, for a given automaton (2dfa) with n states, we build an automaton accepting the complement with at most 4n states, independently of the size of the input alphabet. Actually, we show a stronger result, by presenting an equivalent 4n-state 2dfa that always halts. For the nondeterministic case, using a variant of inductive counting, we show that the complement of a unary language, accepted by an n-state two-way automaton (2nfa), can be accepted by an O(n⁸)-state 2nfa. Here we also make 2nfa’s halting. This allows the simulation of unary 2nfa’s by probabilistic Las Vegas two-way automata with O(n⁸) states.     

概率有限自动机的积和分解

给出几种概率有限自动机的积,讨论了他们之间的相互关系,并在文献[1]的基础上利用这些积给出匀概率有限自动机的分解,证明了一个匀概率有限自动机可以分解为一个随机编码源、一个伯努利过程和一些确定有限自动机的串联积。     

A note on two-dimensional probabilistic finite automata

This note introduces two-dimensional probabilistic finite automata (2-pfa's), and investigates several properties of them. We first show that the class of sets recognized by 2-pfa's with bounded error probability, 2-PFA, is incomparable with the class of sets accepted by two-dimensional alternating finite automata. We then show that 2-PFA is not closed under row catenation, column catenation, row +, and column + operations in Siromoney et al. (G. Siromoney, R. Siromoney, K. Krithivasan, Inform. and Control 22 (1973) 447).     

Some algebraic properties of measure-once two-way quantum finite automata

Quantum finite automata (QFA) can be divided into four kinds depend upon the head-directions and the measure times. They are measure-once one way QFA (MO-1QFA) introduced by Moore and Crutchfield (Theor Comput Sci 237: 275–306, 2000); measure-many one way QFA (MM-1QFA) and measure-many two-way QFA (MM-2QFA) introduced by Kondacs and Watrous (Proceedings of the 38th IEEE annual symposium on 433 foundations of computer science, 66–75, 1997); and measure-once two-way QFA (MO-2QFA) which were not given until now. The purpose of this work is mainly to discuss one kind of QFA, which is called MO-2QFA for brief. First of all, the definition of MO-2QFA is given and the conditions for preserving unitary properties are shown. Then, we analysis the basic algebraic properties of the class of languages which can be recognized by MO-2QFA, such as the union, intersection, complement and reversal operations. As well, we consider the catenation operation on the class of quantum languages recognized by MO-2QFA is closed in the generalized conditions.      

Vector space formulation of probabilistic finite state automata

This paper develops a vector space model of a class of probabilistic finite state automata (PFSA) that are constructed from finite-length symbol sequences. The vector space is constructed over the real field, where the algebraic operations of vector addition and the associated scalar multiplication operations are defined on a probability measure space, and implications of these algebraic operations are interpreted. The zero element of this vector space is semantically equivalent to a PFSA, referred to as symbolic white noise. A norm is introduced on the vector space of PFSA, which provides a measure of the information content. An application example is presented in the framework of pattern recognition for identification of robot motion in a laboratory environment.     

On the power of real-time two-way multihead finite automata with jumps

We investigate the relative power of jumps, nondeterminism, and number of heads for real-time automata. Results include showing that jumps and power that cannot be compensated for by nondeterminism and more heads. We also show that k+1 heads are more powerful than k heads, even if the finite automaton is allowed head to head jumps.     

A comparison of collapsed Bayesian methods for probabilistic finite automata

This paper describes several collapsed Bayesian methods, which work by first marginalizing out transition probabilities, for inferring several kinds of probabilistic finite automata. The methods include collapsed Gibbs sampling (CGS) and collapsed variational Bayes, as well as two new methods. Their targets range over general probabilistic finite automata, hidden Markov models, probabilistic deterministic finite automata, and variable-length grams. We implement and compare these algorithms over the data sets from the Probabilistic Automata Learning Competition (PAutomaC), which are generated by various types of automata. We report that the CGS-based algorithm designed to target general probabilistic finite automata performed the best for any types of data.     

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.     

Wavelet-based feature extraction using probabilistic finite state automata for pattern classification

Real-time data-driven pattern classification requires extraction of relevant features from the observed time series as low-dimensional and yet information-rich representations of the underlying dynamics. These low-dimensional features facilitate in situ decision-making in diverse applications, such as computer vision, structural health monitoring, and robotics. Wavelet transforms of time series have been widely used for feature extraction owing to their time-frequency localization properties. In this regard, this paper presents a symbolic dynamics-based method to model surface images, generated by wavelet coefficients in the scale-shift space. These symbolic dynamics-based models (e.g., probabilistic finite state automata (PFSA)) capture the relevant information, embedded in the sensor data, from the associated Perron-Frobenius operators (i.e., the state-transition probability matrices). The proposed method of pattern classification has been experimentally validated on laboratory apparatuses for two different applications: (i) early detection of evolving damage in polycrystalline alloy structures, and (ii) classification of mobile robots and their motion profiles.     

Concise representations of regular languages by degree and probabilistic finite automata

Meyer and Fischer b][MF] proved that nondeterministic finite automata (NFA) can be exponentially more concise than deterministic finite automata (DFA) in their representations of regular languages. Several variants of that basic finite state machine model are now being used to analyze parallelism and to build real-time software systems [HL+]. Even though these variants can sometimes represent regular languages in a more concise manner than NFA, the underlying models fundamentally differ from NFA in how they operate. Degree automata [W] (DA), however, differ from NFA only in their acceptance criteria and accept only regular languages. We show here that DA are also exponentially more concise than NFA on some sequences of regular languages. We also show that the conciseness of probabilistic automata [R] with isolated cutpoints can be unbounded over DA and, concurrently, i.e., over the same sequence of languages, those DA can be exponentially more concise than NFA.Detlef Wotschke was supported in part by Deutsche Forschungsgemeinschaft under Grant No. Wo 334/2-1 and by Stiftung Volkswagenwerk under Grant No. II/62 325.     

Wavelet-based gender detection on off-line handwritten documents using probabilistic finite state automata

Detection of gender from handwriting of an individual presents an interesting research problem with applications in forensic document examination, writer identification and psychological studies. This paper presents an effective technique to predict the gender of an individual from off-line images of handwriting. The proposed technique relies on a global approach that considers writing images as textures. Each handwritten image is converted into a textured image which is decomposed into a series of wavelet sub-bands at a number of levels. The wavelet sub-bands are then extended into data sequences. Each data sequence is quantized to produce a probabilistic finite state automata (PFSA) that generates feature vectors. These features are used to train two classifiers, artificial neural network and support vector machine to discriminate between male and female writings. The performance of the proposed system was evaluated on two databases, QUWI and MSHD, within a number of challenging experimental scenarios and realized classification rates of up to 80%. The experimental results show the superiority of the proposed technique over existing techniques in terms of classification rates.     

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.     

PAC-learnability of probabilistic deterministic finite state automata in terms of variation distance

We consider the problem of PAC-learning distributions over strings, represented by probabilistic deterministic finite automata (PDFAs). PDFAs are a probabilistic model for the generation of strings of symbols, that have been used in the context of speech and handwriting recognition, and bioinformatics. Recent work on learning PDFAs from random examples has used the KL-divergence as the error measure; here we use the variation distance. We build on recent work by Clark and Thollard, and show that the use of the variation distance allows simplifications to be made to the algorithms, and also a strengthening of the results; in particular that using the variation distance, we obtain polynomial sample size bounds that are independent of the expected length of strings.     

An inner product space on irreducible and synchronizable probabilistic finite state automata

Probabilistic finite state automata (PFSA) have found their applications in diverse systems. This paper presents the construction of an inner-product space structure on a class of PFSA over the real field via an algebraic approach. The vector space is constructed in a stationary setting, which eliminates the need for an initial state in the specification of PFSA. This algebraic model formulation avoids any reference to the related notion of probability measures induced by a PFSA. A formal language-theoretic and symbolic modeling approach is adopted. Specifically, semantic models are constructed in the symbolic domain in an algebraic setting. Applicability of the theoretical formulation has been demonstrated on experimental data for robot motion recognition in a laboratory environment.