Language operations with regular expressions of polynomial size

DOI10.1016/j.tcs.2009.04.009zbMath1176.68105WikidataQ54152565 ScholiaQ54152565MaRDI QIDQ2271463

Markus Holzer, Hermann Gruber

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

derivatives; regular expressions; cyclic shift; language quotient; circular shift

Mathematics Subject Classification ID

68Q45: Formal languages and automata

Related Items

The Size-Cost of Boolean Operations on Constant Height Deterministic Pushdown Automata, Further Remarks on the Operational Nonterminal Complexity, The size-cost of Boolean operations on constant height deterministic pushdown automata, Two double-exponential gaps for automata with a limited pushdown, Operational complexity and right linear grammars, Descriptional complexity of regular languages, On minimizing regular expressions without Kleene star, A logic for document spanners, Boolean language operations on nondeterministic automata with a pushdown of constant height, THE COMPLEXITY OF REGULAR(-LIKE) EXPRESSIONS, Tight Bounds on the Descriptional Complexity of Regular Expressions

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• From regular expressions to deterministic automata
• Local languages and the Berry-Sethi algorithm
• Intersection and union of regular languages and state complexity
• Regular expression for a language without empty word
• Follow automata.
• Canonical derivatives, partial derivatives and finite automaton constructions.
• General properties of star height of regular events
• GENERATING ALL CIRCULAR SHIFTS BY CONTEXT-FREE GRAMMARS IN GREIBACH NORMAL FORM
• State complexity of cyclic shift
• Finite Automata, Digraph Connectivity, and Regular Expression Size
• On the Hardness of Determining Small NFA’s and of Proving Lower Bounds on Their Sizes
• Finding Lower Bounds for Nondeterministic State Complexity Is Hard
• On the State Complexity of Scattered Substrings and Superstrings
• Optimal Lower Bounds on Regular Expression Size Using Communication Complexity
• Derivatives of Regular Expressions
• More on the Size of Higman-Haines Sets: Effective Constructions