Language operations with regular expressions of polynomial size

DOI10.1016/J.TCS.2009.04.009MaRDI QIDQ2271463zbMATH OpenOpenAlexWikidataFDO

Authors Hermann Gruber, Markus Holzer

Publication date 7 August 2009

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2009.04.009

zbMATH Keywords

derivativesregular expressionslanguage quotientcyclic shiftcircular shift

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• Descriptional complexity of deterministic regular expressions
• The complexity of regular(-like) expressions
• The complexity of regular(-like) expressions
• Quotient complexity of regular languages
• Towards a theory of complexity of regular languages

Cites work

• scientific article; zbMATH DE number 3505007 (Why is no real title available?)
• scientific article; zbMATH DE number 1502109 (Why is no real title available?)
• scientific article; zbMATH DE number 1747444 (Why is no real title available?)
• scientific article; zbMATH DE number 3311755 (Why is no real title available?)
• Canonical derivatives, partial derivatives and finite automaton constructions.
• Derivatives of Regular Expressions
• Finding Lower Bounds for Nondeterministic State Complexity Is Hard
• Finite Automata, Digraph Connectivity, and Regular Expression Size
• Follow automata.
• From regular expressions to deterministic automata
• GENERATING ALL CIRCULAR SHIFTS BY CONTEXT-FREE GRAMMARS IN GREIBACH NORMAL FORM
• General properties of star height of regular events
• Intersection and union of regular languages and state complexity
• Local languages and the Berry-Sethi algorithm
• More on the Size of Higman-Haines Sets: Effective Constructions
• On the Hardness of Determining Small NFA’s and of Proving Lower Bounds on Their Sizes
• On the state complexity of scattered substrings and superstrings
• Optimal Lower Bounds on Regular Expression Size Using Communication Complexity
• Regular expression for a language without empty word
• Regular expressions: new results and open problems
• State complexity of cyclic shift
• Succinctness of the complement and intersection of regular expressions

Cited in

(15)

• On minimizing regular expressions without Kleene star
• Regularity of a dynamic neighborhood of a regular language
• Tight Bounds on the Descriptional Complexity of Regular Expressions
• Algorithms for checking intersection non-emptiness of regular expressions
• Boolean language operations on nondeterministic automata with a pushdown of constant height
• Chop operations and expressions: descriptional complexity considerations
• Operational complexity and right linear grammars
• The size-cost of Boolean operations on constant height deterministic pushdown automata
• The size-cost of Boolean operations on constant height deterministic pushdown automata
• A logic for document spanners
• Further Remarks on the Operational Nonterminal Complexity
• The complexity of regular(-like) expressions
• Descriptional complexity of regular languages
• Two double-exponential gaps for automata with a limited pushdown
• Closure properties and descriptional complexity of deterministic regular expressions

This page was built for publication: Language operations with regular expressions of polynomial size

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