Zobrazeno 1 - 10
of 118
pro vyhledávání: '"Linear bounded automaton"'
Autor:
Nadine Losert
Publikováno v:
Information and Computation. 256:185-195
We look at the question of join preservation for bounded Turing reducibilities r and r ′ such that r is stronger than r ′ . We say that join preservation holds for two reducibilities r and r ′ if every join in the computably enumerable (c.e.) r
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::17e52f2aa055a07f1e75d34b99522b2b
https://doi.org/10.1016/j.ic.2017.07.005
https://doi.org/10.1016/j.ic.2017.07.005
Autor:
Martin Kutrib, Matthias Wendlandt
Publikováno v:
Fundamenta Informaticae. 155:31-58
A k-limited automaton is a linear bounded automaton that may rewrite each tape square only in the first k visits, where \(k\ge 0\) is a fixed constant. It is known that these automata accept context-free languages only. We investigate deterministic k
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::e640121e8f02856b78236cec18fd94f3
https://doi.org/10.3233/fi-2017-1575
https://doi.org/10.3233/fi-2017-1575
Autor:
Ferran Cedo, Jan Okniński
Publikováno v:
Proceedings of the Edinburgh Mathematical Society. 60:31-38
We show that every finitely generated algebra that is a finitely generated module over a finitely generated commutative subalgebra is an automaton algebra in the sense of Ufnarovskii.
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::beab803f12caf4849a8dbb81f5b7c3df
https://doi.org/10.1017/s0013091516000134
https://doi.org/10.1017/s0013091516000134
Publikováno v:
Developments in Language Theory
Developments in Language Theory, pp.366-378, 2018, ⟨10.1007/978-3-319-98654-8_30⟩
Developments in Language Theory ISBN: 9783319986531
DLT
Developments in Language Theory, pp.366-378, 2018, ⟨10.1007/978-3-319-98654-8_30⟩
Developments in Language Theory ISBN: 9783319986531
DLT
It is well-known that one-tape Turing machines working in linear time are no more powerful than finite automata, namely they recognize exactly the class of regular languages. We study the costs, in terms of description sizes, of the conversion of non
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::bfe39aab88bfccff1750a009c9a86b49
https://hal.archives-ouvertes.fr/hal-02079083
https://hal.archives-ouvertes.fr/hal-02079083
Autor:
Prem Nath
Publikováno v:
International Journal of Computer Network and Information Security. 8:61-66
Linear-bounded automata (LBA) accept context-sensitive languages (CSLs) and CSLs are generated by context-sensitive grammars (CSGs). So, for every CSG/CSL there is a LBA. A CSG is converted into normal form like Kuroda normal form (KNF) and then corr
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::6be69adf6026afda0762f89be8474426
https://doi.org/10.5815/ijcnis.2016.01.08
https://doi.org/10.5815/ijcnis.2016.01.08
Publikováno v:
RAIRO - Theoretical Informatics and Applications. 48:505-539
We present a new model of a two-dimensional computing device called Sgraffito automaton . In general, the model is quite simple, which allows a clear design of computations. When restricted to one-dimensional inputs, that is, strings, the Sgraffito a
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::b009852f23df0ce224c03b15b8695037
https://doi.org/10.1051/ita/2014023
https://doi.org/10.1051/ita/2014023
Autor:
Gheorghe Paun, Oscar H. Ibarra
Publikováno v:
Theoretical Computer Science. 358(1):88-103
We give "syntactic" characterizations of context-sensitive languages (CSLs) in terms of some restricted models of symport/antiport P systems. These are the first such characterizations of CSLs in terms of P systems. In particular, we show the followi
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::9902e87f45151b86ef4843817e6042af
Autor:
Adam Woryna
Publikováno v:
Communications in Algebra. 42:1354-1361
We study profinite groups which are infinitely iterated wreath products W ∞ = …≀C n 2 ≀C n 1 of finite cyclic groups via combinatorial language of transducers. Namely, we provide a naturally defined automaton realization of the group W ∞ by
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::5ef63bad3563100d7f573bb804ec319a
https://doi.org/10.1080/00927872.2012.738749
https://doi.org/10.1080/00927872.2012.738749
Publikováno v:
Theoretical Computer Science. 417:66-73
The standard simulation of a nondeterministic Turing machine (NTM) by a deterministic one essentially searches a large bounded-degree graph whose size is exponential in the running time of the NTM. The graph is the natural one defined by the configur
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::e1f4462ea848013eb4ed4f562190a731
https://doi.org/10.1016/j.tcs.2011.05.018
https://doi.org/10.1016/j.tcs.2011.05.018
Autor:
Giovanni Pighizzini
Publikováno v:
Language and Automata Theory and Applications ISBN: 9783319299990
LATA
LATA
In 1965 Hennie proved that one-tape deterministic Turing machines working in linear time are equivalent to finite automata, namely they characterize regular languages. This result has been improved in different directions, by obtaining optimal lower
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::8bdfc1efaeaa47a4c7c68fa77ad88863
https://doi.org/10.1007/978-3-319-30000-9_3
https://doi.org/10.1007/978-3-319-30000-9_3