What may be ignored in big Oh notation? The average random case for string matching is the topic of the analysis. The relevant terms are n, m, A, logm: "n"...
Dear Daniel, By random string matching, do you mean that each character of the pattern and text string is picked uniformly at random and indepenedently from...
... Dear hatred, There is nothing unusual for a probability to be o(1) ;) However, your line of argument still has its merit. It is typical to set indicator...
... That is probably the key point. The m term may indeed be superlogarithmic ( examples are when searching for file fragments or fractions of well known...
Dear Ericpony, I derive the n/A^m this way: Pr[a match occurs] \leq \sum_{i} Pr[a match occurs at index i] (by the union bound) = \sum_{i} 1/A^m =n/A^m, You...
Dear Daniel, I did some google search and found this: ftp://reports.stanford.edu/pub/cstr/reports/cs/tr/77/629/CS-TR-77- 629.pdf Maybe it helps? Best, ...
All known usages of matching strings may be a fairly long list... however the O( n/m ) method is very different in flavor from O( n+m ) regexp match. And being...
Mike, You're so MEAN (smile)! No, really--it's good to see you're on top of things, and will come down quickly and mercilessly on folks who try to use this...
Thanks for the kudos Keith! I'm just glad to see the site is no longer the spam bin it became a few months back. As for the 2 week CS degrees--No problem! Send...
hi theoreticians. heres a new informa form recently discovered using very little punctuations, translation is easy to languages normally for man kind the...
three coloring problem this problem may soon become the most famous three color problem ever given to theory people. by the way if there are any responses to...
on average pspace is probably quadratic the twenty one regular color theorems are good early evidence see the draft below for a sketch of a complex idea ...
Hi Daniel. I'm a bit confused about what (specifically) your 'triangular' emails are all about. With no offence intended, the majority of it seems nonsensical...
Mike, Well, firstly, its a new communication form, with some very simple propertys. Its easy to translate to other languages, its also legible to some...
comp sci theory, how good is the triangular form for presenting abstract issues? as man machine relations become more developed, people need easier methods for...
dear comp sci theory, i have done ten years of followup work, using The Self Evidence Theorem of formal reason, as a primary foundation. please see if the...
Hello, This email message is a notification to let you know that a file has been uploaded to the Files area of the comp-sci-theory group. File :...
comp-sci-theory@yahoo...
Sep 4, 2007 8:13 pm
2695
Hi All, I would like to recommend a new web site, www.wikicfp.com, which could help you to organize and share "Calls for Papers" on theoretical computer...
So I missed the FOCS 2007 (in Providence, RI) deadline =\, and I'm trying to find a decent cheap hotel now. I don't plan on doing anything there except...
2DFAs are equivalent in computing power to DFAs. Thus any non-regular language in P would do. How about 0^n 1^n ... it. Any help would be ... automaton that...
... regular ... I think you are absolutely right---2DFAs are stronger than simple DFAs. :) I guess the problem may be solved this way (and there may be many ...
Hi! I'm a student, and I study Information Systems. But here I would discuss "Introduction to Theory of Computation" by M. Sipser and "Model checking" by...
Structural complexity theory and computational social choice theory are pretty cool. As for others, I don't know. Piotr PS. Okay... and seriously, if you are...
... Dear Manzur, Sometimes googling might help, but I don't know of a version of complete answers to that book. Maybe just post it here when a problem ...
This is exactly the type of thing that is not wanted on this group. This is not a homework answer database. Continue like this and you will be banned. Mike...
Hi, I've been lurking on this group for sometime now, and thought I'd better make a post. I have just started studying for a PhD at Durham University in the...
Having problems with message search?
Fill out this form to ensure your group is one of the first to be migrated to the new message search system.
