User micha&#235;l - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T09:33:49Z http://mathoverflow.net/feeds/user/7687 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/32899/what-is-the-relation-between-the-number-syntactic-congruence-classes-and-the-num What is the relation between the number syntactic congruence classes, and the number of Nerode relation classes? Michaël 2010-07-22T04:53:17Z 2011-12-17T06:22:13Z <p>For a monoid $M$ and a subset $S$ of $M$, define the <i>syntactic congruence</i> $\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].$$</p> <p>Now define the <i>Nerode equivalence</i> as the following right congruence : $$u \sim_S v \Leftrightarrow (\forall x)[ux \in S \leftrightarrow vx \in S].$$</p> <p>Let $[u]_\equiv$ be the equivalence class of $u$ with respect to $\equiv_S$ and $[u]_\sim$ with respect to $\sim_S$.</p> <p>Now define $i_\equiv (n)$ to be the number of different $[u]_\equiv$ for $u$ of size $n$. </p> <p>Define $i_\sim(n)$ in a similar fashion.</p> <p>Now the question is, how do the two $i$ functions relate ?</p> <p>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?</p> http://mathoverflow.net/questions/62404/2-variable-segment-of-fo-over-ordered-finite-structures/62461#62461 Answer by Michaël for $2$-variable segment of FO over ordered, finite structures Michaël 2011-04-20T21:33:14Z 2011-04-20T22:01:49Z <p>It is not the case. As an example, the following paper:</p> <p>Kouck´y, M., Lautemann, C., Poloczek, S., Th´erien, D.: Circuit lower bounds via Ehrenfeucht-Fraiss´e games, 2006.</p> <p>shows that, over words, FO[+, $\times$] with 2 variables is equivalent to AC$^0$ with <i>linear size</i> circuits --- while FO[+, $\times$] is equivalent to the whole class AC$^0$.</p> <p>Those two classes are known to differ (S. Chaudhuri and J. Radhakrishnan: Deterministic restrictions in circuit complexity, 1996).</p> http://mathoverflow.net/questions/51657/closure-of-cfls-under-complementation-and-intersection/51665#51665 Answer by Michaël for 'Closure' of CFLs under complementation and intersection Michaël 2011-01-10T15:43:46Z 2011-01-10T15:43:46Z <p>Would <a href="http://www.springerlink.com/content/t1xk67013513016m/" rel="nofollow"><i>An infinite hierarchy of intersections of context-free languages</i></a> (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.</p> http://mathoverflow.net/questions/32253/vocabulary-on-monoid-periodicity Vocabulary on monoid periodicity Michaël 2010-07-17T02:53:47Z 2010-09-21T22:52:08Z <p>I'm learning about periodic languages, and I'm confused over the vocabulary used to describe the periodicity of (syntactic) monoids.</p> <p>If I understand correctly, a monoid M is <i>periodic</i> if : $$(\forall m \in M)(\exists i \neq j)[m^i = m^j],$$ and it is <i>aperiodic</i> 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?</p> <p>And in the same vein, what would be the book you'd recommend on monoids and semigroups?</p> <p>Thank you.</p> http://mathoverflow.net/questions/37777/which-recursively-defined-predicates-can-be-expressed-in-presburger-arithmetic/37795#37795 Answer by Michaël for Which recursively-defined predicates can be expressed in Presburger Arithmetic? Michaël 2010-09-05T14:44:02Z 2010-09-05T14:44:02Z <p>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}\}.$$</p> <p>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 &amp; Spanier).</p> http://mathoverflow.net/questions/32329/to-what-extent-mso-ws1s-when-adding-relations To what extent MSO = WS1S, when adding relations? Michaël 2010-07-18T00:02:04Z 2010-07-18T00:55:01Z <p>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}}, &lt;, Q_{a_1}, \ldots, Q_{a_n} \rangle,$$ and the more usual <i>word model</i>: $${\mathbb{N}^{\rm fin}}(w) = \langle \{0, \ldots, |w|-1\}, &lt;, Q_{a_1}, \ldots, Q_{a_n} \rangle,$$ where $Q_{a_i} = \{p \;|\; w_p = a_i\}$.</p> <p>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.</p> <p>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?</p> <p>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$."</p> <p>Now, if we add a predicate $|X| &lt; |Y|$, then WS1S becomes undecidable (see Klaedtke &amp; Ruess, 10.1.1.7.3029), while MSO stays trivially decidable.</p> <p>Thank you.</p> http://mathoverflow.net/questions/32318/most-general-formulation-of-godels-incompleteness-theorems/32331#32331 Answer by Michaël for Most general formulation of Gödel's incompleteness theorems Michaël 2010-07-18T00:25:52Z 2010-07-18T00:25:52Z <p>The general understanding is that if a system is expressive enough to do arithmetic (say, <a href="http://en.wikipedia.org/wiki/Robinson_arithmetic" rel="nofollow">Robinson arithmetic</a>) 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 <i>represent</i> all the computable functions.</p> <p>This <a href="http://www.math.ru.nl/~terwijn/publications/syllabus.pdf" rel="nofollow">syllabus</a> gives a great short proof of Gödel's theorem, and the introductory text could help.</p> <p>Hope this helps.</p> http://mathoverflow.net/questions/32320/what-is-the-relationship-between-translation-and-time-complexity/32325#32325 Answer by Michaël for What is the relationship between "translation" and time complexity? Michaël 2010-07-17T23:13:42Z 2010-07-17T23:13:42Z <p>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 &amp; 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&amp;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."</p> <p>You should in particular check the notion of "pseudo-polynomial time" and section 4.2 of Garey &amp; Johnson.</p> <p>Hope this helps.</p> http://mathoverflow.net/questions/72062/what-are-some-proofs-of-godels-theorem-which-are-essentially-different-from-th Comment by Michaël Michaël 2011-08-04T13:52:04Z 2011-08-04T13:52:04Z Did you have a look to this recent blog post of Scott? <a href="http://www.scottaaronson.com/blog/?p=710" rel="nofollow">scottaaronson.com/blog/?p=710</a> http://mathoverflow.net/questions/62404/2-variable-segment-of-fo-over-ordered-finite-structures/62461#62461 Comment by Michaël Michaël 2011-04-23T02:11:42Z 2011-04-23T02:11:42Z You're missing the crucial notion of &lt;i&gt;uniformity&lt;/i&gt;: the computational power needed to generate the circuit for each input size. FO(all) (usually denoted FO[$\mathcal{N}$] or FO[$\mathfrak{Arb}$]) equals &lt;i&gt;non-uniform&lt;/i&gt; 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. http://mathoverflow.net/questions/32329/to-what-extent-mso-ws1s-when-adding-relations Comment by Michaël Michaël 2010-07-19T00:56:56Z 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.