License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2013.327
URN: urn:nbn:de:0030-drops-43838
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2013/4383/
Go to the corresponding LIPIcs Volume Portal

Löding, Christof ; Repke, Stefan

Decidability Results on the Existence of Lookahead Delegators for NFA

pdf-format:
24.pdf (0.5 MB)

Abstract

In this paper, we study lookahead delegators for nondeterministic finite automata (NFA), which are functions that deterministically choose transitions by additionally using a bounded lookahead on the input word. Of course, the delegator has to lead to an accepting state for each word that is accepted by the NFA. In the special case where no lookahead is allowed, a delegator coincides with a deterministic transition function that preserves the language.

Typical decision problems are to decide whether a delegator with a given fixed lookahead exists, or whether a delegator with some bounded lookahead exists for a given NFA. In a paper of Ravikumar and Santean from 2007, the complexity and decidability of these questions have been tackled, mainly for the case of unambiguous NFA. In this paper, we revisit the subject and provide results for the case of general NFA. First, we correct a complexity result from the above paper by showing that the existence of delegators with fixed lookahead can be decided in time polynomial in the number of states. We use two player games on graphs as a tool to obtain the result.
As second contribution, we show that the problem becomes PSPACE-complete if the bound on the lookahead is a part of the input.
The third result provides a bound on the maximal required amount of lookahead. We use this to show that the (previously open) problem of deciding the existence of a bounded lookahead delegator is also PSPACE-complete.

BibTeX - Entry

@InProceedings{lding_et_al:LIPIcs:2013:4383,
  author =	{Christof L{\"o}ding and Stefan Repke},
  title =	{{Decidability Results on the Existence of Lookahead Delegators for NFA}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)},
  pages =	{327--338},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-64-4},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{24},
  editor =	{Anil Seth and Nisheeth K. Vishnoi},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2013/4383},
  URN =		{urn:nbn:de:0030-drops-43838},
  doi =		{10.4230/LIPIcs.FSTTCS.2013.327},
  annote =	{Keywords: Automata, Lookahead Delegators, Safety Games}
}

Keywords: Automata, Lookahead Delegators, Safety Games
Collection: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)
Issue Date: 2013
Date of publication: 10.12.2013

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI