Loughborough University
Browse
FreydenbergerSchmid.pdf (589.04 kB)

Deterministic regular expressions with back-references

Download (589.04 kB)
conference contribution
posted on 2017-03-10, 11:11 authored by Dominik FreydenbergerDominik Freydenberger, Markus L. Schmid
Most 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 Science

Citation

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 Informatics

Version

  • 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-11

Publication date

2017

Notes

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-8969

Book series

Schloss Dagstuhl – Leibniz Center for Informatics;66

Language

  • en

Location

Hanover, Germany

Usage metrics

    Loughborough Publications

    Licence

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC