Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userExtension Complexity of Formal Languages
113
0
0.0
(
0
)
Added by
Hans Raj Tiwary
Publication date
2016
fields
Informatics Engineering
and research's language is
English
Authors
Hans Raj Tiwary
Ask ChatGPT about the research
No Arabic 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.
rate research
Read More
We first show that given a $k_1$-letter quantum finite automata $mathcal{A}_1$ and a $k_2$-letter quantum finite automata $mathcal{A}_2$ over the same input alphabet $Sigma$, they are equivalent if and only if they are $(n_1^2+n_2^2-1)|Sigma|^{k-1}+k$-equivalent where $n_1$, $i=1,2$, are the numbers of state in $mathcal{A}_i$ respectively, and $k=max{k_1,k_2}$. By applying a method, due to the author, used to deal with the equivalence problem of {it measure many one-way quantum finite automata}, we also show that a $k_1$-letter measure many quantum finite automaton $mathcal{A}_1$ and a $k_2$-letter measure many quantum finite automaton $mathcal{A}_2$ are equivalent if and only if they are $(n_1^2+n_2^2-1)|Sigma|^{k-1}+k$-equivalent where $n_i$, $i=1,2$, are the numbers of state in $mathcal{A}_i$ respectively, and $k=max{k_1,k_2}$. Next, we study the language equivalence problem of those two kinds of quantum finite automata. We show that for $k$-letter quantum finite automata, the non-strict cut-point language equivalence problem is undecidable, i.e., it is undecidable whether $L_{geqlambda}(mathcal{A}_1)=L_{geqlambda}(mathcal{A}_2)$ where $0<lambdaleq 1$ and $mathcal{A}_i$ are $k_i$-letter quantum finite automata. Further, we show that both strict and non-strict cut-point language equivalence problem for $k$-letter measure many quantum finite automata are undecidable. The direct consequences of the above outcomes are summarized in the paper. Finally, we comment on existing proofs about the minimization problem of one way quantum finite automata not only because we have been showing great interest in this kind of problem, which is very important in classical automata theory, but also due to that the problem itself, personally, is a challenge. This problem actually remains open.
We investigate the internal representations that a recurrent neural network (RNN) uses while learning to recognize a regular formal language. Specifically, we train a RNN on positive and negative examples from a regular language, and ask if there is a simple decoding function that maps states of this RNN to states of the minimal deterministic finite automaton (MDFA) for the language. Our experiments show that such a decoding function indeed exists, and that it maps states of the RNN not to MDFA states, but to states of an {em abstraction} obtained by clustering small sets of MDFA states into superstates. A qualitative analysis reveals that the abstraction often has a simple interpretation. Overall, the results suggest a strong structural relationship between internal representations used by RNNs and finite automata, and explain the well-known ability of RNNs to recognize formal grammatical structure.
In this paper we propose a generalization of the extension complexity of a polyhedron $Q$. On the one hand it is general enough so that all problems in $P$ can be formulated as linear programs with polynomial size extension complexity. On the other hand it still allows non-polynomial lower bounds to be proved for $NP$-hard problems independently of whether or not $P=NP$. The generalization, called $H$-free extension complexity, allows for a set of valid inequalities $H$ to be excluded in computing the extension complexity of $Q$. We give results on the $H$-free extension complexity of hard matching problems (when $H$ are the odd set inequalities) and the traveling salesman problem (when $H$ are the subtour elimination constraints).
Equality and disjointness are two of the most studied problems in communication complexity. They have been studied for both classical and also quantum communication and for various models and modes of communication. Buhrman et al. [Buh98] proved that the exact quantum communication complexity for a promise version of the equality problem is ${bf O}(log {n})$ while the classical deterministic communication complexity is $n+1$ for two-way communication, which was the first impressively large (exponential) gap between quantum and classical (deterministic and probabilistic) communication complexity. If an error is tolerated, both quantum and probabilistic communication complexities for equality are ${bf O}(log {n})$. However, even if an error is tolerated, the gaps between quantum (probabilistic) and deterministic complexity are not larger than quadratic for the disjointness problem. It is therefore interesting to ask whether there are some promis
The question if a given partial solution to a problem can be extended reasonably occurs in many algorithmic approaches for optimization problems. For instance, when enumerating minimal dominating sets of a graph $G=(V,E)$, one usually arrives at the problem to decide for a vertex set $U subseteq V$, if there exists a textit{minimal} dominating set $S$ with $Usubseteq S$. We propose a general, partial-order based formulation of such extension problems and study a number of specific problems which can be expressed in this framework. Possibly contradicting intuition, these problems tend to be NP-hard, even for problems where the underlying optimisation problem can be solved in polynomial time. This raises the question of how fixing a partial solution causes this increase in difficulty. In this regard, we study the parameterised complexity of extension problems with respect to parameters related to the partial solution, as well as the optimality of simple exact algorithms under the Exponential-Time Hypothesis. All complexity considerations are also carried out in very restricted scenarios, be it degree restrictions or topological restrictions (planarity) for graph problems or the size of the given partition for the considered extension variant of Bin Packing.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
