May

It was a busy May.

First, I've been to WATA 2014: 7th International Workshop on Weighted Automata: Theory and Applications, from 5th May till 9th May, where I had a talk on synchronizing weighted automata, about which I already had a post a few months ago. There were several interesting talks during the (dense) week, check the details here (in Hungarian). Then, I went to Athens for another week for doing scientific cooperation - it turned out the topic is a bit difficult to me to grasp, but it was a quite useful visit anyway. After that, AFL 2014 had been organized (in Szeged, so this time I did not have to travel anywhere) - on this conference I had a similar but different talk on the same synchronization topic, see the paper (completely free to read). I've been a bit sick on that week, though, so I could not really participate in the first part of the conference but you can read the details here (in Hungarian). Moreover, we received the notification from DCFS 2014 that our paper on biclique coverings, rectifier networks and their direct application to epsilon-removal of NFAs had been accepted, and we had to compile a camera-ready version of the submission according to the referees' (quite positive) suggestions.

That's okay for one month, but it's not the best thing that most conferences tend to have deadlines within a very short time frame...

PCP -- undecidability on four tiles?

Hey, someone please check this.
Claims to have shown PCP is already undecidable for FOUR tiles.

P is not NP, again

today's posting: http://arxiv.org/abs/1403.4143
it's maybe this year's first P!=NP posting (there were already three P=NP, at least)

okay, get back to science

(Location-)synchronizing weighted automata

Back on the synchronization topic. I've extended the notion of synchronizability of nondeterministic automata to automata with transitions weighted in an arbitrary semiring.

For preliminaries, a semiring is an algebra K=(K,+,*,0,1) where (K,+,0) is a commutative monoid with neutral element 0, (K,*,1) is a (not necessarily commutative) monoid with neutral element 1, with 0 being an absorbing element and * distributing over +, i.e.,

0a = a0 = 0,

(a+b)c = ac + bc,

a(b+c) = ab + ac

for each a, b, c in K. One usually assumes |K|>1 in order to avoid trivial cases, which in turn implies 0 is different from 1.

As an example, the naturals, the integers, the (nonnegative) rationals and the (nonnegative) reals form semirings with the standard addition and multiplication. Among these guys the integers, rationals and reals form a ring since their additive structure is a group (have inverses). Another useful example is the Boolean semiring {0,1} with addition being disjunction and product being conjunction, i.e. 1+1 = 1 (the other values come from the definition directly: 1+0 = 0+1 = 1 and 0+0 = 0 since 0 is neutral for +, 1*1 = 1, 0*1 = 0, 1*0 = 0 since 1 is neutral for *, 0*0 = 0 since 0 is absorbing for *).

Given a semiring K, and an alphabet A (that is, a finite nonempty set), a K-weighted A-automaton is simply a collection {Ma}a in A of nxn matrices Ma for some integer n>0, with entries in K. That is, to each letter a in the alphabet, a matrix Ma in Knxn is associated.

Usually one also gives an initial and a final vector but that's not needed in the synchronization framework so we omit it now.

Now to each word w=a1...ak a matrix Mw is associated in the uniform way Mw := Ma1Ma2Ma3...Mak. Note that this is the unique homomorphism from A* to Knxn extending the Ma guys.

We call a word w location-synchronizing if for some column index i, the matrix Mw has only zeros but in column i, and in column i each entry is nonzero. If even the entries in column i are all equal, we call w synchronizing. The matrix Mw itself is also called location-synchronizing (synchronizing, resp.)

As examples,

( 1 0 0 )

( 1 0 1 )

( 1 0 0 )

is not (location-)synchronizing since it has nonzero entries in two columns,

( 1 0 0 )

( 0 0 0 )

( 1 0 0 )

is not (location-)synchronizing since it has nonzero entries only in one column (the first one) but in this column a 0 also appears,

( 1 0 0 )

( 2 0 0 )

( 1 0 0 )

is location-synchronizing but not synchronizing and

( 2 0 0 )

( 2 0 0 )

( 2 0 0 )

is synchronizing.

For a semiring K, the K-synchronizability and K-location synchronizability problems are the following:

given a K-weighted automaton, does it possess a (location-)synchronizing word?

In other words, given a finite list of matrices M1, M2, ..., Mk in Knxn, does there exist a (location-)synchronizing matrix of the form M = Mi1Mi2...Mit for some t>0?

