Regular expression length via arithmetic formula complexity
From MaRDI portal
Recommendations
- Regular expression length via arithmetic formula complexity
- Optimal regular expressions for permutations
- Optimal Lower Bounds on Regular Expression Size Using Communication Complexity
- On the complexity of realization of finite languages by formulas
- Tight Bounds on the Descriptional Complexity of Regular Expressions
Cites work
- A direct version of Shamir and Snir's lower bounds on monotone circuit depth
- A lower bound technique for the size of nondeterministic finite automata
- Arithmetic circuits: a survey of recent results and open questions
- Asymptotic analysis of a random walk on a hypercube with many dimensions
- Boolean function complexity. Advances and frontiers.
- Complexity measures for regular expressions
- Finite Automata, Digraph Connectivity, and Regular Expression Size
- From finite automata to regular expressions and back -- a summary on descriptional complexity
- Homogeneous formulas and symmetric polynomials
- scientific article; zbMATH DE number 3577144 (Why is no real title available?)
- scientific article; zbMATH DE number 1517989 (Why is no real title available?)
- scientific article; zbMATH DE number 2201362 (Why is no real title available?)
- Intersection and union of regular languages and state complexity
- Lower bounds for context-free grammars
- Lower bounds for monotone counting circuits
- Lower bounds for tropical circuits and dynamic programs
- Method of determining lower bounds for the complexity of \(\Pi\)-circuits
- Monotone separation of logarithmic space from logarithmic depth
- More concise representation of regular languages by automata and regular expressions
- Non-commutative circuits and the sum-of-squares problem
- NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES
- On the depth complexity of formulas
- Operational complexity of straight line programs for regular languages
- Optimal Lower Bounds on Regular Expression Size Using Communication Complexity
- Optimal regular expressions for permutations
- Regular expression length via arithmetic formula complexity
- Separating monotone VP and VNP
- Short monotone formulae for the majority function
- Some Exact Complexity Results for Straight-Line Computations over Semirings
- Star height via games
- Succinctness of the Complement and Intersection of Regular Expressions
- The Chung-Feller theorem revisited
- The complexity of regular(-like) expressions
- Tight Bounds on the Descriptional Complexity of Regular Expressions
- Tropical complexity, Sidon sets, and dynamic programming
Cited in
(3)
This page was built for publication: Regular expression length via arithmetic formula complexity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5918469)
