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.MFCS.2017.22
URN: urn:nbn:de:0030-drops-80822
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/8082/
Go to the corresponding LIPIcs Volume Portal

Lu, Ping ; Wu, Zhilin ; Chen, Haiming

The Complexity of SORE-definability Problems

pdf-format:
LIPIcs-MFCS-2017-22.pdf (0.6 MB)

Abstract

Single occurrence regular expressions (SORE) are a special kind of deterministic regular expressions, which are extensively used in the schema languages DTD and XSD for XML documents. In this paper, with motivations from the simplification of XML schemas, we consider the SORE-definability problem: Given a regular expression, decide whether it has an equivalent SORE. We investigate extensively the complexity of the SORE-definability problem: We consider both (standard) regular expressions and regular expressions with counting, and distinguish between the alphabets of size at least two and unary alphabets. In all cases, we obtain tight complexity bounds. In addition, we consider another variant of this problem, the bounded SORE-definability problem, which is to decide, given a regular expression E and a number M (encoded in unary or binary), whether there is an SORE, which is equivalent to E on the set of words of length at most M. We show that in several cases, there is an exponential decrease in the complexity when switching from the SORE-definability problem to its bounded variant.

BibTeX - Entry

@InProceedings{lu_et_al:LIPIcs:2017:8082,
  author =	{Ping Lu and Zhilin Wu and Haiming Chen},
  title =	{{The Complexity of SORE-definability Problems}},
  booktitle =	{42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)},
  pages =	{22:1--22:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-046-0},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{83},
  editor =	{Kim G. Larsen and Hans L. Bodlaender and Jean-Francois Raskin},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/8082},
  URN =		{urn:nbn:de:0030-drops-80822},
  doi =		{10.4230/LIPIcs.MFCS.2017.22},
  annote =	{Keywords: Single occurrence regular expressions, Definability, Complexity}
}

Keywords: Single occurrence regular expressions, Definability, Complexity
Collection: 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)
Issue Date: 2017
Date of publication: 01.12.2017

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