Optimization in multivalued logic. Optimal strings with given patterns

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

$$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 thi

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.

StackExchange Computer Science Q#40700, answer score: 2