arXiv research

Train track automata for fully irreducible elements in Out(F_r).

Classifies knots in the Poincaré sphere, using fixed points and folding automata.

This note gives a brief survey of the minimum dilatation problem for pseudo-Anosov mapping classes, and the first explicit train track description of an infinite family of pseudo-Anosov mapping classes with orientable stable foliations and the conjectural minimum dilatation for closed surfaces of even genus $g \ge 2$.

Transformers simulate finite-state automata with fewer layers.

Study immersions of punctured 4-manifolds for quantum automata applications.

Quantum cellular automata form a homology theory.

We obtain an index of the complexity of a random sequence by allowing the role of the measure in classical probability theory to be played by a function we call the generating mechanism. Typically, this generating mechanism will be a finite automata. We generate a set of biased sequences by applying a finite state auto…

This document investigates the integration of adaptive distinguishing sequences into the process of active automata learning (AAL). A novel AAL algorithm "ADT" (adaptive discrimination tree) is developed and presented. Since the submission of the original thesis, the presented algorithm has been integrated into LearnLi…

We present an interactive version of an evidence-driven state-merging (EDSM) algorithm for learning variants of finite state automata. Learning these automata often amounts to recovering or reverse engineering the model generating the data despite noisy, incomplete, or imperfectly sampled data sources rather than optim…

Automaton models are often seen as interpretable models. Interpretability itself is not well defined: it remains unclear what interpretability means without first explicitly specifying objectives or desired attributes. In this paper, we identify the key properties used to interpret automata and propose a modification o…

Recurrent neural networks trained on regular languages exhibit stable states that can recover from noise.

Understanding how a learned black box works is of crucial interest for the future of Machine Learning. In this paper, we pioneer the question of the global interpretability of learned black box models that assign numerical values to symbolic sequential data. To tackle that task, we propose a spectral algorithm for the …

In this work we present ISA, a novel approach for learning and exploiting subgoals in reinforcement learning (RL). Our method relies on inducing an automaton whose transitions are subgoals expressed as propositional formulas over a set of observable events. A state-of-the-art inductive logic programming system is used …

Paper verifies RNNs using automata learning and model checking.

Designs a Cellular Automata rule for forming touching loop patterns.

CURIE uses cellular automata to detect concept drift in data streams.

New train tracks for complex homeomorphisms found.

A new layer learns abstract relations from graph structure using finite-state automata.

A framework for analyzing financial systems under scenario constraints.

LUNAR uses cellular automata for real-time data classification in fast streams.

Machine learning provides algorithms that can learn from data and make inferences or predictions on data. Stochastic acceptors or probabilistic automata are stochastic automata without output that can model components in machine learning scenarios. In this paper, we provide dynamic programming algorithms for the comput…

We show that the subsurface projection of a train track splitting sequence is an unparameterized quasi-geodesic in the curve complex of the subsurface. For the proof we introduce induced tracks, efficient position, and wide curves. This result is an important step in the proof that the disk complex is Gromov hyperbolic…

We show how well known rules of back propagation arise from a weighted combination of finite automata. By redefining a finite automata as a predictor we combine the set of all $k$-state finite automata using a weighted majority algorithm. This aggregated prediction algorithm can be simplified using symmetry, and we pro…

The paper distills a weighted automaton from RNNs for language modeling.

Paper translates train track concepts to cluster algebras for pseudo-Anosov mapping classes.

This work uses SVM to identify track component failures in AC Track Circuits.

This paper proposes DeepSynth, a method for effective training of deep Reinforcement Learning (RL) agents when the reward is sparse and non-Markovian, but at the same time progress towards the reward requires achieving an unknown sequence of high-level objectives. Our method employs a novel algorithm for synthesis of c…

Recurrent neural networks are a widely used class of neural architectures. They have, however, two shortcomings. First, it is difficult to understand what exactly they learn. Second, they tend to work poorly on sequences requiring long-term memorization, despite having this capacity in principle. We aim to address both…

The paper defines and proves the existence of train track maps on graphs of groups.

Study Agol cycles in pseudo-Anosov 3-braids.

Study of endperiodic maps on infinite graphs, proving homotopy and eigenvalue properties.

In the present work we introduce a stochastic cellular automata model in order to simulate the dynamics of the stock market. A direct percolation method is used to create a hierarchy of clusters of active traders on a two dimensional grid. Active traders are characterised by the decision to buy, (+1), or sell, (-1), a …

Reservoir computers (RCs) and recurrent neural networks (RNNs) can mimic any finite-state automaton in theory, and some workers demonstrated that this can hold in practice. We test the capability of generalized linear models, RCs, and Long Short-Term Memory (LSTM) RNN architectures to predict the stochastic processes g…

Using Lipschitz distance on Outer space we give another proof of the train track theorem.

Let $X$ be an infinite Riemann surface equipped with its conformal hyperbolic metric such that the action of the covering group $π_1(X)$ on $\tilde{X}$ is of the first kind-i.e., the surface $X$ is equal to its convex core. We first prove that any geodesic lamination on $X$ is nowhere dense. Given a fixed geodesic pant…

The study of pseudo-Anosov maps with minimum expansion factor using train tracks.

In this paper, we unravel a fundamental connection between weighted finite automata~(WFAs) and second-order recurrent neural networks~(2-RNNs): in the case of sequences of discrete symbols, WFAs and 2-RNNs with linear activation functions are expressively equivalent. Motivated by this result, we build upon a recent ext…

We present an algorithm for extraction of a probabilistic deterministic finite automaton (PDFA) from a given black-box language model, such as a recurrent neural network (RNN). The algorithm is a variant of the exact-learning algorithm L*, adapted to a probabilistic setting with noise. The key insight is the use of con…

Dual neural network architecture improves accuracy and interpretability.

In this paper we develop the metric theory for the outer space of a free product of groups. This generalizes the theory of the outer space of a free group, and includes its relative versions. The outer space of a free product is made of $G$-trees with possibly non-trivial vertex stabilisers. The strategies are the same…

We provide the first solution for model-free reinforcement learning of ω-regular objectives for Markov decision processes (MDPs). We present a constructive reduction from the almost-sure satisfaction of ω-regular objectives to an almost- sure reachability problem and extend this technique to learning how to control an …

We prove that for every P there is a bound B depending only on P so that the mapping torus of every P--small irreducible train-track map can be obtained by surgery from one of B mapping tori. We show that given an integer P>0 there is a bound $M$ depending only on P, so that there exists a presentation of the fundament…

We define "fat" train tracks and use them to give a combinatorial criterion for the Hempel distance of Heegaard splittings for closed orientable 3-manifolds. We apply this criterion to 3-manifolds obtained from surgery on knots in the three sphere.

Let $S_{g,p}$ denote the genus $g$ orientable surface with $p$ punctures. We show that nested train track sequences constitute $O((g,p)^{2})$-quasiconvex subsets of the curve graph, effectivizing a theorem of Masur and Minsky. As a consequence, the genus $g$ disk set is $O(g^{2})$-quasiconvex. We also show that splitti…

The thesis shows how automorphisms of hyperbolic groups can be represented by train track maps.

Any endomorphism of a finitely generated free group naturally descends to an injective endomorphism of its stable quotient. In this paper, we prove a geometric incarnation of this phenomenon: namely, that every expanding irreducible train track map inducing an endomorphism of the fundamental group gives rise to an expa…

Masked LARk prevents cross-site tracking while training models.

BootsTAP uses real-world data to improve TAP tracking performance.