TY - GEN
T1 - The complexity of SORE-definability problems
AU - Lu, Ping
AU - Wu, Zhilin
AU - Chen, Haiming
N1 - Publisher Copyright:
© Ping Lu, Zhilin Wu, and Haiming Chen; licensed under Creative Commons License CC-BY.
PY - 2017/11/1
Y1 - 2017/11/1
N2 - 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 SOREdefinability 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.
AB - 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 SOREdefinability 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.
KW - Complexity
KW - Definability
KW - Single occurrence regular expressions
UR - https://www.scopus.com/pages/publications/85038423519
U2 - 10.4230/LIPIcs.MFCS.2017.22
DO - 10.4230/LIPIcs.MFCS.2017.22
M3 - 会议稿件
AN - SCOPUS:85038423519
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 42nd International Symposium on Mathematical Foundations of Computer Science, MFCS 2017
A2 - Larsen, Kim G.
A2 - Raskin, Jean-Francois
A2 - Bodlaender, Hans L.
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 42nd International Symposium on Mathematical Foundations of Computer Science, MFCS 2017
Y2 - 21 August 2017 through 25 August 2017
ER -