Zobrazeno 1 - 10
of 546
pro vyhledávání: '"Ibarra, Oscar H."'
Autor:
Ibarra, Oscar H., McQuillan, Ian
There are many types of automata and grammar models that have been studied in the literature, and for these models, it is common to determine whether certain problems are decidable. One problem that has been difficult to answer throughout the history
Externí odkaz:
http://arxiv.org/abs/2405.08988
Autor:
Ibarra, Oscar H.1 ibarra@cs.ucsb.edu, McQuillan, Ian2 mcquillan@cs.usask.ca
Publikováno v:
Computer Science Journal of Moldova. 2024, Vol. 32 Issue 3, p389-411. 23p.
Autor:
Ibarra, Oscar H., McQuillan, Ian
Publikováno v:
Theoretical Computer Science 799, 71--93 (2019)
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:
http://arxiv.org/abs/2212.03791
Autor:
Ibarra, Oscar H., McQuillan, Ian
Publikováno v:
Theoretical Computer Science 798, 23-39 (2019)
State grammars are context-free grammars where the productions have states associated with them, and a production can only be applied to a nonterminal if the current state matches the state in the production. Once states are added to grammars, it is
Externí odkaz:
http://arxiv.org/abs/2212.03992
Publikováno v:
Theoretical Computer Science 862, 97--118 (2021)
It is shown that for every language family that is a trio containing only semilinear languages, all bounded languages in it can be accepted by one-way deterministic reversal-bounded multicounter machines (DCM). This implies that for every semilinear
Externí odkaz:
http://arxiv.org/abs/2212.03359
Autor:
Ibarra, Oscar H., McQuillan, Ian
Publikováno v:
International Journal of Foundations of Computer Science, 31 (8), 1179-1198 (2020)
Techniques are developed for creating new and general language families of only semilinear languages, and for showing families only contain semilinear languages. It is shown that for language families L that are semilinear full trios, the smallest fu
Externí odkaz:
http://arxiv.org/abs/2212.01301
Autor:
Ibarra, Oscar H., McQuillan, Ian
Publikováno v:
International Journal of Foundations of Computer Science, 32 (5), 481-508, (2021)
We examine different generalizations of checking stack automata by allowing multiple input heads and multiple stacks, and characterize their computing power in terms of two-way multi-head finite automata and space-bounded Turing machines. For various
Externí odkaz:
http://arxiv.org/abs/2212.00897
Publikováno v:
International Journal of Foundations of Computer Science, 32 (6), 801--823 (2021)
This paper examines several measures of space complexity of variants of stack automata: non-erasing stack automata and checking stack automata. These measures capture the minimum stack size required to accept every word in the language of the automat
Externí odkaz:
http://arxiv.org/abs/2212.00891