Abstract: In this article we undertake a study of extension complexity from the perspective of formal languages. We define a natural way to associate a family of polytopes with binary languages. This allows us to define the notion of extension complexity of formal languages. We prove several closure properties of languages admitting compact extended formulations. Furthermore, we give a sufficient machine characterization of compact languages. We demonstrate the utility of this machine characterization by obtaining upper bounds for polytopes for problems in nondeterministic logspace; lower bounds in streaming models; and upper bounds on extension complexities of several polytopes.
Recommendations
Cites work
- scientific article; zbMATH DE number 2089362 (Why is no real title available?)
- scientific article; zbMATH DE number 764212 (Why is no real title available?)
- Approximate Constraint Satisfaction Requires Large LP Relaxations
- Approximation Limits of Linear Programs (Beyond Hierarchies)
- Computational Complexity
- Disjunctive programming: Properties of the convex hull of feasible points
- Exponential lower bounds for polytopes in combinatorial optimization
- Extended formulations in combinatorial optimization
- Information-theoretic approximations of the nonnegative rank
- Languages Simultaneously Complete for One-Way and Two-Way Log-Tape Automata
- Lectures on Polytopes
- Lower bounds on the size of semidefinite programming relaxations
- On the existence of 0/1 polytopes with high semidefinite extension complexity
- Some \(0/1\) polytopes need exponential size extended formulations
- Some efficiently solvable problems over integer partition polytopes
- Streaming algorithms for language recognition problems
- The projected faces property and polyhedral relations
- Tutorials on emerging methodologies and applications in operations research. Selected papers presented at INFORMS 2004, Denver, CO, USA, October 24--27, 2004.
- Uncapacitated flow-based extended formulations
- Weak and strong one-way space complexity classes
Cited in
(4)
This page was built for publication: Extension complexity of formal languages
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q778518)
