12

This falls within the general topic of "grammar induction"; searching on that phrase will turn up tons of literature. See, e.g., Inducing a context free grammar, https://en.wikipedia.org/wiki/Grammar_induction, https://cstheory.stackexchange.com/q/27347/5038. For regular languages (rather than context-free ones), see also Is regex golf NP-Complete?, ...


9

If the number of strings is finite say set $S=\{s_1,s_2....s_m\}$ you can always come up with context free grammar that generates all those strings, let $A$ be a non terminal then the rule can be $A \to s_1|s_2|...s_n$. For a finite set of strings you can even come up with a finite state automata that accepts only those strings. So the case of finite set of ...


6

The answer by @YuvalFilmus is perfectly fine, and points you to the import notion of star height. But let me add a little bit more. We will show that languages of your form give a proper subset of the languages of star height one. But first, some musings what might come close to your form. General Regular Languages First, probably the closest form to yours ...


6

Since you have both lists, even if not both at the same time, your space cost is at least that of the longest, thus at least $n/2$. This corresponds to a $O(n)$ space complexity. So, unless you exclude it for some reason, it makes sense to use a bit array $M[1:n]$ to represent the set A by its characteristic function, i.e. $M[i]=0$ iff $i\notin A$, and $1$ ...


4

You need to say that (a) there are at least $n$ elements, and (b) there are at most $n$ elements. To express (a), $$ L_n := \exists x_1\dotsc \exists x_n\, \left( \bigwedge_{1\le i < j \le n} x_i\ne x_j \right). $$ To express (b), $$ M_n := \forall x_1\dotsc \forall x_{n+1}\, \left( \bigvee_{1\le i < j \le n+1}x_i = x_j\right). $$ So the sentence $L_n ...


4

Count instead $$ (a+b)^{n+m} - M_{m,n} = \sum_{i+j < m} a^i b (a+b)^{n+m-2-i-j} b a^j. $$ This leads to $$ \begin{align*} |M_{m,n}| &= 2^{n+m} - \sum_{i+j<m} 2^{n+m-2-i-j} \\ &= 2^{n+m} - \sum_{k=0}^{m-1} (k+1) 2^{n+m-2-k} \\ &= 2^{n+m} - 2^{n+m-2} (4-2^{-(m-2)}-m2^{-(m-1)}) \\ &= 2^{n+m} (1 - 1 + 2^{-m} + m2^{-m-1}) \\ &= (m+2) 2^{...


4

One useful fact about regular languages is that a union of finitely many regular languages is regular. From this it follows that all finite languages are regular: the language that recognizes a single constant string is always regular, and a finite language is a union of finitely many constant strings. (Proof: remember that regular languages are exactly ...


3

Interesting question. The right intuition should probably be along the guideline that two random subsets of cardinality $n$ drawn from some $cn$ elements for some constant $c$ differ from each other significantly with a probability very close to 1 and, hence, the weight of the minimum spanning tree of the graph $G$ should be $\mathcal\Theta(n^2)$ on average. ...


3

This has been asked before in various guises. The answer is very simple. If the continuum hypothesis holds, then here is pseudocode for a Turing machine accepting $L$: Accept if the input equals 1. If the continuum hypothesis doesn't hold, then here is pseudocode for a Turing machine accepting $L$: Accept if the input equals 0. In both cases, we have ...


3

What you are asking is akin to a search index. Indeed Finite State Transducers can be created and used to recognize text fed to them. For exameple, Lucene uses this algorithm: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.24.3698 For a practical use, check out this blog post by Andrew Gallant: Index 1,600,000,000 Keys with Automata and Rust In ...


3

There are lots of ways, so you need to impose additional criteria on the quality of the results. Examples: List: For each string $w$ in the language, have a rule $S \rightarrow w$. Let $S$ be the starting nonterminal. Done. Prefix tree: For each prefix $w$ of a string in the language, have the nonterminal $X_w$. For each string $w_1xw_2$ in the language, ...


3

I can give two candidate solutions for your specific situation. Approach #1: parity This only works if $k$ is odd. Notice that if $k$ is odd, the parity of $f(x)$ is the reverse of the parity of $x$. In other words, the xor of the bits of $f(x)$ is the complement of the xor of the bits of $x$. This suggests an encoding. Define $g(x)$ to choose between $...


3

Here is a concrete version of D.W.'s idea. Let $n$ be even, and consider the language $$ C_n = \{ w^2 : w \in \{0,1\}^n \}. $$ (Note that $C_n$ is a language rather than an automaton as in the original post.) The words in $\{0,1\}^n$ are all pairwise inequivalent, and so the DFA complexity of $C_n$ (the number of states in a minimal DFA for $C_n$), which we ...


3

It is perhaps more natural to consider the set $S$. Let us further consider the case $A = B = n$ and the set $S \cap [0,1] = \mathcal{F}_n$, the $n$th Farey sequence; if we know $|\mathcal{F}_n|$ and can solve the problem for $\mathcal{F}_n$ then we can also solve it for the entire $S$. The set $\mathcal{F}_n$ has size $\Theta(n^2)$. The fastest algorithm ...


3

You can certainly do better than $N(N-1)$: you can achieve $O(N \lg N)$ running time. Evaluate $f$ on every possible element of $x$, then sort the resulting values, and look at the gap between consecutive values. The smallest such gap is exactly the value of $\min |f(x_1)-f(x_2)|$. As Raphael says, without any information about $f$, it seems unlikely that ...


3

1) You need to take a look at this page. Remember that there is an implication to be proved true or false. 2) Consider the fact $L \subseteq L^{+}$ and apply it to the case $L^{+} = \emptyset$.


