3
$\begingroup$

This question comes from an application in multivalued logic.

Suppose, we are given an alphabet of three letters $A, B, C$ and a set of indices $1,2,3,4,5$. Consider items formed by subscripting the letters with one of the indices. Examples are the following:

$$A_1 \\ B_4 \\ C_3 \\ ... $$

Suppose, additionally, that there is a total binary relation $\mathcal{R}$ on items $*_i <= *_j$ for each pair $ i, j \in \{ 1,..., 5 \} $ where $*$ denotes one of the letters $A,B$ and $C$. The relation is reflexive and transitive.

Consider a set of strings of length $5$ freely generated by the alphabet $A, B, C, ...$ disregarding ordering. Examples are the following:

$$ AABBC \\ AAAAB \\ AABCC \\ ... $$

Since order doesn't count, a string $AABBC$ is the same as $ABBAC$.

Let's call such strings templates. The templates can be "filled in" with the indices to form tuples of items using the following rules:

  • R1: there may be no repetitions of indices disregarding the letter type, e.g.

$$A_1, A_1, B_2, C_3, C_4$$

and

$$A_1, A_2, B_2, C_1, C_4$$

are both forbidden since the index $1$ is used two times.

  • R2: ordering in a tuple does not count, e. g.

$$\left( A_3 A_2 B_1 B_4 C_5 \right)$$

is the same as

$$\left( A_2 A_3 B_1 B_4 C_5 \right)$$

One can think of such "filling in" the templates as filling in a truth table with several logical levels in general.

Let us denote the set of all freely generated strings of length $5$ from the $A,B$ and $C$ by $\mathbb{Tmp}$. Let $\mathbb{Tpl}$ denote the set of all tuples generated by index assignments according to the rules R1 and R2. We can define a mapping $U:\mathbb{Tpl} \mapsto \mathbb{Tmp}$ which removes the indices from a tuple and gives its underlying template. For example:

$$ U \left( A_2 A_3 B_1 B_4 C_5 \right) = AABBC $$

We say that a tuple $T$ satisfies the template $t$ if $U(T) = t$. We say that $T$ satisfies a set of templates $\tau = \left(t_1, t_2, ..., t_l \right)$ if there exists a template $t_i \in \tau$ for some $i \in \left( 1,2,...,l \right)$ s. t. $U(T) = t_i$.

Suppose, that we are given a set of templates $\tau$ and a total binary relation $\mathcal{R}$ on items.

What is the greatest item (greatest in the sense of the binary relation $\mathcal{R}$) of all the least items of all the tuples satisfying the templates $\tau$. In other words, what is the maximin item of the tuples?

The bruteforce algorithm is evident: take a template, build all the corresponding tuples, compare elements in each tuple and find the least, compare all the outcomes of the previous step, take the greatest. I am sure this is an $NP$-complete problem if the underlying truth table is irreducible.

What if we order all the items to obtain a sequence like this:

$$ C_2 <= B_4 <= C_1 <= C_5 <= B_1 <= A_2 <= C_3 <= A_3 <= B_3 <= C_4 <= A_4 <= A_5 <= B_5 <= A_1 <= B_2$$

Let's call this sequence $S$.

Can it simplify the problem by any chance?

For instance, consider the templates:

$$\tau = \left( AAAAB, AAABB, AAABC \right)$$

Can there be an algorithm more effective than the bruteforce? I was thinking in the following way: one can start in the sequence $S$ form left to right and "drop" items until there is no more letters to drop (otherwise, the templates are violated) or if the indexing requirement is violated.

Example of such a procedure goes like this:

drop $C_2$, drop $B_4$, drop $C_1$, drop $C_5$, drop $B_1$, drop $A_2$, drop $C_3$, drop $A_3$, $B_3$ must be picked

So no tuple may contain an item greater than $B_3$.

It seems to offer a minor complexity reduction and only for simple templates. For more complex ones, there are subtleties which I won't discuss here. But I am suspicious that there is a fundamental limitation in this problem which makes every algorithm not really better than the bruteforce.

