Zobrazeno 1 - 10
of 18 472
pro vyhledávání: '"Regular languages"'
Autor:
Hora, Ryuya
Both topos theory and automata theory are known for their multi-faceted nature and relationship with topology, algebra, logic, and category theory. This paper aims to clarify the topos-theoretic aspects of automata theory, particularly demonstrating
Externí odkaz:
http://arxiv.org/abs/2411.06358
Extracting finite state automata (FSAs) from black-box models offers a powerful approach to gaining interpretable insights into complex model behaviors. To support this pursuit, we present a weighted variant of Angluin's (1987) $\mathbf{L^*}$ algorit
Externí odkaz:
http://arxiv.org/abs/2411.06228
Autor:
COTUMACCIO, NICOLA1 nicola.cotumaccio@dal.ca, D'AGOSTINO, GIOVANNA2 giovanna.dagostino@uniud.it, POLICRITI, ALBERTO2 alberto.policriti@uniud.it, PREZZA, NICOLA3 nicola.prezza@unive.it
Publikováno v:
Journal of the ACM. Aug2023, Vol. 70 Issue 4, p1-62. 62p.
Autor:
Borenstein, Nadav, Svete, Anej, Chan, Robin, Valvoda, Josef, Nowak, Franz, Augenstein, Isabelle, Chodroff, Eleanor, Cotterell, Ryan
What can large language models learn? By definition, language models (LM) are distributions over strings. Therefore, an intuitive way of addressing the above question is to formalize it as a matter of learnability of classes of distributions over str
Externí odkaz:
http://arxiv.org/abs/2406.04289
Akademický článek
Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.
K zobrazení výsledku je třeba se přihlásit.
Autor:
Place, Thomas, Zeitoun, Marc
We classify the regular languages using an operator $\mathcal{C}\mapsto TL(\mathcal{C})$. For each input class of languages $\mathcal{C}$, it builds a larger class $TL(\mathcal{C})$ consisting of all languages definable in a variant of unary temporal
Externí odkaz:
http://arxiv.org/abs/2402.10080
The definition of period in finite-state Markov chains can be extended to regular languages by considering the transitions of DFAs accepting them. For example, the language $(\Sigma\Sigma)^*$ has period two because the length of a recursion (cycle) i
Externí odkaz:
http://arxiv.org/abs/2403.05088
Autor:
Casares, Antonio, Ohlmann, Pierre
In the context of two-player games over graphs, a language $L$ is called positional if, in all games using $L$ as winning objective, the protagonist can play optimally using positional strategies, that is, strategies that do not depend on the history
Externí odkaz:
http://arxiv.org/abs/2401.15384
Recent work by Hewitt et al. (2020) provides an interpretation of the empirical success of recurrent neural networks (RNNs) as language models (LMs). It shows that RNNs can efficiently represent bounded hierarchical structures that are prevalent in h
Externí odkaz:
http://arxiv.org/abs/2402.15814
We study the space complexity of the following problem: For a fixed regular language $L$, test membership of a sliding window of length $n$ to $L$ over a given stream of symbols. For deterministic streaming algorithms we prove a trichotomy theorem, n
Externí odkaz:
http://arxiv.org/abs/2402.13385