Geodesic
Inkdots as advice for finite automata
Discrete mathematics & theoretical computer science, Tome 19 (2017-2018) no. 3.

Voir la notice de l'article provenant de la source Episciences

We examine inkdots placed on the input string as a way of providing advice to finite automata, and establish the relations between this model and the previously studied models of advised finite automata. The existence of an infinite hierarchy of classes of languages that can be recognized with the help of increasing numbers of inkdots as advice is shown. The effects of different forms of advice on the succinctness of the advised machines are examined. We also study randomly placed inkdots as advice to probabilistic finite automata, and demonstrate the superiority of this model over its deterministic version. Even very slowly growing amounts of space can become a resource of meaningful use if the underlying advised model is extended with access to secondary memory, while it is famously known that such small amounts of space are not useful for unadvised one-way Turing machines. 
@article{DMTCS_2017_19_3_a4,
     author = {K\"u\c{c}\"uk, U\u{g}ur and Say, A. C. Cem and Yakary{\i}lmaz, Abuzer},
     title = {Inkdots as advice for finite automata},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {19},
     number = {3},
     year = {2017-2018},
     doi = {10.23638/DMTCS-19-3-1},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-19-3-1/}
}
TY  - JOUR
AU  - Küçük, Uğur
AU  - Say, A. C. Cem
AU  - Yakaryılmaz, Abuzer
TI  - Inkdots as advice for finite automata
JO  - Discrete mathematics & theoretical computer science
PY  - 2017-2018
VL  - 19
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-19-3-1/
DO  - 10.23638/DMTCS-19-3-1
LA  - en
ID  - DMTCS_2017_19_3_a4
ER  - 
%0 Journal Article
%A Küçük, Uğur
%A Say, A. C. Cem
%A Yakaryılmaz, Abuzer
%T Inkdots as advice for finite automata
%J Discrete mathematics & theoretical computer science
%D 2017-2018
%V 19
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-19-3-1/
%R 10.23638/DMTCS-19-3-1
%G en
%F DMTCS_2017_19_3_a4
Küçük, Uğur; Say, A. C. Cem; Yakaryılmaz, Abuzer. Inkdots as advice for finite automata. Discrete mathematics & theoretical computer science, Tome 19 (2017-2018) no. 3. doi : 10.23638/DMTCS-19-3-1. http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-19-3-1/

Cité par Sources :