The inclusion problem for regular expressions

DOI10.1016/j.jcss.2011.12.003zbMath1250.68162WikidataQ59238607 ScholiaQ59238607MaRDI QIDQ1757837

Dag Hovland

Publication date: 6 November 2012

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2011.12.003

zbMATH Keywords

regular expressions; formal languages; inclusion; 1-unambiguity

Mathematics Subject Classification ID

68W40: Analysis of algorithms

68Q45: Formal languages and automata

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

Related Items

A theoretical framework for cardinality-based feature models: the semantics and computational aspects, A synchronous effects logic for temporal verification of pure Esterel, From Finite Automata to Regular Expressions and Back — A Summary on Descriptional Complexity

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Efficient asymmetric inclusion of regular expressions with interleaving and counting for XML type-checking
• Regular expressions into finite automata
• Linear Automaton Transformations
• THE ABSTRACT THEORY OF AUTOMATA
• The Inclusion Problem for Regular Expressions
• Rewriting regular inequalities
• Mathematical Foundations of Computer Science 2004
• Inclusion Test Algorithms for One-Unambiguous Regular Expressions
• Two Complete Axiom Systems for the Algebra of Regular Events
• Roots of Star Events
• Ambiguity in Graphs and Expressions
• Derivatives of Regular Expressions
• One-unambiguous regular languages