$\endgroup$
  • $\begingroup$ There seem to be a lot of questions in here, which usually doesn't work well on Stack Exchange. It should probably be broken up into several questions. Also, could you edit the "update:" into the main text? As far as most people here know, this is a completely new question. It doesn't help anyone to know that that section was added later. (Even when the question is edited after being posted, it probably hinders more than it helps.) $\endgroup$ – David Richerby Mar 24 '15 at 14:31
  • $\begingroup$ Please don't re-post; that violates site rules and is impolite to answerers. In the future you can click "flag" underneath your post to flag it for moderator attention and ask them to migrate it. $\endgroup$ – D.W. Mar 24 '15 at 16:36
  • $\begingroup$ What does it mean for a tuple to "satisfy these templates"? Does that mean it satisfies all templates? Presumably it's OK to use a different sequence of indices for each template? When you talk about a tuple, I'm guessing you mean the set of values (not the formal string $A_1A_2B_3B_4C_5$)? What do you mean by dropping values? What is the underlying domain of values? Is it infinite, or finite? If it is finite, how many elements does it have? Is it totally ordered? If not, what do you know about its structure? $\endgroup$ – D.W. Mar 24 '15 at 16:42
  • $\begingroup$ Thanks for the info about migrating questions -- will use it for future. Concerning your second comment, a tuple must satisfy at least one of the templates of course -- how can it satisfy all of them if they are different? "Dropping" values is meant abtractly. Imagine that you start in the sequence from left to right. You "drop" values until you meet one which you have to pick to fulfill template and index requirements. The underlying domain for the values is the alhpabet. I tried to make it clear, but there are some flaws unforunately, sorry for that. $\endgroup$ – Rubi Shnol Mar 25 '15 at 10:33
  • $\begingroup$ I'm sorry, I can't understand the question at all. Now I'm even more confused, after the update. Can you define all terms precisely, and provide a worked example? What is an "optimal tuple"? What is "the afore sequence"? Where did $(B_3,A_4,A_5,A_1,B_2)$ come from? What do you mean by "leftmost value" and how does relate to the "least element is as large as possible" goal? If you only need to satisfy one of the templates, why don't you run your algorithm separately $k$ times, once on each of the $k$ templates, and keep the best tuple you found among those $k$ trials? I'm totally lost. $\endgroup$ – D.W. Mar 26 '15 at 21:46
2
$\begingroup$

As stated, it looks like the solution is trivial: if $\omega$ is the largest value in the underlying domain of values, then $\omega \omega \cdots \omega$ is the optimal value for the tuple.

Let's take your example, templates $AAAAB$, $AAABB$, and $AAABC$. Suppose the underlying domain of allowable values is $\{0,1,\dots,9\}$. Then $99999$ is the optimal tuple. It satisfies $AAAAB$ by the assignment $A_1A_2A_3A_4B_5$. It satisfies $AAABB$ by the assignment $A_1A_2A_3B_4B_5$. In fact it satisfies every template. For any template, there exists an assignment of values to each $X_i$ that makes the tuple $99999$ match that template: just assign the value $9$ to every $X_i$, for all levels $X$ and all variable indices $i$.

Perhaps you meant to provide both the templates and the assignment of values (all $m^2$ values for all the $X_i$'s, where $X$ and $i$ range over all possibilities) as input.

$\endgroup$
  • $\begingroup$ Thanks for the answer @D.W. Unfortunately, that's not right. You can't have repeated indices in a tuple. Index assignment is a permutation: "assign indices (without repetitions)". It means, a tuple must contain all indices from 1 to 5 in this case. What doesn't play a role is if you permute two values with the same letters, .i.e $A_1 , A_2$ = $A_2 , A_1$. $\endgroup$ – Rubi Shnol Mar 25 '15 at 10:36
  • $\begingroup$ OK, thanks for the explanation, @ValerySaharov. I've edited my answer to reflect that constraint, but the bottom line still appears to be the same. $\endgroup$ – D.W. Mar 25 '15 at 19:43
  • $\begingroup$ Thanks @D.W. Let's talk about it a bit more, this question arises really often in engineering application (many problems can be formulated in terms of multivalued logic). Let's focus on three letters A, B, C and five indices 1, 2, 3, 4, 5. The tuples you mentioned in your answer are now right: they match the templates and they contain all the indices from 1 to 5. But, these tuples are not necessary optimal. Please look at the update to the question. $\endgroup$ – Rubi Shnol Mar 26 '15 at 10:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.