DROPS

Document

DOI: 10.4230/LIPIcs.MFCS.2020.30

Randomization in Non-Uniform Finite Automata

Authors: Pavol Ďuriš, Rastislav Královič, Richard Královič, Dana Pardubská, Martin Pašen, and Peter Rossmanith

Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)

Abstract

The non-uniform version of Turing machines with an extra advice input tape that depends on the length of the input but not the input itself is a well-studied model in complexity theory. We investigate the same notion of non-uniformity in weaker models, namely one-way finite automata. In particular, we are interested in the power of two-sided bounded-error randomization, and how it compares to determinism and non-determinism. We show that for unlimited advice, randomization is strictly stronger than determinism, and strictly weaker than non-determinism. However, when the advice is restricted to polynomial length, the landscape changes: the expressive power of determinism and randomization does not change, but the power of non-determinism is reduced to the extent that it becomes incomparable with randomization.

Cite as

Pavol Ďuriš, Rastislav Královič, Richard Královič, Dana Pardubská, Martin Pašen, and Peter Rossmanith. Randomization in Non-Uniform Finite Automata. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 30:1-30:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{duris_et_al:LIPIcs.MFCS.2020.30,
  author =	{\v{D}uri\v{s}, Pavol and Kr\'{a}lovi\v{c}, Rastislav and Kr\'{a}lovi\v{c}, Richard and Pardubsk\'{a}, Dana and Pa\v{s}en, Martin and Rossmanith, Peter},
  title =	{{Randomization in Non-Uniform Finite Automata}},
  booktitle =	{45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
  pages =	{30:1--30:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-159-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{170},
  editor =	{Esparza, Javier and Kr\'{a}l', Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.30},
  URN =		{urn:nbn:de:0030-drops-126987},
  doi =		{10.4230/LIPIcs.MFCS.2020.30},
  annote =	{Keywords: finite automata, non-uniform computation, randomization}
}

Document

DOI: 10.4230/LIPIcs.OPODIS.2017.14

Treasure Hunt with Barely Communicating Agents

Authors: Stefan Dobrev, Rastislav Královic, and Dana Pardubská

Published in: LIPIcs, Volume 95, 21st International Conference on Principles of Distributed Systems (OPODIS 2017)

Abstract

We consider the problem of fault-tolerant parallel exhaustive search, a.k.a. “Treasure Hunt”, introduced by Fraigniaud, Korman and Rodeh in [13]: Imagine an infinite list of “boxes”, one of which contains a “treasure”. The ordering of the boxes reflects the importance of finding the treasure in a given box. There are k agents, whose goal is to locate the treasure in the least amount of time. The system is synchronous; at every step, an agent can ”open” a box and see whether the treasure is there. The hunt finishes when the first agent locates the treasure. The original paper [13] considers non-cooperating randomized agents, out of which at most f can fail, with the failure pattern determined by an adversary. In this paper, we consider deterministic agents and investigate two failure models: The failing-agents model from [13] and a “black hole” model: At most f boxes contain “black holes”, placed by the adversary. When an agent opens a box containing a black hole, the agent disappears without an observable trace. The crucial distinction, however, is that we consider “barely communicating” or “indirectly weakly communicating” agents: When an agent opens a box, it can tell whether the box has been previously opened. There are no other means of direct or indirect communication between the agents. We show that adding even such weak means of communication has very strong impact on the solvability and complexity of the Treasure Hunt problem. In particular, in the failing agents model it allows the agents to be 1-competitive w.r.t. an optimal algorithm which does not know the location of the treasure, but is instantly notified of agent failures. In the black holes model (where there is no deterministic solution for non-communicating agents even in the presence of a single black hole) we show a lower bound of 2f + 1 and an upper bound of 4f + 1 for the number of agents needed to solve Treasure Hunt in presence of up to f black holes, as well as partial results about the hunt time in the presence of few black holes.

Cite as

Stefan Dobrev, Rastislav Královic, and Dana Pardubská. Treasure Hunt with Barely Communicating Agents. In 21st International Conference on Principles of Distributed Systems (OPODIS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 95, pp. 14:1-14:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{dobrev_et_al:LIPIcs.OPODIS.2017.14,
  author =	{Dobrev, Stefan and Kr\'{a}lovic, Rastislav and Pardubsk\'{a}, Dana},
  title =	{{Treasure Hunt with Barely Communicating Agents}},
  booktitle =	{21st International Conference on Principles of Distributed Systems (OPODIS 2017)},
  pages =	{14:1--14:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-061-3},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{95},
  editor =	{Aspnes, James and Bessani, Alysson and Felber, Pascal and Leit\~{a}o, Jo\~{a}o},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2017.14},
  URN =		{urn:nbn:de:0030-drops-86346},
  doi =		{10.4230/LIPIcs.OPODIS.2017.14},
  annote =	{Keywords: parallel exhaustive search, treasure hunt, fault-tolerant search, weak coordination, black holes}
}

Search Results

Documents authored by Pardubská, Dana

Randomization in Non-Uniform Finite Automata

Abstract

Cite as

Treasure Hunt with Barely Communicating Agents

Abstract

Cite as

Thanks for your feedback!

Could not send message