Deterministic regular expressions with back-references
conference contribution
posted on 2017-03-10, 11:11 authored by Dominik FreydenbergerDominik Freydenberger, Markus L. SchmidMost modern libraries for regular expression matching allow back-references (i. e., repetition
operators) that substantially increase expressive power, but also lead to intractability. In order
to find a better balance between expressiveness and tractability, we combine these with the notion
of determinism for regular expressions used in XML DTDs and XML Schema. This includes the
definition of a suitable automaton model, and a generalization of the Glushkov construction.
History
School
- Science
Department
- Computer Science
Published in
34th International Symposium on Theoretical Aspects of Computer ScienceCitation
FREYDENBERGER, D.D. and SCHMID, M.L., 2017. Deterministic regular expressions with back-references. Presented at the 34th International Symposium on Theoretical Aspects of Computer Science (STACS 2017), Hanover, Germany, Mar 8-11th.Publisher
Schloss Dagstuhl – Leibniz Center for InformaticsVersion
- VoR (Version of Record)
Publisher statement
This work is made available according to the conditions of the Creative Commons Attribution 4.0 International (CC BY 4.0) licence. Full details of this licence are available at: http://creativecommons.org/licenses/ by/4.0/Acceptance date
2016-12-11Publication date
2017Notes
This is an Open Access Article. It is published by Schloss Dagstuhl under the Creative Commons Attribution 4.0 Unported Licence (CC BY). Full details of this licence are available at: http://creativecommons.org/licenses/by/4.0/ISSN
1868-8969Publisher version
Book series
Schloss Dagstuhl – Leibniz Center for Informatics;66Language
- en
