Biclique coverings, rectifier networks and the cost of $\varepsilon$-removal

Autor:	Iván, Szabolcs, Lelkes, Ádám Dániel, Nagy-György, Judit, Szörényi, Balázs, Turán, György
Rok vydání:	2014
Předmět:	Computer Science - Formal Languages and Automata Theory Computer Science - Discrete Mathematics 68R10 G.2.2 F.1.1
Druh dokumentu:	Working Paper
Popis:	We relate two complexity notions of bipartite graphs: the minimal weight biclique covering number $\mathrm{Cov}(G)$ and the minimal rectifier network size $\mathrm{Rect}(G)$ of a bipartite graph $G$. We show that there exist graphs with $\mathrm{Cov}(G)\geq \mathrm{Rect}(G)^{3/2-\epsilon}$. As a corollary, we establish that there exist nondeterministic finite automata (NFAs) with $\varepsilon$-transitions, having $n$ transitions total such that the smallest equivalent $\varepsilon$-free NFA has $\Omega(n^{3/2-\epsilon})$ transitions. We also formulate a version of previous bounds for the weighted set cover problem and discuss its connections to giving upper bounds for the possible blow-up. Comment: 12 pages, to appear in proceedings of DCFS 2014: 16th International Conference on Descriptional Complexity of Finite-State Systems
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/1406.0017 Zobrazit plný text záznamu View this record from Arxiv