A full Mealy automaton is associated with a graph and a square complex, which contains an anti-torus if and only if the automaton is bi-reversible and the graph is aperiodic.
problem Determining the existence of anti-tori in square complexes associated with Mealy automata
method Associating a graph and a square complex with a Mealy automaton and proving the equivalence between bi-reversibility and aperiodicity of the graph
result The square complex contains an anti-torus if and only if the automaton is bi-reversible and the graph is aperiodic
Paper details Hilbert-curve for high-performance data mining.
problem Efficiently mapping multi-dimensional data to one dimension.
method Defines Hilbert-curve using finite automaton and context-free grammar.
result Cache-oblivious algorithms for matrix operations and clustering.
Paper defines topology automaton for Barański carpets and proves Hölder equivalence conditions.
problem Tackles Hölder equivalence of Barański carpets.
method Defines topology automaton and applies method from previous studies.
result Obtains sufficient condition for Hölder equivalence of Barański carpets.
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 …
In this paper we study Thurston's automaton on the braid groups via binary operations. These binary operations are obtained from the construction of this automaton. We study these operations and find some connections between them in a "skew lattice" spirit.
Method extracts knowledge from LSTM for sequence validation.
problem Validating sequences generated by unknown automata.
method Clustering hidden states to build a corresponding automaton.
result Automaton accurately predicts sequence validity.
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…
The language of maximal lexicographic representatives of elements in the positive braid monoid An with n generators is a regular language. We describe with great detail the smallest Finite State Automaton accepting such language, and study the proportion of elements of length k whose maximal lexicographic repres…
The paper distills a weighted automaton from RNNs for language modeling.
problem Tackles the gap between deep learning and grammatical inference.
method Uses a spectral approach to infer a weighted automaton from a trained RNN.
result Extracted weighted automata are good approximations of the RNNs, validating the approach.
New formulas derived for Jones polynomial of rational links.
problem Calculating the Jones polynomial of rational links.
method Colored Brylawski's tensor product formula for Tutte polynomials, finite automaton for crossing signs.
result Generalization of existing formulas for rational links.
A new layer learns abstract relations from graph structure using finite-state automata.
problem Learning abstract relations from graph structure for program analysis.
method Relaxing the problem into learning finite-state automata policies on a graph-based POMDP and training these policies using implicit differentiation.
result GFSA layer finds shortcuts in grid-world graphs and reproduces simple static analyses on Python programs.
Deep learning models predict faster dune migration in arid regions.
problem Predicting the movement of sand dunes in arid regions.
method Tested two deep learning algorithms (GAN and CNN) on simulated data from a cellular automaton model.
result Deep learning models can predict dune migration at ten million times the speed of existing models.
Representative investors whose behaviour is modelled by a deterministic finite automaton generate complexity both in the time series of each asset and in the cross-sectional correlation when the rule governing their behaviour is schizophrenic, meaning the investor must hold multiple seemingly contradictory beliefs simu…
Transformers simulate finite-state automata with fewer layers.
problem How do shallow, non-recurrent Transformers simulate complex computations?
method Hierarchical reparameterization of recurrent dynamics to simulate automata.
result Polynomial-sized, O(logT)-depth solutions exist and are common. Hidden tree Markov models allow learning distributions for tree structured data while being interpretable as nondeterministic automata. We provide a concise summary of the main approaches in literature, focusing in particular on the causality assumptions introduced by the choice of a specific tree visit direction. We w…
Braids can be represented geometrically as laminations of punctured disks. The geometric complexity of a braid is the minimal complexity of a lamination that represents it, and tight laminations are representatives of minimal complexity. These laminations give rise to a normal form of braids, via a relaxation algorithm…
We discuss algorithms for estimating the Shannon entropy h of finite symbol sequences with long range correlations. In particular, we consider algorithms which estimate h from the code lengths produced by some compression algorithm. Our interest is in describing their convergence with sequence length, assuming no limit…
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…
We present a method to extract a weighted finite automaton (WFA) from a recurrent neural network (RNN). Our algorithm is based on the WFA learning algorithm by Balle and Mohri, which is in turn an extension of Angluin's classic \lstar algorithm. Our technical novelty is in the use of \emph{regression} methods for the s…
Study of group actions on CAT(0) cube complexes, focusing on marked length spectra.
problem Comparing marked length spectra of group actions on CAT(0) cube complexes.
method Use of finite-state automata and thermodynamic formalism for suspension flows over subshifts of finite type.
result Prove that the Manhattan curve is analytic and convex, and a straight line if and only if marked length spectra are homothetic.
Reinforcement Learning (RL) is a widely employed machine learning architecture that has been applied to a variety of control problems. However, applications in safety-critical domains require a systematic and formal approach to specifying requirements as tasks or goals. We propose a model-free RL algorithm that enables…
Autostackability for finitely generated groups is defined via a topological property of the associated Cayley graph which can be encoded in a finite state automaton. Autostackable groups have solvable word problem and an effective inductive procedure for constructing van Kampen diagrams with respect to a canonical fini…
One purpose of this article is to draw attention to the seminal work of J. Mealy in 1989 on calibrations in semi-riemannian geometry where split SLAG geometry was first introduced. The natural setting is provided by doing geometry with the complex numbers C replaced by the double numbers D, where i with i^2 = -1 is rep…
Paper verifies RNNs using automata learning and model checking.
problem Verifying the correctness of RNNs is challenging.
method Learn a deterministic finite automaton from RNN, use model checking for verification.
result Can discover and generalize counterexamples to faulty flows.
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…
In recent years, distance education has enjoyed a major boom. Much work at The Open University (OU) has focused on improving retention rates in these modules by providing timely support to students who are at risk of failing the module. In this paper we explore methods for analysing student activity in online virtual l…
We study the problem of online path learning with non-additive gains, which is a central problem appearing in several applications, including ensemble structured prediction. We present new online algorithms for path learning with non-additive count-based gains for the three settings of full information, semi-bandit and…
Most people are risk-averse (risk-seeking) when they expect to gain (lose). Based on a generalization of ``expected utility theory'' which takes this into account, we introduce an automaton mimicking the dynamics of economic operations. Each operator is characterized by a parameter q which gauges people's attitude unde…
We propose a method for efficient training of Q-functions for continuous-state Markov Decision Processes (MDPs) such that the traces of the resulting policies satisfy a given Linear Temporal Logic (LTL) property. LTL, a modal logic, can express a wide range of time-dependent logical properties (including "safety") that…
In the context of learning deterministic policies in continuous domains, we revisit an approach, which was first proposed in Continuous Actor Critic Learning Automaton (CACLA) and later extended in Neural Fitted Actor Critic (NFAC). This approach is based on a policy update different from that of deterministic policy g…
Reinforcement Learning (RL) has emerged as an efficient method of choice for solving complex sequential decision making problems in automatic control, computer science, economics, and biology. In this paper we present a model-free RL algorithm to synthesize control policies that maximize the probability of satisfying h…
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…
CURIE uses cellular automata to detect concept drift in data streams.
problem Detecting changes in data distribution (concept drift) in data streams.
method CURIE represents data stream distribution in a cellular automata grid and uses its neighborhood rule to detect changes.
result CURIE, when hybridized with base learners, performs competitively in detection metrics and classification accuracy.
Compactifies stability conditions on triangulated categories, inspired by Teichmüller theory.
problem Moduli space of stability conditions on triangulated categories.
method Inspired by Thurston compactification of Teichmüller space, constructs maps to infinite projective space.
result Injective maps with compact closure, identifies categorical analogs of intersection functionals.
New neural stack and Turing Machine architectures prove stability and computational power.
problem Designing stable neural network architectures for Turing Machine simulation.
method Introducing neural stack and Turing Machine architectures, proving stability and computational equivalence.
result Differentiable nnTM with bounded neurons can simulate Turing Machine in real-time and is equivalent to UTM.
We introduce the State Classification Problem (SCP) for hybrid systems, and present Neural State Classification (NSC) as an efficient solution technique. SCP generalizes the model checking problem as it entails classifying each state s of a hybrid automaton as either positive or negative, depending on whether or not …
Faster Tsetlin Machines use clause indexing to speed inference and learning.
problem Overfitting and slow inference in Tsetlin Machines.
method Introduced a look-up table that indexes clauses based on feature falsification, enabling faster evaluation of clauses.
result Up to 15 times faster classification and three times faster learning on MNIST and Fashion-MNIST.
Convolutional networks struggle to learn Game of Life, even with lottery ticket weights.
problem Training convolutional networks to predict Conway's Game of Life is challenging.
method Examined small convolutional networks trained on Game of Life, focusing on weight initializations and network sizes.
result Minimal networks require significantly more parameters to converge, and their performance is sensitive to small changes in weights.
Machine learning predicts critical points for directed percolation models.
problem Determining critical points for directed percolation models.
method Supervised and unsupervised machine learning algorithms (CNN and DBSCAN) were used.
result Machine learning accurately predicts critical points for both models.