Uğur Küçük ; A. C. Cem Say ; Abuzer Yakaryılmaz - Inkdots as advice for finite automata

dmtcs:1286 - Discrete Mathematics & Theoretical Computer Science, September 26, 2017, Vol. 19 no. 3 - https://doi.org/10.23638/DMTCS-19-3-1
Inkdots as advice for finite automata

Authors: Uğur Küçük ; A. C. Cem Say ORCID-iD; Abuzer Yakaryılmaz

    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.


    Volume: Vol. 19 no. 3
    Section: Automata, Logic and Semantics
    Published on: September 26, 2017
    Accepted on: September 1, 2017
    Submitted on: December 5, 2016
    Keywords: Computer Science - Formal Languages and Automata Theory,Computer Science - Computational Complexity

    Consultation statistics

    This page has been seen 1011 times.
    This article's PDF has been downloaded 355 times.