A FORMAL STUDY OF PRACTICAL REGULAR EXPRESSIONS

DOI10.1142/S012905410300214XzbMATH Open1101.68443OpenAlexW2083735143WikidataQ63112201 ScholiaQ63112201MaRDI QIDQ5696950FDOQ5696950

Authors: Kai Salomaa, C. Câmpeanu, Sheng Yu 

Publication date: 19 October 2005

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s012905410300214x

Recommendations

• scientific article; zbMATH DE number 1962769
• Extended Regular Expressions: Succinctness and Decidability
• On the intersection of regex languages with regular languages
• Extended regular expressions: succinctness and decidability
• Pattern expressions and pattern automata

zbMATH Keywords

programming languagesformal languagesregular expressionsregexextended regex

Mathematics Subject Classification ID

Theory of programming languages (68N15) Formal languages and automata (68Q45)

Cites Work

• Title not available (Why is that?)
• Translating regular expressions into small \(\epsilon\)-free nondeterministic finite automata
• Shuffle on trajectories: Syntactic constraints
• Title not available (Why is that?)

Cited In (44)

• Characterising REGEX languages by regular languages equipped with factor-referencing
• Synchronized regular expressions
• Document spanners: a formal approach to information extraction
• Pattern matching with variables: a multivariate complexity analysis
• Title not available (Why is that?)
• Inferring descriptive generalisations of formal languages
• Title not available (Why is that?)
• Regular languages with variables on graphs
• Bad News on Decision Problems for Patterns
• Patterns with bounded treewidth
• On the semantics of regular expression parsing in the wild
• On minimizing regular expressions without Kleene star
• Synchronized regular expressions
• On the parameterised complexity of string morphism problems
• On the closure of pattern expressions languages under intersection with regular languages
• Document spanners: from expressive power to decision problems
• A benchmark production tool for regular expressions
• On Extended Regular Expressions
• Matching patterns with variables under Simon's congruence
• Inclusion problems for patterns with a bounded number of variables
• Generating all minimal Petri net unsolvable binary words
• Pumping lemmas can be ``harmful
• Title not available (Why is that?)
• How to settle the ReDoS problem: back to the classical automata theory
• Regular and context-free pattern languages over small alphabets
• On the semantics of regular expression parsing in the wild
• On the language equivalence of NE star-patterns
• A polynomial time match test for large classes of extended regular expressions
• Annotated regular expressions and input-driven languages
• Bad news on decision problems for patterns
• A note on the complexity of matching patterns with variables
• Extended regular expressions: succinctness and decidability
• Inside the class of REGEX languages
• Regular Expressions on Average and in the Long Run
• Re-examining regular expressions with backreferences
• On the undecidability and descriptional complexity of synchronized regular expressions
• Goodby to the kindhearted dragon Prof. Sheng Yu, 1950--2012
• Title not available (Why is that?)
• Title not available (Why is that?)
• Pattern expressions and pattern automata
• Expressiveness and static analysis of extended conjunctive regular path queries
• Deterministic regular expressions with back-references
• On the intersection of regex languages with regular languages
• Matching patterns with variables under edit distance

This page was built for publication: A FORMAL STUDY OF PRACTICAL REGULAR EXPRESSIONS

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5696950)