Zobrazeno 1 - 10
of 33 408
pro vyhledávání: '"Automata Theory"'
Autor:
Loregian, Fosco
We study monads in the (pseudo-)double category $\mathbf{KSW}(\mathcal{K})$ where loose arrows are Mealy automata valued in an ambient monoidal category $\mathcal{K}$, and the category of tight arrows is $\mathcal{K}$. Such monads turn out to be eleg
Externí odkaz:
http://arxiv.org/abs/2501.01882
Autor:
Shallit, Jeffrey
In 2009 Benoit Cloitre introduced a certain self-generating sequence $$(a_n)_{n\geq 1} = 1, 1, 2, 1, 1, 1, 1, 2, 1, 1, 2, 1, 1, 2, 2, \ldots,$$ with the property that the sum of the terms appearing in the $n$'th run equals twice the $n$'th term of th
Externí odkaz:
http://arxiv.org/abs/2501.00784
Reward machines (RMs) are an effective approach for addressing non-Markovian rewards in reinforcement learning (RL) through finite-state machines. Traditional RMs, which label edges with propositional logic formulae, inherit the limited expressivity
Externí odkaz:
http://arxiv.org/abs/2501.00364
Autor:
Fici, Gabriele
I will show that there exist two binary words (one of length 4 and one of length 6) that play a special role in many different problems in combinatorics on words. They can therefore be considered \textit{the shortest interesting binary words}. My cla
Externí odkaz:
http://arxiv.org/abs/2412.21145
Autor:
Deng, Bruce, Kejriwal, Mayank
Agent-based modeling (ABM) has become a cornerstone of complexity science, enabling the study of heterogeneous agents interacting within dynamic environments. Among ABM frameworks, John Conway's Game of Life (GoL) stands out for its simplicity and ab
Externí odkaz:
http://arxiv.org/abs/2412.20691
Quantum fingerprinting is a technique that maps classical input word to a quantum state. The obtained quantum state is much shorter than the original word, and its processing uses less resources, making it useful in quantum algorithms, communication,
Externí odkaz:
http://arxiv.org/abs/2412.18823
Two finite words are k-binomially equivalent if each subword (i.e., subsequence) of length at most k occurs the same number of times in both words. The k-binomial complexity of an infinite word is a function that maps the integer $n\geq 0$ to the num
Externí odkaz:
http://arxiv.org/abs/2412.18425
Autor:
Shallit, Jeffrey
The paperfolding sequences form an uncountable class of infinite sequences over the alphabet $\{ -1, 1 \}$ that describe the sequence of folds arising from iterated folding of a piece of paper, followed by unfolding. In this note we observe that the
Externí odkaz:
http://arxiv.org/abs/2412.17930
Autor:
Idir, Olivier, Lehtinen, Karoliina
The parity index problem of tree automata asks, given a regular tree language L, what is the least number of priorities of a nondeterministic parity tree automaton that recognises L. This is a long-standing open problem, also known as the Mostowski o
Externí odkaz:
http://arxiv.org/abs/2412.16793