Partial Answer of How Transformers Learn Automata
We introduce a novel framework for simulating finite automata using representation-theoretic semidirect products and Fourier modules, achieving more efficient Transformer-based implementations.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
The Role of Logic and Automata in Understanding Transformers
The advent of transformers has in recent years led to powerful and revolutionary Large Language Models (LLMs). Despite this, our understanding on the capability of transformers is still meager. In this invited contributi…
Simulating Weighted Automata over Sequences and Trees with Transformers
Transformers are ubiquitous models in the natural language processing (NLP) community and have shown impressive empirical successes in the past few years. However, little is understood about how they reason and the limit…
Bridging Graph Position Encodings for Transformers with Weighted Graph-Walking Automata
A current goal in the graph neural network literature is to enable transformers to operate on graph-structured data, given their success on language and vision tasks. Since the transformer's original sinusoidal positiona…
Graph Neural NetworkMachine TranslationPositionOn (co-lex) Ordering Automata
The states of a deterministic finite automaton A can be identified with collections of words in Pf(L(A)) -- the set of prefixes of words belonging to the regular language accepted by A. But words can be ordered and among…
An evolutionary approach to the identification of Cellular Automata based on partial observations
In this paper we consider the identification problem of Cellular Automata (CAs). The problem is defined and solved in the context of partial observations with time gaps of unknown length, i.e. pre-recorded, partial confi…