New answers tagged

4

NAUTY "colors" nodes with constant depth neighborhood canonical forms. Babai's new algo does likewise with log size neighborhoods. The kicker is that in a random graph the diameter is about log n, so you end up gobbling the whole thing. Definitely worth doing for sparse graphs, can really cut down the state space you need to search. Also when you have to ...


2

Isn't the solution a one-counter language? The succession of the domino's is easily seen as a finite state restriction. For the unequality of $u'$ and $v'$ you have to find a single position where these strings differ. Keep track of $|u'|-|v'|$ during computation on the stack. You just nondeterministically choose such a letter, on a position of the longest ...


0

I would like to add two books not found on the answers given up to now: Aaron Stump, Programming Language Foundations David Schmidt, Denotational Semantics: A Methodology for Language Development Stump's book is concise but very clear.


2

Writing Mathematics Donald E. Knuth, Tracy Larrabee, and Paul M. Roberts, "Mathematical Writing", 1989 (pdf)


2

I'm not sure what your question is. Tell me if I am mistaken. From what I understand: Given a subsequential transducer, you can easily transform it into your canonical form by replacing every transition $(q,a)\to (p,v)$ into a transition reading $a$ and producing nothing followed by a sequence of transitions reading nothing and producing $v$ one letter at a ...


3

All deterministic classes are (almost trivially) closed under complement: Given a deterministic TM $M$ for a language $L$, one obtains a deterministic TM for its complement by simply running $M$ and then "flipping" the answer. The machine runs in the same time and space asymptotically. By applying the same proof to the complement class, it follows that ...


2

Shaull already mentioned NL. ​ The same thing also applies to all super-logarithmic space classes. ​ The only other examples I can find for which I don't know of as-natural equivalent definitions from which closedness under complement trivially follows are: SAC and each of its positive levels and SZK .


7

Nonderministic Logspace (NL) is closed under complement. That is, $NL=coNL$. This non-trivial result is known as (or rather, is the consequence of) the Immerman–Szelepcsényi theorem.



Top 50 recent answers are included