We are lifting classical problems from single instances to regular sets of instances. The task of nding a positive instance of the combinatorial problem P in a potentially in nite given regular set is equivalent to the so called intReg-problem of P , which asks for a given DFA A, whether the intersection of P with L(A) is non-empty. The intRegproblem generalizes the idea of considering multiple instances at once and connects classical combinatorial problems with the eld of automata theory. While the question of the decidability of the intReg-problem has been answered positively for several NP and even PSPACE-complete problems, we are presenting some natural problems even from L with an undecidable intReg-problem. We also discuss alphabet sizes and di erent encoding-schemes elaborating the boundary between problem-variants with a decidable respectively undecidable intReg-problem.
In many elds multiple problem instances are considered all at once and they
are accepted if there is at least one positive instance among them. The instances
are described through a strongly compressed representation. For instance, in
graph modi cation problems 1 a graph G together with several graph editing
operations is given and one asks whether G can be transformed into a graph
G0 with a certain property using up to n editing operations [
A natural generalization of the task of nding a positive instance in a nite
set of instances is to search in an in nite set of instances. A well studied class
of potentially in nite languages are the regular languages which are also in a
compressed way represented by nite automata or regular expressions. We call
A = (Q; ; ; q0; F ) a deterministic nite automaton (DFA for short) if Q is
a nite set of states, a nite alphabet, : Q ! Q a total transition
function, q0 2 Q the start state, and F Q the set of nal states. We generalize
to words in the usual way. We denote the language accepted by A with
L(A) = fw 2 j (q0; w) 2 F g. Asking whether the accepted language of
a DFA A contains a positive instance of a problem P is equivalent to asking
whether the intersection P \ L(A) is non-empty. This question was introduced
in [
The intReg-problem has been studied independently under the name regular
realizability problem RR(L), where the lter language L plays the role of problem
P above, i. e., RR(L) = intReg(L) (see [
In contrast, the line of research in [
This paper is structured as follows. First, we discuss machine languages for
several complexity classes. Then, we consider the problems of bounded and
corridor tiling, followed by bounded PCP. We will show that all of these problems
have an undecidable intReg-problem. Next, we investigate the PSPACE-complete
problem of Equivalence of Regular Expressions and prove that the problem
in a shu ed encoding has an undecidable intReg problem. As the proof only uses
the concatenation operator of regular expressions, we get the undecidability of
intReg of the so called String Equivalence Modulo Padding problem in
a shu ed encoding, which lies in L. For this problem, we will discuss di erent
alphabet sizes and encoding schemes and show that all other considered variants
of this problem have a decidable intReg-problem. Finally, we present a graph
problem on directed multi-hyper-graphs with an undecidable intReg-problem.
This contrasts the results in [
We expect the reader to be familiar with regular languages and their
description through nite automata and regular expressions. The reader should also be
familiar with the complexity classes L, NL, NP, and PSPACE. We refer to the
textbooks [
For several complexity classes, we can de ne machine languages which are
complete for their complexity classes. We will show that the following machine
languages have an undecidable intReg-problem. The intReg-problem of the machine
language for NP was already discussed in [
string an with n 2 N.
Question: Does M accept x visiting only log(n) di erent tape-positions? Encoding: LNL = fhM i$x$an j M is an NTM accepting x in log(n) spaceg. The language LNL is complete for the class NL. Every language in NL can be accepted by a non-deterministic Turing machine which is space-bounded by a function f 2 (log). Since f is logspace-constructible, there exists a deterministic TM Mf which computes f (n) on the input 0n in logarithmic space. Hence, every xed problem in NL can be reduced to LNL by hard-wiring the NTM M which decides the problem and is space-bounded by f , followed by the input word w and a unary string of size 2f(jwj). Note that f (jwj) is logarithmically smaller than jwj and hence can be stored using log(jwj) many cells. A logarithmically space-bounded TM can compute an output string which is exponentially in the size of its used memory. As can be easily veri ed LNL 2 NL.
The machine language for NP, in short LNP, is de ned analogously demanding that x is accepted in n steps, while the machine language for PSPACE, in short LPSPACE, demands x to be accepted in n space. With similar arguments LNP is complete for NP and LPSPACE is complete for PSPACE.
Theorem 1. intReg(LNL), intReg(LNP), and intReg(LPSPACE) are undecidable.
Proof. We give a reduction from the undecidable non-emptiness-problem for
recursively enumerable sets [
The next problem we want to investigate is about the tiling of the plane. For
a given set of tile types and a xed corner tile, the question is to ll a plane
with the given tiles under some conditions. While the problem for an in nite
plane is undecidable [
First, we will give a formal de nition of the problem Bounded Tiling. Then, we will show that this problem has an undecidable intReg-problem by reducing L6=; to the problem intReg(Bounded Tiling).
A tile is a square unit where each of the edges is labeled with a color from a nite set C of colors. The color assignment is described by tile types. A tile type is a sequence t = (w; n; e; s) with w; n; e; s 2 C of four symbols representing the coloring of the left, top, right, and bottom edge color. We denote with tw, respectively tn, te, ts, the rst, respectively second, third, and forth entry of the tuple t. Tiles can be regarded as instances of tile types. A tile must not be rotated or re ected. In the following problem, we give a nite set of tile types as input. From every tile type arbitrary many tiles can be placed. The tiles have to cover up a square grid region such that adjacent edges have to have the same color. The grid comes with an edge coloring which contains for each border of the square grind a sequence of colors presetting the adjacent color of tiles resting on the edge. A tiling is a mapping from the square grid region to a set of tile types. With hT i we denote a proper encoding of the tile type set T and with [n] we denote the set f1; 2; : : : ; ng. We call f : [n] [n] ! T a tiling function if for all i; j 2 [n], it holds that f (i; j)e = f (i + 1; j)w for i < n and f (i; j)n = f (i; j + 1)s for j < n meaning that adjacent edges of the tiles have the same color. Here, the bottom left square of a grid region is indexed by (1; 1).
De nition 3 (Bounded Tiling).
Given: Finite set T of tile types with colors from a nite color set C and an n n square grid region V with a given edge coloring.
edge coloring? Encoding: hT i followed by an edge coloring $l$t$r$b, l = l1#l2# : : : #ln, with t = t1#t2# : : : #tn, r = r1#r2# : : : #rn, b = b1#b2# : : : #bn with li; ti; ri; bi 2 C.
Howard Straubing gives in his article \Tiling Problems" [
Peter van Emde Boas [
With that construction in mind, we will now prove that the intReg-problem for Bounded Tiling is undecidable.
Theorem 2. The problem intReg(Bounded Tiling) is undecidable.
Proof. We give a reduction from the undecidable problem L6=;. Let hM i be the
encoding of an arbitrary NTM. We construct a regular language R which contains
a positive Bounded Tiling instance if and only if M accepts at least one word.
We alter the machine M to an NTM N which behaves like M except having
only one distinguished accepting con guration, i.e., an empty tape with the head
on the rst position of the former input word. According to Straubing [
Let TN be the corresponding tile type set for the NTM N and let CN be the set of colors appearing in TN . Let C CN be the subset of colors representing input alphabet symbols, let 2 CN be the white color representing a white vertical border edge of the square grid, and let 2 CN be the color representing an empty tape cell. Finally let qf 2 CN be the color representing the accepting state of the Turing machine. We de ne the regular set R as R = L (fhTN i $ $ qf $ $ C g) : The set R consists of the set of tile types for the NTM N together with edge colorings for every possible input word and every possible size of the eld V . The top row will always contain the accepting con guration of N padded with arbitrary many blank symbols. The left and right borders of the eld V can consist of arbitrary many white edges, while the bottom row can encode every possible input word with arbitrary many added blank symbols allowing an arbitrary time bound for the Turing machine. Note that the edge coloring does not have to de ne a square, but the square shape is also contained in the set R for every input word and every number of padding symbols. Therefore, for every input word w, the set R contains every size of squared elds with w encoded in the bottom edge coloring. The tile type set of R is constructed in a way that in a valid tiling adjacent rows will represent successive con gurations of the Turing machine. So, for every number of steps the TM makes on the input word, there is a square eld, with the input word encoded, in the set R preventing enough space for the con gurations of the TM. This brings us to our main claim, R \ Bounded Tiling 6= ; , L(N ) 6= ;. tu
With the same argument, we can show that the PSPACE-complete problem
Corridor Tiling [
Another undecidable problem, which becomes decidable if we restrict the size
of the potential solution, is the Post's Correspondence Problem (in short
PCP). We show that the NP-complete version Bounded Post
Correspondence Problem [
Given: Finite alphabet , two sequences A = (a1; a2; : : : ; an), B = (b1; b2; : : : ; bn) of strings from , and a positive integer K n.
Question: Is there a sequence i1; i2; : : : ; ik of k K (not necessarily distinct) positive integers ij 2 [n] such that ai1 ai2 : : : aik = bi1 bi2 : : : bik ? Encoding: LBP CP := fa1#a2# : : : #an$b1#b2# : : : #bn$ bin(K) j K n ^ A = (a1; a2; : : : ; an); B = (b1; b2; : : : ; bn) is a PCP instance with a solution Kg. The problem PCP is de ned analogously but does not contain a bound K. Theorem 3. The problem intReg(BPCP) is undecidable.
Proof. We give a reduction PCP intReg(BPCP). Let A = (a1; a2; : : : ; an) and B = (b1; b2; : : : ; bn) be a PCP instance. We construct a regular language R consisting of the given PCP instance combined with every possible solution bound K. Since K is bounded by the length of list A and B, we will pump those lists up by repeating the last list element of both lists arbitrarily often. Because the same element can be picked multiple times, adding elements already appearing in the given lists does not change the solvability of the instance. We de ne R as R = fa1#a2# : : : #an(#an) $b1#b2# : : : #bn(#bn) $f0; 1g g: It holds that R \ BPCP 6= ; if and only if there is a sequence of indexes i1; i2; : : : ; im such that ai1 ai2 : : : aim = bi1 bi2 : : : bim . tu 5
In this section we show that the problem of Equivalence of Regular
Expressions (in short RegEx) over a binary alphabet in a shu ed encoding has an
undecidable regular intersection emptiness problem. It turns out, that the
problem is already undecidable if the regular expressions do not use alternation or the
Kleene star. Thus, also the problem of String Equivalence Modulo Padding
over a binary alphabet in a shu ed encoding has an undecidable intReg-problem.
When we consider the String Equivalence Modulo Padding problem over a
unary alphabet or in a sequential encoding, the problem becomes decidable. We
rst de ne the problem of Equivalence of Regular Expressions (adapted
from [
De nition 5 (Shuffled RegEx).
Given: A word w = e1f1e2f2e3f3 : : : enfn over the alphabet [ f;; ; (; ); j; g such that E = e1e2e3 : : : en and F = f1f2f3 : : : fn are regular expressions over the alphabet using the operators alternation, concatenation, and Kleene star. Note that one regular expression can be padded with or ; if the regular expression are of unequal length.
Question: Is L(E) = L(F )?
The problem of equivalence of the regular expressions is well known to be
PSPACEcomplete [
Theorem 4. The problem intReg(Shuffled RegEx) is undecidable. Proof. We give a reduction PCP intReg(Shuffled RegEx) and translate a given PCP instance into a regular language LReg. We emphasize references to the regular expression de ning the language LReg, while references to the regular expressions encoded in the words of LReg are not emphasized. We also emphasize references to the regular language of shu ed regular expressions.
Let A = a1; a2; : : : ; ak and B = b1; b2; : : : ; bk be a PCP instance. We de ne a regular expression, describing a regular language LReg of shu ed regular expressions describing concatenations of list elements. Let LReg be de ned through the regular expression ab1100 ab2200 : : : ak0 + bk0 where the string abii00 consists of the two shu ed strings ai, bi where the shorter string is padded with -symbols at the end until both stings have the same length. The -symbol is here used as an alphabet symbol of the language LReg and refers to the regular expression which will be interpreted as f g and not to the empty word itself. Therefore, LReg consists of all possible pairwise concatenations of elements of the lists A and B where the concatenated strings are padded with -symbols to have the same length.
For every PCP instance, the described regular expression of the language LReg can be computed by a computable total function. It remains to show that the PCP instance A, B has a solution if and only if LReg \ Shuffled RegEx 6= ;. More precisely, the intersection will contain all solutions of the PCP instance.
First, consider the only if direction. Let i1; i2; : : : ; in be a solution of the PCP instance A; B such that ai1 ai2 : : : ain = bi1 bi2 : : : bin . By construction, the regular language LReg contains all possible concatenations of the strings ab1100 ; : : : ; abkk00 corresponding to the pairs (a1; b1); : : : (ak; bk) of the strings of the lists A and B. Therefore, LReg also contains the word w = abii1100 abii2200 : : : abiinn00 . The word w consists of the two shu ed regular expressions E = ai1 0ai2 0 : : : aik 0 and F = bi1 0bi2 0 : : : bik 0. Since they are both nonempty strings with padded 's their described language is a singleton set. By construction, we have L(E) = fai1 ai2 : : : aik g and L(F ) = fbi1 bi2 : : : bik g. By assumption is ai1 ai2 : : : ain = bi1 bi2 : : : bin , therefore we have L(E) = L(F ) and w 2 LReg\ Shuffled RegEx.
For the other direction, assume LReg\ Shuffled RegEx 6= ;. Let w = abii1100 abii2200 : : : abiinn00 2 LReg\ Shuffled RegEx consists of the two shu ed regular expressions E = ai1 0ai2 0 : : : aik 0 and F = bi1 0bi2 0 : : : bik 0. By assumption is L(E) = L(F ). Since L(E) and L(F ) each contain only one element, from which the describing regular expressions di er only by padded -symbols, it holds by construction that ai1 ai2 : : : ain = bi1 bi2 : : : bin . Therefore, i1; i2; : : : ; in is a solution of the PCP instance.
To show undecidability of the intReg(Shuffled RegEx) problem we have made use of only one operator of regular expressions, namely the concatenation. If we restrict the Shuffled RegEx problem to regular expressions using only letters from , the -symbol and the concatenation, we get the much easier problem of Shuffled String Equivalence Modulo Padding, in short Shuffled String . Since we are only using the associative operation of concatenation, we can get rid of brackets. All of the following problems are in the complexity class L, since they can be solved deterministically using two pointers. De nition 6 (Shuffled String ).
Given: A word w = s1t1s2t2s3t3 : : : sntn such that si; ti 2 [ f g. Question: Is h(s1s2s3 : : : sn) = h(t1t2t3 : : : tn) where h : ( [ f g) ! is an erasing homomorphism which leaves all symbols in unchanged and deletes the -symbols. Corollary 1. The problem intReg(Shuffled String ) is undecidable.
If we restrict the alphabet to singleton sets, the Shuffled String becomes
decidable as this problem, considered as a language, is a context-free language.
Alternatively, if we refrain from the shu ed encoding and consider instead a
sequential encoding, the problem also becomes decidable. Here, we identify
subautomata which accept pre xes up to the symbol $ and sub-automata which
accept su xes starting after the symbol $. We use a homomorphism h to erase
the padding symbol and check for each pair of pre x and su x sub-automata
AP and AS whether h(L(AP )) \ h(L(AS)) 6= ;. Details on the above discussed
variations can be found in the long version of this work [
In this section we consider a graph problem with an undecidable intReg-problem
which contrasts the decidability results for graph problems in [
For a word w 2 and a letter 2 , we denote with wj the number of 's in w. We consider directed hyper-multi-graphs with self loops and 2 to 4 vertices per edge. More formally, we consider graphs of the form G = (V; E), where V is a set of vertices and E a set of edges together with the function fE : E ! V [2::4] which assigns each edge with a tuple consisting of 2 to 4 vertices incident to this edge. An edge is called a loop if all of its incident vertices are identical. We encode G by listing its edges separated by $-signs. Vertices appearing in edges are encoded by strings of a's separated by #'s. To extract the encoded graph, we de ne the following decoding function. For m 2 N, 1 ki 3; i m, let where G = (V; E) with V = fvpi j i 2 [m]g [ Sfvqi;j j j kig; E = fe1; e2; : : : ; emg, fE : ei 7! (vpi ; vqi;1 ; :::; vqi;ki ). We present a graph-problem over this class of graphs for which its intReg-problem is undecidable by encoding the sets of derivation-trees of two given context-free grammars in Chomsky-normalform (CNF for short) into a regular set of directed hyper-multi-graphs. The languages of the two grammars will share a common word w if and only if the intersection of the constructed regular language with the graph-problem is nonempty and contains the two derivations of w. We call G = (V; T; P; S) a context free grammar in CNF, if V is a nite set of variables, T a nite set of terminal, P a set of derivation rules of the from A ! BC or A ! a with A; B; C 2 V , a 2 T , and S 2 V the start variable. We rst give the construction and then de ne the graph problem Embedded Derivation Trees, EDT for short. Theorem 5. intReg( EDT) is undecidable.
Proof. Let G1 = (V1; T; P1; S0), G2 = (V2; T; P2; S00) be two context free grammars in CNF. We alter them, by introducing two new variables S1 and S2, to the grammars G1 = (V1 [fS1g; T; P1 [fS1 ! S0g; S1), G2 = (V2 [fS2g; T; P2 [fS2 ! S00g; S2). From now on we will identify V1 [ fS1g as V1 and V2 [ fS2g as V2. W.l.o.g. assume that the sets V1; V2 are disjoint and both grammars share the terminal alphabet T . Note that the following problem is undecidable: Is there a word w 2 T such that w can be derived from G1 and from G2?
Let m1 = jV1j, m2 = jV2j, t = jT j(jT j+1) , n = m1 + m2 + 2t + 2. We construct a 2 regular set R = R1 R2, where R1 (respectively R2) is de ned as follows: We x an order on the elements in V1; V2; T such that S1 is the rst element in V1 and S2 is the rst element in V2. We refer to the i'th element of a set S as S[i]. Let V1[s0] = S0, V2[s00] = S00 for integers s0 and s00. For the derivation rule S1 ! S0 in G1, we dene the regular expression rs1 = a0#a1#a0#as0 $ and for the derivation rule S2 ! S00 in G2 we de ne rs2 = an 1#am1+1#an 1#am1+s00 $ For every derivation rule p1 = V1[i] ! V1[j]V1[k], i; j; k m1 in P1, we de ne the regular expression rp1 = a0#ai(an) #aj(an) #ak(an) $: For a derivation rule p2 = V2[i] ! V2[j]V2[k], i; j; k m2 in P2, we de ne rp2 = an 1#am1+i(an) #am1+j(an) #am1+k(an) $. We de ne for each j 2 [jT j] and b 2 f1; 2g a regular expression which encodes a cycle of length j consisting of binary edges. We call these cycles leave-cycle later. rljcb = m1+m2+(b 1)t+ (j+1)(j+2) 2
2 Y
ak(an) #ak+1(an) $ k=m1+m2+(b 1)t+ j(j2+1) am1+m2+(b 1)t+ (j+1)(j+2) 1(an) #am1+m2+(b 1)t+ j(j2+1) (an) $
2 For derivation rules q1 = V1[i] ! T [j] in P1 and q2 = V2[i] ! T [j] in P2, we de ne: rq1 = a0#ai(an) #am1+m2+ j(j2+1) (an) $rljc1, and rq2 = an 1#am1+i(an) #am1+m2+t+ j(j2+1) (an) $rljc2. We are now ready to de ne R1 and R2. We set Ri = rsi Spi2Pi rpi Sqi2Pi rqi for i 2 f1; 2g.
We now de ne our graph property such that it lters out the encoded graphs
in the regular set which consists of two derivation trees, one from G1 and one
from G2, which derivate the same word. It is helpful to consider Figure [
Let G = (V; E) be a directed hyper-multi-graph such that each edge contains two, three, or four vertices. The multi-graph embedding maps G onto a multi-graph (G) = Gm = (Vm; Em) with Em Vm Vm in the following way: Vm = V , for a 4-nary edge (a; b; c; d) 2 E we add the edges (a; c); (b; c); (b; d) to Em. For a ternary edge (a; b; c) 2 E, we add the edges (a; c); (b; c) to Em. Binary edges are simply added to Em.
Input: A directed hyper-multi-graph G = (V; E) with fE : E ! V [2::4]. Question: Does the multi-graph embedding (G) consists fo two connected components G1m and G2m such that the following holds. G1m contains a vertex v1 and G2m contains a vertex v2, such that G1mnfv1g and G2mnfv2g are (directed) binary trees (where edges are pointing from parents to children) in which the leave layer consists of directed cycles (called leave-cycles). Exactly the root-node and the parents of leave-cycles have out-degree one, all other nodes which are not part of a leave-cycle have out-degree 2. The node v1 is connected to exactly one child of each parent node in G1mnfv1g except for the root as here v1 is pointing to the root and not to the child. The only node pointing towards v1 is the root of G1mnfv1g. The node v1 has no further connections. The same holds for v2 with respect to G2mnfv2g. If G1m and G2m are drawn such that v1 and v2 always point to the left child, then the sequence of lengths of the leave-cycles of G1m and G2m (read from left to right) must coincide. Both graphs must not contain multi-edges and loops are only allowed as a leave-cycle. The leave-cycles are not connected to each other.
We will rst argue that for any w 2 R with decdir hyp mul(w) being a positive instance of EDT the sub-graphs G1m and G2m of (decdir hyp mul(w)) must correspond to two derivation trees, one for G1 and one for G2.
Note that for i 0 (mod n) and j 1 (mod n) the only vertex labels ai(#j$) and aj (#j$) which can be a factor of a word in R are a0# and an 1#. Especially, there are no factors of the form (an)k(#j$) or (an 1)(an)k(#j$) with k > 0 and the vertex a0# is only appearing in sub-graphs corresponding to derivation rules of G1 whereas an 1# is only appearing in sub-graphs corresponding to derivation rules of G2. Hence, for a graph G = (decdir hyp mul(w)) with w 2 R in order to consist of two disjoint graph G1m and G2m one of them must contain a vertex encoded by a0# and hence be constructed by G1 and the other one must contain a vertex encoded by an 1# and be constructed by G2 as one of this elements is part of any regular expression rsi ; rpi ; rqi .
Note that by the de nition of R1 and R2 each string w 2 R contains exactly one factor encoding the derivation rule S1 ! S0 and one factor encoding the derivation rule S2 ! S00. There are no other derivation rules in which S1 or S2 appear. Hence, there will be no factor a1(an)k# and am1+1(an)k# in w with k > 0. As rs1 and rs2 are the only regular expressions allowing to create an edge, the multi-edge embedding of which creates an arc pointing towards v1 (encoded by a0#) and v2 (encoded by an 1#), the root of the tree2 Gm1nfv1g necessarily be S1 with the child S0 and the root of the tree Gm2nfv2g needs to be S2 with child S00. The sub-tree starting in S0 will then correspond to a derivation tree of G1, when the leave-cycle of length i is interpreted as the i-th letter of T , and the sub-tree starting in S00 will correspond to a derivation tree of G2.
W.l.o.g. we will focus on Gm1. By the de nition of EDT G1m must be a binary tree with leave-cycles and by previous arguments have the root S1 with the single child S0, all other internal parent-nodes have out-degree two. As G1m does not contain any multi-edges and loops are only allowed as leave-cycles, every inner node V1m[i] has exactly two appearances of its encoding ak# in w namely in the 4-nary hyper-edge where it appears as one child and in the 4-nary hyper-edge where it appears as the parent node. The rst edge corresponds to a derivation where the variable represented by V1m[i] is 'created' and the second edge to a derivation where this variable is 'consumed'. Hence, following the inner nodes gives us a derivation tree for derivations of the form A ! BC in P1.
Every member of a cycle of length k has its own domain of representatives
which is disjoint with the domains of the other elements of the cycle. It is also
disjoint with the domains of elements of cycles with di erent lengths. We show
that if w 2 R encodes a positive instance of EDT, then for each leave-cycle
Ci of length k which is the child of a node V1m[j0] encoding the variable V1[j],
the description of Ci is created by the regular expression rq1 which encodes the
derivation V1[j] ! T [k]. Let Ci[
Replacing cycles of length k by the corresponding letters T [k] completes our derivation tree constructed by the inner nodes with derivations of terminals. As the trees G1m and G2m have the same sequence of cycle lengths in the leavelevel if the child pointing to v1, respectively v2 is drawn as the left child, the constructed derivations derive the same word.
For the other direction, we can construct a word w 2 R for which the graph
decdir hyp mul(w) is a Yes-instance from the two derivations of a common word
x 2 L(G1) \ L(G2) as follows. We go through the derivation trees from top
to bottom, left to right and increase an index k with every new considered
2 We interpret the cycles in the leave-layer as leaves and hence interpret the graph as
a tree despite the fact that it contains cycles.
appearance of a variable. We encode each derivation according to the above
de ned regular expressions, s.t. for the encoding ae of a variable appearance
e n = k. Details on constructing w can be found in the long version [