Results 1 to 10 of about 551,541 (325)
Regular expression types for XML [PDF]
Proceedings of the fifth ACM SIGPLAN international conference on Functional programming, 2000 We propose regular expression types as a foundation for XML processing languages. Regular expression types are a natural generalization of Document Type Definitions (DTDs), describing structures in XML documents using regular expression operators (i.e., *, ?, |, etc.) and supporting a simple but powerful notion of
Haruo Hosoya +2 more
+12 more sources
Regular expression patterns [PDF]
Proceedings of the ninth ACM SIGPLAN international conference on Functional programming, 2004 We extend Haskell with regular expression patterns . Regular expression patterns provide means for matching and extracting data which goes well beyond ordinary pattern matching as found in Haskell. It has proven useful for string manipulation and for processing structured data such as XML.
Niklas Broberg +2 more
openalex +3 more sources
Exploring efficient grouping algorithms in regular expression matching. [PDF]
PLoS ONE, 2018 BACKGROUND:Regular expression matching (REM) is widely employed as the major tool for deep packet inspection (DPI) applications. For automatic processing, the regular expression patterns need to be converted to a deterministic finite automata (DFA ...
Chengcheng Xu, Jinshu Su, Shuhui Chen
doaj +2 more sources
Games for Succinctness of Regular Expressions [PDF]
EPTCS 346, 2021, pp. 258-272, 2021 We present a version of so called formula size games for regular expressions. These games characterize the equivalence of languages up to expressions of a given size. We use the regular expression size game to give a simple proof of a known non-elementary succinctness gap between first-order logic and regular expressions.
arxiv +7 more sources
The inclusion problem for regular expressions [PDF]
Journal of Computer and System Sciences, 2011 AbstractThis paper presents a polynomial-time algorithm for the inclusion problem for a large class of regular expressions. The algorithm is not based on construction of finite automata, and can therefore be faster than the lower bound implied by the Myhill–Nerode theorem.
Dag Hovland
openalex +8 more sources
Derivatives of approximate regular expressions [PDF]
Discrete Mathematics & Theoretical Computer Science, 2013 Automata, Logic and Semantics Our aim is to construct a finite automaton recognizing the set of words that are at a bounded distance from some word of a given regular language. We define new regular operators, the similarity operators, based on a generalization of the notion of distance and we introduce the family of regular expressions ...
Jean-Marc Champarnaud +2 more
openalex +11 more sources
Implication of regular expressions
Applied Mathematics Letters, 2011 AbstractIn this work we study the following implication problem for regular expressions: “Given a set of regular expressions R and a regular expression S, is it true that every string which matches the regular expressions in R also matches S?” The problem comes in two flavors: “non-disjoint” and “disjoint”. We show that both of them are PSPACE-complete.
Alex Thomo
openalex +3 more sources
Derivatives for Enhanced Regular Expressions [PDF]
arXiv, 2016 Regular languages are closed under a wealth of formal language operators. Incorporating such operators in regular expressions leads to concise language specifications, but the transformation of such enhanced regular expressions to finite automata becomes more involved.
arxiv +6 more sources
Parameterized Regular Expressions and their Languages [PDF]
Theoretical Computer Science, 2011 We study regular expressions that use variables, or parameters, which are interpreted as alphabet letters. We consider two classes of languages denoted by such expressions: under the possibility semantics, a word belongs to the language if it is denoted by some regular expression obtained by replacing variables with letters; under the certainly ...
Pablo Barceló +2 more
openalex +12 more sources
Regular Expressions with Lookahead [PDF]
JUCS - Journal of Universal Computer Science, 2021 This paper investigates regular expressions which in addition to the standard operators of union, concatenation, and Kleene star, have lookaheads. We show how to translate regular expressions with lookaheads (REwLA) to equivalent Boolean automata having at most 3 states more than the length of the REwLA.
Berglund,Martin +2 more
openaire +5 more sources