Now in the Boolean semiring B, both problems are the same since a column of nonzero elements can only be a column of ones, thus in B, every location-synchronizing matrix is also synchronizing.

It's known for a few years (check the authors' researchgate address here) that B-synchronizability is PSPACE-complete, already for partial automata, i.e. the case where in each matrix, each row contains at most one 1.

Thus we can deduce easily that K-synchronizability and K-location synchronizability is PSPACE-hard for every semiring K.

I've proven only a few things so far:

• If K is finite, then both problems are in PSPACE.
• If K is locally finite and the operators + and * are computable, then both problems are decidable.
• If K is both zero-sum-free and zero-divisor-free, then K-location synchronizability is in PSPACE, thus is PSPACE-complete.
• If the freely generated semigroup over two generators, i.e. {a,b}+ can be embedded into the multiplicative structure of K, then K-synchronizability is undecidable. (Note that in this case K-location synchronizability can be still in PSPACE, e.g. when K itself is the language semiring P({a,b}*) with union as addition and concatenation as product.)
• If the matrix mortality problem is undecidable for K, then both problems are undecidable for K. (that's the case for the integers, showing zero sum can imply undecidability for location synchronizability in semirings that are not locally finite.)
• If the naturals with the standard operations can be embedded into K  (i.e. when 0, 1, 1+1, 1+1+1, ... are all pairwise different), then K-synchronizability is undecidable.

Personally I think that this last result is a bit surprising (since e.g. mortality is decidable for the naturals) and its proof is slightly more involved than the others.

More details soon (where "soon" means "within two weeks" now.. really :-) )

Nonpermutational stuff, again

So.
We've seen that when S is a subsemigroup of Tn, whose members have exactly one fixed point each, then we can group them by their fixed points: let Si be the subsemigroup of S consisting of those guys having i as fixed point.
We've also seen that Si is indeed a semigroup and for each i, there exists a partial ordering <i of [n] such that when pf=q for some f in Si, then p<iq. Except when p=i. This <i has i as maximal element.
Without loss of generality we can assume that

• Sn is (one of) the largest among those Si guys and
• <n is consistent with the standard <,

i.e. for each f in Sn, p<pf whenever p<n.

We show that if Sn is "large enough" then the other Si guys are "small". Namely,
Lemma. Suppose for each i<j, i'<j' with i'<>j' there exists some f in Sn with if=j, i'f=j'.
Then for each i and f in Si we have

1. if j<i, then j < jf;
2. if i<=j, then i=jf.

Observe that this lemma implies that |Si| <= (n-1)! / (n-i)! since one can choose the value only for the elements smaller than i some larger value and all the others have to be mapped to i. Summing these values we get an upper bound e(n-1)! for the size of these semigroups.
The other option is that Sn does not satisfy the conditions for the lemma. It's routine to check that in this case |Sn| <= (n-1)! - (n-3)! (this bound is sharp). Since Sn was chosen to be the largest, we have that |S| <= n((n-1)! - (n-3)!).
Now for the proof of the lemma...

1. For i = n, the claims get satisfied: guys below n get elevated and n is mapped to n, okay. So assume i < n. And let f be a member of Si.
2. Then, nf < n (since n is not a fixed point of f).
3. Assume pf < p for some p and that pf <> nf. Then by the assumption, nfg = n and pfg = p for some g in Sn. Thus the composition fg has two fixed points p and n, a contradiction. Hence if pf < p, then pf = nf. In particular, if p < nf, then p <= pf. (That is, all backward arrows share their target.)
4. Assume nf < i. Note that if = i. Then by assumption nfg = i and ig=n for some g in Sn, and fgfg has two fixed points n and i, a contradiction. Thus, i <= nf.
5. Assume i < nf. Also nfffff..f is eventually i < nf (since f is nonpermutational with target i), hence there exists some smallest k such that nf^{k+1} < nf. However, this involves a second backward jump with target different from nf, a contradiction. Thus i = nf.
6. Observe that 3, part b and 5 together prove Statement 1.
7. Assume i < j < jf. Then for some g, jfg = n and ig = j and fgfg has two fixed points n and j, a contradiction. Hence if i < j, then jf < j, thus jf = i, proving Statement 2.

That's all. It turned out to be not that horrible at all...
...I'd guess the bound is not strict. I would be surprised if some S with |S| >= 3(n-1)! could be actually constructed...

