Tag Info

3

This answer assumes that you only allow the tiles to have integer sides. There are always some trivial tilings, in which the rectangle being tiled has either a single row or a single column. Counting the number of these is simple combinatorics. Let us show that deciding whether there are any other tilings is NP-complete (under randomized reductions, or ...

3

(Answered also on https://cstheory.stackexchange.com/questions/47691/) A ($2C_4$, $C_5$, $P_5$)-free graph may have exponentially many maximal cliques. For example, the complement of the disjoint union of $n/3$ triangles with $3^{n/3}$ maximal cliques is $K_1 \cup K_2$-free, and thus has none of $2C_4$, $C_5$, $P_5$ appear as an induced subgraph. https://doi....

2

Broad context First off, the field in which this sort of research would be carried out is called computational social choice (theory). Searching for papers or books in that field will give you exactly what you ask for: literature on mathematical models of (political) voting schemes, and related topics like resource allocation and judgement aggregation. As ...

2

If there would be a polynomial time algorithm for your problem, it could be used to solve the NP-hard recognition problem in polynomial time by just giving the input to it and checking if its output is correct. Therefore the problem you pose is NP-hard in the sense that if it admits polynomial time algorithm, then P=NP. (Here we assume that the input is some ...

2

In modern papers, and unless stated otherwise, NP-hardness is one of the following: A decision problem is NP-hard if it is NP-hard with respect to many-one reductions. An optimization problem is NP-hard if its decision version is NP-hard. Sometimes, more informal notions are used. The most common one is probably hardness of approximation. When a theorem ...

1

Eliminating right-recursion can create parsing conflicts in an LALR(k) grammar. Here's a very simple example with $k=1$. \begin{align}S&\to L R\\ L&\to \epsilon\\ L&\to L a b\\ R&\to \epsilon\\ R&\to a c R\\ \end{align} That grammar is LALR(1). If you change R to left recursive: \begin{align}S&\to L R\\ L&\to \epsilon\\ L&...

1

The answer to your first question is: Not that we know of. A grammar is $\hbox{LALR}(k)$ if and only if its $\hbox{LALR}(k)$ automaton is deterministic. The only way that we know of checking that a grammar is $\hbox{LALR}(k)$ is to build the automaton, or something that essentially amounts to building the automaton. The good news is that the key complication ...

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