User michaël - MathOverflow

What is the relation between the number syntactic congruence classes, and the number of Nerode relation classes?

2010-07-22T04:53:17Z

For a monoid $M$ and a subset $S$ of $M$, define the syntactic congruence $\equiv_S$ of $S$ as the least congruence on $M$ that saturates $S$, i.e. : $$u \equiv_S v \Leftrightarrow (\forall x, y)[xuy \in S \leftrightarrow xvy \in S].$$

Now define the Nerode equivalence as the following right congruence : $$u \sim_S v \Leftrightarrow (\forall x)[ux \in S \leftrightarrow vx \in S].$$

Let $[u]_\equiv$ be the equivalence class of $u$ with respect to $\equiv_S$ and $[u]_\sim$ with respect to $\sim_S$.

Now define $i_\equiv (n)$ to be the number of different $[u]_\equiv$ for $u$ of size $n$.

Define $i_\sim(n)$ in a similar fashion.

Now the question is, how do the two $i$ functions relate ?

For instance, a standard theorem says that $i_\sim(n)$ is bounded by a constant whenever $i_\equiv(n)$ is, and reciprocally. Is there any other result in this trend?

Answer by Michaël for $2$-variable segment of FO over ordered, finite structures

2011-04-20T21:33:14Z

It is not the case. As an example, the following paper:

Kouck´y, M., Lautemann, C., Poloczek, S., Th´erien, D.: Circuit lower bounds via Ehrenfeucht-Fraiss´e games, 2006.

shows that, over words, FO[+, $\times$] with 2 variables is equivalent to AC$^0$ with linear size circuits --- while FO[+, $\times$] is equivalent to the whole class AC$^0$.

Those two classes are known to differ (S. Chaudhuri and J. Radhakrishnan: Deterministic restrictions in circuit complexity, 1996).

Answer by Michaël for 'Closure' of CFLs under complementation and intersection

2011-01-10T15:43:46Z

Would An infinite hierarchy of intersections of context-free languages (Liu Weiner 1973) answer your question? They prove that the intersection of $k$ CFL forms a class strictly contained in the intersection of $k +1$ CFL.

Vocabulary on monoid periodicity

2010-07-17T02:53:47Z

I'm learning about periodic languages, and I'm confused over the vocabulary used to describe the periodicity of (syntactic) monoids.

If I understand correctly, a monoid M is periodic if : $$(\forall m \in M)(\exists i \neq j)[m^i = m^j],$$ and it is aperiodic if : $$(\exists k)(\forall m \in M)[m^k = m^{k+1}],$$ and then an aperiodic monoid is periodic. Where does that bizarre vocabulary come from?

And in the same vein, what would be the book you'd recommend on monoids and semigroups?

Thank you.

Answer by Michaël for Which recursively-defined predicates can be expressed in Presburger Arithmetic?

2010-09-05T14:44:02Z

Presburger Arithmetic (over the naturals) describes exactly the semi-linear sets. A set ($\subseteq \mathbb{N}^k$) is linear if it can be expressed as $$L(\vec c, P=\{\vec{p_1}, \ldots, \vec{p_n}\}) = \{ \vec c + \sum_{i=1}^pc_i\vec{p_i} \;|\; c_i \in \mathbb{N}\}.$$

A set is semi-linear if it can be expressed as a finite union of linear sets. One can deduce a few techniques from this characterization (due to Ginsburg & Spanier).

To what extent MSO = WS1S, when adding relations?

2010-07-18T00:02:04Z

Let me first clarify my definitions. For a word $w \in \Sigma^*$, with $\Sigma={a_1, \ldots, a_n}$, I define two structures: $${\mathbb{N}}(w) = \langle {\mathbb{N}}, <, Q_{a_1}, \ldots, Q_{a_n} \rangle,$$ and the more usual word model: $${\mathbb{N}^{\rm fin}}(w) = \langle \{0, \ldots, |w|-1\}, <, Q_{a_1}, \ldots, Q_{a_n} \rangle,$$ where $Q_{a_i} = \{p \;|\; w_p = a_i\}$.

Then WS1S is the set of second order formulas with models of the form ${\mathbb{N}}(w)$, with order, and for which second order quantification is limited to finite subsets of the domain. MSO is the set of second order formulas with models of the form ${\mathbb{N}^{\rm fin}}(w)$, with order.

The usual proof that REG = WS1S proves at the same time that MSO = WS1S. My question is then, for which first or second order relations can we keep this to be true?

For instance, if we add a unary predicate $E(X)$ which says that a (monadic) second order variable contains an even number of objects, we add no power, as $E(X)$ is expressible as "there exists $X_1$ and $X_2$ that partition $X$, in such a way that if an element is in $X_i$ the next one in $X$ is in $X_j$, $i \neq j$, and the first element of $X$ is in $X_1$ and the last is in $X_2$."

Now, if we add a predicate $|X| < |Y|$, then WS1S becomes undecidable (see Klaedtke & Ruess, 10.1.1.7.3029), while MSO stays trivially decidable.

Thank you.

Answer by Michaël for Most general formulation of Gödel's incompleteness theorems

2010-07-18T00:25:52Z

The general understanding is that if a system is expressive enough to do arithmetic (say, Robinson arithmetic) then Gödel's theorem applies. A computability view would be, if a system can represent all the computable functions, then Gödel's theorem applies. The crucial link here is that arithmetic is enough to represent all the computable functions.

This syllabus gives a great short proof of Gödel's theorem, and the introductory text could help.

Hope this helps.

Answer by Michaël for What is the relationship between "translation" and time complexity?

2010-07-17T23:13:42Z

A legit encoding would give two different codings for two different objects. The problem of, for instance, graph isomorphism only makes sense if one considers two isomorphic graphs to be different. There are tons of problems for which changing the encoding leads to a classification in a smaller complexity class. Take for example (Garey & Johnson, p. 159), LINEAR DIVISIBILITY, which is, given integers $a$ and $c$ the problem of answering $(\exists x)[ax +1|c]$. This problem is $\gamma$-complete, but trivially in P if the inputs are given in unary. G&J add "[The] supposed intractability [of LINEAR DIVISIBILITY] depends heavily on the convention that numbers be represented by strings having length logarithmic in their magnitudes."

You should in particular check the notion of "pseudo-polynomial time" and section 4.2 of Garey & Johnson.

Hope this helps.

Comment by Michaël

2011-08-04T13:52:04Z

Did you have a look to this recent blog post of Scott? scottaaronson.com/blog/?p=710

Comment by Michaël

2011-04-23T02:11:42Z

You're missing the crucial notion of <i>uniformity</i>: the computational power needed to generate the circuit for each input size. FO(all) (usually denoted FO[$\mathcal{N}$] or FO[$\mathfrak{Arb}$]) equals <i>non-uniform</i> AC$^0$, which includes non-decidable languages (for instance, any unary language is in AC$^0$). FO[+, $\times$] corresponds to a nicer (more realistic) notion of uniformity (namely, logtime-uniform). A nice survey on this topic is given by Schweikardt.

Comment by Michaël

2010-07-19T00:56:56Z

Oh, sorry. Though, it worked, didn't it? :-) I'll have a closer look to jsMath to know what are the do-s and don't-s. Thanks.