NP is in DTIME(n^{polylogn})? or not?

While I've been slicing chicken, my phone fetched today's arXiv posts in my topics of interests and I bumped into this. While it's not the "usual" P=NP stuff, I'm still quite sceptical..
..however, if it's correct, that has several serious impacts on complexity theory. And the author has several strong publications..

..worth a read. who knows.

On the number of nonpermutational transformations

So for recap, a transformation f: [n]→[n] is nonpermutational ([n] stands for the set {1,...,n} here) if f(X)=X implies |X|=1 for any nonempty subset X of [n].

(These guys are interesting now since a reduced automaton recognizes a definite language if and only if every nonempty word induces a nonpermutational transformation on the set of states, but it's not important for now.)

For example, f=(2,3,3) and g=(1,1,2) are nonpermutational (we write transformations of [n] also as vectors, the above f is defined as f(1)=2, f(2)=3 and f(3)=3), but their product fg = (1,2,2) is not since fg({1,2})={1,2}. Product here is function composition, i.e. fg(x)=g(f(x)). Sorry for the ordering: when f and g are words inducing some transformation on the state set of an automaton, then fg, the concatenation of f and g in this order induces a function that way: first we apply (i.e. "read") f, then g.

That's why we will write pf instead of f(p) for a p in [n].

Thinking a bit, the following are equivalent for a function f:[n]→[n]:

1. f is nonpermutational;
2. f ^k is constant for some k;
3. the graph of f is a rooted tree with edges directed towards the root and with a loop attached to the root.

Here "the graph of f" is the one with vertex set [n] and p→q is an edge if and only if pf=q. Thus, each node has outdegree one. Since the graph is finite, this implies the existence of at least one cycle.

Clearly, since if f is any transformation of [n], then f(X)=X with X being the (nonempty) set of all nodes lying on some cycle. Thus if f is nonpermutational, then the above X has only one element, hence there is only one vertex lying on a cycle -- which has to be a loop then. Removing this loop we get a DAG (a directed acyclic graph), with each node but the originally looped one having outdegree one, showing 1) implies 3). Now 3) implies 2) since each application of f takes each vertex closed to the root and thus f ⁿ maps each vertex to the root. Finally, 2) implies 1) since if Xf=X, then Xf ^k=X as well. Since f ^k is by assumption a constant, X is a singleton, thus f is indeed nonpermutational.

In the following, when f is a nonpermutational transformation, Fix(f) denotes its unique fixed point.

We are interested in the following question: given n, how large can a semigroup of nonpermutational transformations of [n] be at most? Since the set of all nonpermutational functions do not form a semigroup, it's not that easy as counting all the nonpermutational functions but the answer is a hell less number.

Trivial bound: nⁿ. It's the total number of transformations...
A slightly lower but still trivial bound: n^(n-2). It's (by Cayley's formula) the number of rooted trees on the vertex set [n], so it's the total number of nonpermutational transformations. But, they do not form a semigroup...
A somewhat more carefully designed bound: n!. To see this, let S be a semigroup consisting of nonpermutational transformations only. Let Si, for i in [n], stand for the set of those members f of S with Fix(f)=i. Then each Si is also a semigroup (since if p is a fixed point of f and g, then it is the fixed point of fg as well). Now for i in [n], let us consider the graph Gi with vertices [n] and (p,q) being an edge iff pf=q for some f in Si. Observe that since Si is a semigroup, Gi is transitive (if f maps p to q and g maps q to r then fg maps p to r). Clearly i is a sink of Gi (there is a loop attached on i and no any other outgoing edges). Let's remove this loop and let Gi' stand for the resulting graph. Suppose there is a cycle in Gi'. Then by transitivity, there is a loop in Gi' as well (removing the loop from the sink does not affect transivity), implying that there is a function in Si having a fixed point different from i which is nonsense by definition of Si. Hence Gi' is a transitive DAG -- a strict partial ordering of [n] with maximal element i. Let < be an arbitrary linear extension of this partial order. Then any member f obeys p<pf for p<>i and if=i. The total number of such f's is (n-1)!: one can choose (n-1) different values for the first element, (n-2) for the second and so on. Thus, |Si| is at most (n-1)! and since S is the disjoint union of n such Si's we get the upper bound n(n-1)!=n!.

Next time we reduce this bound a bit by a horrible case analysis to get an upper bound n((n-1)!-(n-3)!)...

stay tuned