2

I don't see how to achieve what you want for arbitrary $k$. However, for small $k$, it is possible to solve this problem efficiently. In particular, it's possible to find the $k$th smallest element in $O(k \log k)$ time. Use a priority queue (min-heap). Initially, insert $1/B$ into the priority queue. Then, do the following $k$ times: Remove the ...


2

One way to formalize the core part of the Pumping lemma is this, using $L^{\geq k} = \{ w \in L \mid |w| \geq k\}$: If $L$ is regular, there exists $p \in \mathbb{N}$ so that $\qquad \displaystyle \forall w \in L^{\geq p}.\ \exists x,y,z \dots$ (*). For all finite $L$ and $p > \max \{ |w| \mid w \in L\}$, we have obviously that $L^{\geq p} = \emptyset$....


2

I don't have a complete answer, but I suspect the bound $|C| = O(|A| \times |B|)$ is tight -- I suspect we can construct a counterexample to your conjecture that $|C| = O(|A|+|B|)$, as follows. If $x \in \{0,1\}^*$ is a string, let $\text{odd}(x)$ denote the bits at odd-numbered positions, and $\text{even}(x)$ the bits at even-numbered positions. For ...


2

Your problem generalizes MAX-CLIQUE, and as such its decision version is NP-complete. To see this, given a graph $G=(V,E)$, take $I=V$, $A_i=V$, and $R=E$.


2

There is no need to consider the intersection $L \cap F$. If $F$ is finite, then so is $L \cap F$, but that is not a useful fact here. Insteed, one should proceed by contradiction. Suppose $L \setminus F$ were a context-free language. Then there exists a context-free grammar $G_1 = (V_1,\Sigma,R_1,S_1)$ such that $L(G_1) = L \setminus F$. But since $F$ is ...


2

For the record, here is an $\Omega(n^2)$ lower bound when your only access to the data is using queries of the form "$x_i = y_j$?". The proof uses an adversary argument. We will assume for convenience that $n$ is divisible by $8$. We will maintain a bipartite graph, initially with $n$ nodes on each side, corresponding to $x_1,\ldots,x_n$ on one side and to $...


2

Given the following assumptions: Since the meaning of the $=$ operator was not defined, we assume $i≠j⇒x_i≠x_j$ ... The $x_i$ values are not necessarily integers or string, but any type of elements. are taken to mean that each element of the set simply has a different encoding i.e. is represented by a different number in memory, and that each ...


2

Every language of this form can be represented as a regular expression without nested Kleene star. That is, its star height is $1$. The star height hierarchy is strict, and in particular, it is known that the language $(a^*b^*c)^*$ cannot be represented in that form. An example over a binary alphabet would be $(aa(ab)^*bb(ab)^*)^*$.


2

You can't. Consider the following sets for some $k$, with $m=k^2$ (they both are powers of $2$): $\{1..k\}$, $\{k+1..2k\}$, $\ldots$, $\{m-k+1..m\}$ $\{1, 3, 5, \ldots, 2k-1\}$, $\{2, 4, 6, \ldots, 2k\}$, $\{2k+1, 2k+3, \ldots, 4k - 1\}$, $\{2k+2, 2k+4, \ldots, 4k\}$, $\ldots$ $\{1, 5, 9, \ldots, 4k - 3\}$, $\{2, 6, 10, \ldots, 4k-2\}$ $\ldots$. Each ...


2

You can reduce 1-IN-3 SAT to your problem (an instance is a 3CNF, and we want to find a satisfying assignment having exactly one satisfied literal per clause), assuming $p \geq 3$. A clause $x \lor y \lor z$ is encoded as the constraint $x+y+z=1$. A clause $\bar x \lor y \lor z$ is encoded as the constraint $1-x+y+z = 1$; and so on. When $p = 2$, your ...


1

You don't define $H_0$. Presumably it's an undecidable set. First, $f : \mathbb{N} \to H_0$ only means that all the values of $f(x)$ are in $H_0$, i.e. the image of $f$ is a subset of $H_0$: $f(\mathbb{N}) \subseteq H_0$. The proof of the counterexample involves a stronger property: it constructs a function $f$ whose image is exactly $H_0$, that is, $f(\...


1

One approach is to sort the sets by increasing size, then repeatedly perform the following: take the first set in the list, output it, and remove from the list all supersets of it. This will output all of the minimal sets. The running time is $O(nk)$ set comparisons plus $O(n \log n)$ steps for sorting, where $n$ is the number of sets you have and $k$ is ...


1

Each subset of $S$ either contains the first element or doesn't. So we can implement a generic enumeration of subsets which match a predicate as (code given in Python but untested): def subsets_matching_predicate(elements, predicate, included = []): if len(elements) == 0: if predicate(included): yield included else: for ...


1

Our problem is NP-complete by a reduction from MAXIMUM BALANCED BICLIQUE PROBLEM (MBBP). MBBP problem: Input: A bipartite graph $G(U, V, E)$ and an integer $k$ Output: YES if there exists $A\subseteq U$ and $B\subseteq V$ with $|A|=|B|=k$ and $G[A, B]$ is a biclique, NO otherwise Given an MBBP instance $G, k$, output the following instance of our problem: ...


Only top voted, non community-wiki answers of a minimum length are eligible