Regular expression length via arithmetic formula complexity

DOI10.1016/j.jcss.2021.10.004OpenAlexW3126609787WikidataQ113871639 ScholiaQ113871639MaRDI QIDQ5918469

Hannes Seiwert, Ehud Cseresnyes

Publication date: 31 January 2022

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

Full work available at URL: https://arxiv.org/abs/2012.15617

zbMATH Keywords

lower boundformal languagedescriptional complexityregular expressionarithmetic circuit complexitymonotone arithmetic formula

Mathematics Subject Classification ID

Computer science (68-XX)

Uses Software

• GitHub
• lowerbounds-survey

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Lower bounds for monotone counting circuits
• Lower bounds for tropical circuits and dynamic programs
• Boolean function complexity. Advances and frontiers.
• Homogeneous formulas and symmetric polynomials
• A lower bound technique for the size of nondeterministic finite automata
• More concise representation of regular languages by automata and regular expressions
• Intersection and union of regular languages and state complexity
• Complexity measures for regular expressions
• A direct version of Shamir and Snir's lower bounds on monotone circuit depth
• Monotone separation of logarithmic space from logarithmic depth
• Lower bounds for context-free grammars
• Operational complexity of straight line programs for regular languages
• The Chung-Feller theorem revisited
• Method of determining lower bounds for the complexity of \(\Pi\)-circuits
• From Finite Automata to Regular Expressions and Back — A Summary on Descriptional Complexity
• Tropical Complexity, Sidon Sets, and Dynamic Programming
• THE COMPLEXITY OF REGULAR(-LIKE) EXPRESSIONS
• Succinctness of the Complement and Intersection of Regular Expressions
• Arithmetic Circuits: A survey of recent results and open questions
• Asymptotic analysis of a random walk on a hypercube with many dimensions
• Short monotone formulae for the majority function
• Finite Automata, Digraph Connectivity, and Regular Expression Size
• Tight Bounds on the Descriptional Complexity of Regular Expressions
• On the depth complexity of formulas
• Some Exact Complexity Results for Straight-Line Computations over Semirings
• Star Height via Games
• Separating monotone VP and VNP
• Optimal Lower Bounds on Regular Expression Size Using Communication Complexity
• NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES
• Non-commutative circuits and the sum-of-squares problem
• Regular expression length via arithmetic formula complexity

This page was built for publication: Regular expression length via arithmetic formula complexity