Zobrazeno 1 - 10
of 1 917
pro vyhledávání: '"Nondeterministic finite automaton"'
Autor:
Hiroshi Fujiwara, Hiroaki Yamamoto
Publikováno v:
IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS. (3):381-388
This paper presents a new method to translate a regular expression into a nondeterministic finite automaton (an NFA for short). Letrbe a regular expression and letMbe a Thompson automaton forr. We first introduce a labeled Thompson automaton defined
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::34536e9dc8d5053a59b022635620c720
https://soar-ir.repo.nii.ac.jp/records/2001210
https://soar-ir.repo.nii.ac.jp/records/2001210
Autor:
Oscar H. Ibarra, Ian McQuillan
We look at nondeterministic finite automata augmented with multiple reversal-bounded counters where, during an accepting computation, the behavior of the counters is specified by some fixed pattern. These patterns can serve as a useful "bridge" to ot
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::d7b4837c969a0a6ff65ba8cf3ba39e13
http://arxiv.org/abs/2212.03791
http://arxiv.org/abs/2212.03791
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.
Publikováno v:
ACM Transactions on Embedded Computing Systems. 20:1-26
We present an active learning algorithm named NRTALearning for nondeterministic real-time automata (NRTAs). Real-time automata (RTAs) are a subclass of timed automata with only one clock which resets at each transition. First, we prove the correspond
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::5d5e9645fbb83fc5206aae4c5d2fd2f0
https://doi.org/10.1145/3477030
https://doi.org/10.1145/3477030
Publikováno v:
Annals of Mathematics and Artificial Intelligence. 90:93-105
Let $NFA_b(q)$ denote the set of languages accepted by nondeterministic finite automata with $q$ states over an alphabet with $b$ letters. Let $B_n$ denote the set of words of length $n$. We give a quadratic lower bound on the VC dimension of \[ NFA_
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::ca21aaed7df83b4012370f944e8030d9
https://doi.org/10.1007/s10472-021-09769-9
https://doi.org/10.1007/s10472-021-09769-9
Autor:
Henning Bordihn, Markus Holzer
Publikováno v:
Acta Informatica. 58:301-318
We introduce a new measure of descriptional complexity on finite automata, called the number of active states. Roughly speaking, the number of active states of an automaton A on input w counts the number of different states visited during the most ec
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::c936e224a96d03d46f412b53905e5f2e
https://doi.org/10.1007/s00236-021-00397-8
https://doi.org/10.1007/s00236-021-00397-8
Publikováno v:
Theoretical Computer Science. 870:29-52
In this paper, we propose an architecture of oritatami systems, a mathematical model of RNA cotranscriptional folding, with which one can simulate an arbitrary nondeterministic finite automaton (NFA) in a unified manner. The oritatami system is known
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::0458c67f5953bcdde08852d4aa8176a6
https://doi.org/10.1016/j.tcs.2020.12.014
https://doi.org/10.1016/j.tcs.2020.12.014
Autor:
Sang-Ki Ko, Yo-Sub Han
Publikováno v:
International Journal of Foundations of Computer Science. 32:531-550
We study the NFA reductions by invariant equivalences and preorders. It is well-known that the NFA minimization problem is PSPACE-complete. Therefore, there have been many approaches to reduce the size of NFAs in low polynomial time by computing inva
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::49a134938b52dde2ce49e46400a9ed9f
https://doi.org/10.1142/s0129054121410069
https://doi.org/10.1142/s0129054121410069
Publikováno v:
Theoretical Computer Science. 862:144-154
The Closest Substring problem asks whether there exists a consensus string w of given length l such that each string in a set of strings L has a substring whose edit distance is at most r (called the radius) from w. The Closest Substring problem has
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::4e193f5dbeb05dddcd43e6d902a548da
https://doi.org/10.1016/j.tcs.2020.09.005
https://doi.org/10.1016/j.tcs.2020.09.005
Publikováno v:
International Journal of Approximate Reasoning. 129:20-40
Automata theory based on quantum logic has been established by Ying. Nondeterministic fuzzy finite automata theory has been proposed by Cao, and further generalized by Pan et al. In this paper, we propose the notion of nondeterministic finite automat
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::bafa68878f86cdce3e6a7f2c99082391
https://doi.org/10.1016/j.ijar.2020.11.002
https://doi.org/10.1016/j.ijar.2020.11.002