1 Search Results for "Rampersad, Narad"


Document
Existential Length Universality

Authors: Paweł Gawrychowski, Martin Lange, Narad Rampersad, Jeffrey Shallit, and Marek Szykuła

Published in: LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)


Abstract
We study the following natural variation on the classical universality problem: given a language L(M) represented by M (e.g., a DFA/RE/NFA/PDA), does there exist an integer ? ≥ 0 such that Σ^? ⊆ L(M)? In the case of an NFA, we show that this problem is NEXPTIME-complete, and the smallest such ? can be doubly exponential in the number of states. This particular case was formulated as an open problem in 2009, and our solution uses a novel and involved construction. In the case of a PDA, we show that it is recursively unsolvable, while the smallest such ? is not bounded by any computable function of the number of states. In the case of a DFA, we show that the problem is NP-complete, and e^{√{n log n} (1+o(1))} is an asymptotically tight upper bound for the smallest such ?, where n is the number of states. Finally, we prove that in all these cases, the problem becomes computationally easier when the length ? is also given in binary in the input: it is polynomially solvable for a DFA, PSPACE-complete for an NFA, and co-NEXPTIME-complete for a PDA.

Cite as

Paweł Gawrychowski, Martin Lange, Narad Rampersad, Jeffrey Shallit, and Marek Szykuła. Existential Length Universality. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 16:1-16:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{gawrychowski_et_al:LIPIcs.STACS.2020.16,
  author =	{Gawrychowski, Pawe{\l} and Lange, Martin and Rampersad, Narad and Shallit, Jeffrey and Szyku{\l}a, Marek},
  title =	{{Existential Length Universality}},
  booktitle =	{37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)},
  pages =	{16:1--16:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-140-5},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{154},
  editor =	{Paul, Christophe and Bl\"{a}ser, Markus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.16},
  URN =		{urn:nbn:de:0030-drops-118770},
  doi =		{10.4230/LIPIcs.STACS.2020.16},
  annote =	{Keywords: decision problem, deterministic automaton, nondeterministic automaton, pushdown automaton, regular expression, regular language, universality}
}
  • Refine by Author
  • 1 Gawrychowski, Paweł
  • 1 Lange, Martin
  • 1 Rampersad, Narad
  • 1 Shallit, Jeffrey
  • 1 Szykuła, Marek

  • Refine by Classification
  • 1 Theory of computation → Formal languages and automata theory
  • 1 Theory of computation → Problems, reductions and completeness

  • Refine by Keyword
  • 1 decision problem
  • 1 deterministic automaton
  • 1 nondeterministic automaton
  • 1 pushdown automaton
  • 1 regular expression
  • Show More...

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2020

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail