Let C[n] = {x | x is a binary number that is multiple of n}. Show
that for each n >= 1, the language C[n] is regular.
         Thanks in advance

--- In comp-sci-theory@yahoogroups.com, "manzur1986" <manzur1986@...>
wrote:
>
> 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 Clarke. Finally, I want to ask: Is there any
> answers to "Introduction to Theory of Computation" by M. Sipser".
>                Thanks to the author of this forum and to the others
>

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
encounters. Someone might solve it. :)

Best regards,
Ching-Lueh

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 just looking for solutions to your
homework
problems here, then it is not the group.

manzur1986 wrote:
> I forgot to ask: Which fields of CS has interesting research problems?
>
>
>
>
>
> Yahoo! Groups Links
>
>
>
>

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 Clarke. Finally, I want to ask: Is there any
answers to "Introduction to Theory of Computation" by M. Sipser".
                Thanks to the author of this forum and to the others

--- In comp-sci-theory@yahoogroups.com, "bugz_podder"
<bugz_podder@...> wrote:
>
> 2DFAs are equivalent in computing power to DFAs.  Thus any non-
regular
> language in P would do.  How about 0^n 1^n
>

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
other methods).
Since any fixed DFA has about O(n^2) configurations where n is the
input length, its language lies in DTIME(n^2) by considering an O
(n^2) TM simulator of the 2DFA. Or maybe DTIME(n^3) or something
like that, as the simulator may need extra book-keeping.
Then apply the time hierarchy theorem.

Best,
Ching-Lueh

> --- In comp-sci-theory@yahoogroups.com, "npeterson808080"
> <npeterson808080@> wrote:
> >
> > A friend asked me this question, and I wasn't sure how to go
about
> it. Any help would be
> > appreciated!:
> >
> > Prove that there is a language in P that is not recognizable by
a 2DFA.*
> >
> > *A 2DFA (two-headed finite automaton) a deterministic finite
> automaton that has two read-
> > only, bidirectional heads that start at the left-hand end of the
> input tape and can be
> > independently controlled to move in either direction. The tape
of a
> 2DFA is finitea nd is just
> > large enough to contain the input plus two additional blank tape
> cells, one on the left-hand
> > end and one on the right-hand end, that serve as delimiters. A
2DFA
> accepts its input by
> > entering a special accept state.
> >
>

2DFAs are equivalent in computing power to DFAs.  Thus any non-regular
language in P would do.  How about 0^n 1^n

--- In comp-sci-theory@yahoogroups.com, "npeterson808080"
<npeterson808080@...> wrote:
>
> A friend asked me this question, and I wasn't sure how to go about
it. Any help would be
> appreciated!:
>
> Prove that there is a language in P that is not recognizable by a 2DFA.*
>
> *A 2DFA (two-headed finite automaton) a deterministic finite
automaton that has two read-
> only, bidirectional heads that start at the left-hand end of the
input tape and can be
> independently controlled to move in either direction. The tape of a
2DFA is finitea nd is just
> large enough to contain the input plus two additional blank tape
cells, one on the left-hand
> end and one on the right-hand end, that serve as delimiters. A 2DFA
accepts its input by
> entering a special accept state.
>

goodbye...

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 sleeping and showering. Does anyone have any
suggestions, or is anyone looking for a roommate? Thanks!

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 science and related fields.

Why not have a try?
http://wikicfp.com/cfp/call?conference=computation%20theory
http://wikicfp.com/cfp/call?conference=programming%20languages

What's special with WikiCFP ?
- You can have your own customized CFP list.
- It's easy to share your list with others.
- You can organize your list by sorting on various fields.
- You can browse CFPs with respect to categories.
- You can search CFPs by title, location or category.
- There are many other useful features.

I sincerely hope this new site will be helpful to you and the TCS
community.

Best wishes,

Evie

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        : /triangular forms/perm3600.per
   Uploaded by : pehoushek1 <pehoushek1@...>
   Description :  a random permutation over one thru 3600.  can quality of random
permutations be estimnated?    its my first one ever made...

You can access this file at the URL:
http://groups.yahoo.com/group/comp-sci-theory/files/triangular%20forms/perm3600.\
per

To learn more about file sharing for your group, please visit:
http://help.yahoo.com/help/us/groups/files

Regards,

pehoushek1 <pehoushek1@...>

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 foundation appears
  valuable.  i am hoping for
  someone somewhere in america,
  who would possibly be interested
  in the follow up efforts of a
  strong pure valuable foundation.
  perhaps billion dollar bill.

  these are four major message caveats:

  i apologize for not writing clearly,
  in easy to translate triangular form.
  (hopefully some of this comes
   across as humorous, mike!
   i put real effort into
   most of my comp sci
   theory messages.)

  i also apologize for using punctuation,
  for more difficult machine translations.

  the balanced usage parentheses
  is for subordinate topics.
  those may be deleted, skipped over,
  or otherwise ignored
   ( doing so
     tends to allow most high level
     meanings to remain intact
     ( such would be easy to do,
       if someone could invent
       a way to skip over parentheses )).

  an attempt was made to make
  bibliographic references
  as relevant as possible,
  plus as few as possible.

  sincerely, with mild desperation,
  for scholarly sanctuary,
  daniel

  in the following message,
  the title theorem is given,
  explained, and four
  valuable applications
  are introduced.

  there are only a couple
  of bibliography references.

++++ The Self Evidence Theorem ++++

   Every monotone formula is self evident.

   (discovered 1997, published 2002,
    introduction to qspace,
    quantified boolean formulas workshop,
    cincinnati ohio.
    (parenthesis may be skipped over
     without loss of substance)
    ( in english, "the qbfs problem"
      is translated as:

       "the all solvable
         logic problems "problem" "

       (which is also a logic problem)

       some logicians may call that one
       "the omega problem",
       since the number of problems
       solved would be large,
       or, really Big Big Big. )

     the Italians honored the paper,
     by placing it "In the beginning",
     on Page One, the place often
     reserved for enlightenment.

     Page One is a real subtle hint,
     intended for value purposes.
      high quality abstracts are
      often page one papers, and
      may often contain gems.
      (irregardless of the rest
       of the conference).

      brief biographical lamentation,
      minor whines for number shortage relief:

      I have done ten years of
      followup work on this theory.
      I also have more results, including
      a method for conversions:
        from cnf to a set of 2cnfs,
      bery helpful for solving pspace problems.
      I have been seeking somewhere,
      hopefully in america, but I
      would be willing to travel
      to canada or new york,
      to explain the results.
      am looking for shelter place,
      and perhaps food, in trade
      for scholarship efforts...

      since number supplys on bank disks
      are too complitated, too tiny,
      and too hard, to add,
      perhaps from using too many
      negations on peoples bank accounts,
      then food and shelter sanctuary
      would be quite fine.

      in the old days of america, there
      were places called universitys, where
      scholars were allowed to study,
      even if they were american. )

  the monotheorem, the short name
  for the above self evidence theorem,
  has many valuable applications:
    formulas with zero negations
    (either implicit or explicit),
    are easily decidable in place
    ( leads to perfectly clear and
      coherent transmission of ideas ).
    easy and clear means:
      in linear time, modulo
      log factors, with zero
      "externality" needed for
      knowing the truth
      of such sentences.

  many self evident language sentences
  may be easily constructed,
  for valuable teaching translations.

    use the plus transform
    to remove negations.

    senator kennedy gives excellent examples
    of sentences filled with negations.

    to vastly increase longterm understanding,
    and educational value,
    just use step by step
    transformation,
    searching for negative words,
    deleting those, and performing
    mild grammar editting,
    to discover hidden sentences
    with much greater value.

  ++++ four major applications
       of The Self Evidence Theorem ++++

  after positively transformed,
  many sentences become superb material...
  four areas are mentioned:

1 for vastly improved judicial procedures
   (where clouds of negativity have
    completely slimed that
    entire industry, perhaps
    from way too many
    slimey prisons for
    catching people
    with number shortage
    problems),
2 for clear diplomatic communications
   (where long distant communications
    with too much negativity
     become confused... may sometimes
    lead to the arrival of the stupid men,
    often with guns, who do not know the language,
    to be the boss; stupid men often
    try to set up stupid governments,
    that nobody is able to understand),
3 for fundamental principles
   ( sample principle:
       the stupid men
       shall allow scholarly freedom
       in bangladesh...

     thou shall allow freedom

     is very nearly a translation
     of the first amendmen
     of the american Constitution ),
4 for good definitions
   ( good word definitions
     shall be purely good...

     this principle is a relative principle to
       thou shall not commit adultery
       to a peoples language...
     for improved government words:
     life, sentence, judge, book, please,
     should all be good words please. ),
  and mabye other various obscure topics
     (with clear commy then for example,
      the americans may cease bombing the british,
      in afghanistan.
      prince harry is still be alive.)
  which are often desired to be made clear,
   such as whether men with guns
   should be allowed in school.
  by many monotheorists everywhere.

  ( parenthetical side problem for logicians:

      how to discuss complex topics
      in an easy triangular formulation,
      if you are not allowed to use
      the triangular formulation?

      case study example:
       how would you easily explain the
       self evidence theorem of formal logic,
       in every known slavic dialect?
       does anyone know a way?

       in polish pig farmer dialects,
       when one polish policeman says:
         "you must not speak
          clearly around here."
       then what should you do,
       in order to communicate clearly,
       with most polish pig farmers? )

  ++++ end of four major applications ++++

  +++ explained ++++
  the quantified  boolean form of self evidence:
  whenever the logic formula is entirely positive,
  plug in TRUE for "exists" quantifiers,
  and FALSE for "forall" quantifiers.
  then evaluate normally, to obtain
  the truth value of the formula.
  for further study,
  please see the
  generalized positive integer
  quantifier reference,
  by an Italian.
  it was really great stuff.
  ++++ end of explained ++++
  ++++ end of self evidwnce theorem ++++

  ++++ almost at end of message ++++
  +++ footnotes +++
  other scholarly footnotes
  and bibliography references:

  The Self Evidence Theorem
  (2002, cincinnati ohio,
   international conference,
   the important portion
   was managed by italians.

  there is a close relative of
  the evidence theorem, called
   The Equivalence Theorem:
   (same conference, same paper. )

   The number of satisfying assignments
   of every boolean formula
   is equivalent to (identical in quantity)
   the number of valid quantifications.

  this too is a very valuable theorem,
  although calling it the omega theorem
  would be a bit much (egolog).

  some major league follow through results,
  that boolean theorem was also discovered in 1997.
  the equivalence theorem was later generalized.
  over positive finite integer fields,
  using generalized existential quantification.
  by some italians, i believe.
  sorry, i have had noplace and
  nowhere, no office,
  to keep that valuable reference handy,
  as would any logician who has
  an office with a place
  to put stuff.

  ++ alpha skip search algorithm

  the alphabet problem
    subsequence of a sequence
    general pattern matching
    string matching
    identitys of subprograms

  the solution was published in 1997, in france.
  best possible way to do string match,
  over the set of average cases.


  the algorithm was called Alpha Skip Search.
  the method is the optimal average case
  way to do subsequences of sequences,
  on any finite alphabet,
  with size two or more.
  with t. lecroq, france.

  the method was first commercially used,
  in golden common lisp,
  cambridge, MA, 1985,
  with the gmacs edittor,
  a compact well written
  word processor,
  with absolutely zero mouse bugs.

  in 1997, when alpha skip was first published,
  i was attempting to obtain money.
  i hoped to be allowed to do
  further studys in america.
  (for logic work in america.
   but that did not succeed
   back then, so i escaped briefly
   over to europe, hoping for
   an improved scholarly
   environment there.)
  +++ end footnotes +++


      
________________________________________________________________________________\
____
Shape Yahoo! in your own image.  Join our Network Research Panel today!  
http://surveylink.yahoo.com/gmrs/yahoo_panel_invite.asp?a=7

Hi Mike,
As far as I am concerned, these triangular emails are spam.
Cheers,
Piotr

Daniel Pehoushek wrote:

>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 calm
>communication
>and control.
>civilians
>lament.
>
>
>see the discussion below,
>judge for yourselves.
>btw, in discussions
>with my family,
>i call myself
>"the best logician in the country".
>
>so please forgive any apparent
>egolog about the title,
>and ignore the basic
>theorems already
>presented here,
>just as you
>have been
>doing.
>
>maps, maps, maps, towards the future,
>are nay as simple as we all hope.
>good competent tools are needed.
>the triangular form and the
>plus transformation, for
>removing many negations
>from complex issues,
>are valuable tools.
>also, quadratic
>intelligence
>structures,
>extremely
>valuable,
>period.
>
>as the best logician in my country,
>part of my job is to help people
>who must use computers at work.
>very johnny hard job.
>
>a study of conceptual structures,
>valuable for computers, people,
>future man relations machine,
>in draft but justified form,
>is provided underneath.
>the method needs work,
>but very promising
>for the language
>community needs.
>
>general issues to compare include:
>compare partial meritocracy
>with total idiocracy,
>as government form.
>which is better.
>
>daniel
>
>
>+++ merit values discussion +++
>
>  what is merit for truth scholarship worth?
>   theorems within the theorys of truths
>    by the best logician in the country
>     seeking food shelter clothing
>      in trade for valued knowhow
>
>
>gifts to country requesting trade
>the best logician in the country
>subjective position description
>completed well complexity done
>uses new triangular invention
>discussion of value question
>logician fighting for right
>fair value jobs allocation
>metaphysical equivalences
>chemical lobotomy threat
>from by retarded people
>subjects contents pure
>kidnap beaten ransoms
>where are sanctuarys
>false imprisonments
>abstract valuation
>home food clothes
>spoon fork knife
>trade agreement
>transportation
>knowledge for
>major goods
>friendship
>requested
>
>
> what is merit for truth scholarship worth?
>
>   merit means rewards for jobs well done
>    places to continue delivery of goods
>    participation in benefits of goods
>    jobs well done implys gifts given
>     presentations made clear to man
>      complexity problems made clean
>       language independent formula
>        translation easy by scribe
>         more longlasting values
>
>
>   next what is truth scholarship
>    truths made sure pure simpler
>     explanation available widely
>      understanding of principles
>       foundations of sure truths
>        for building civilization
>         groups of formal reasons
>          knowledge of principles
>           equivalent sanity sets
>            pure structure simple
>             brevitys appreciated
>              the study of reason
>               the plus transform
>                removals of minus
>                 works of numbers
>                  how to do truth
>                   proofs designs
>                    small is good
>                     step by step
>                      progression
>                       steadiness
>                        validitys
>                         theorems
>                          theorys
>                           lemmas
>                            forms
>                             sets
>                              how
>                               do
>                                u
>
>   worth worthy worthiness valuations
>    positive relation to civilization
>     presume trustworthy constructive
>      sincere noble high learned good
>       merit equals goods trust value
>        good ideals beliefs moralitys
>         for know how you trades this
>          measures of qualitys valued
>           honorable true equivalence
>            some thing equals another
>             abstract dimensional map
>              through shallow symbols
>               desirables equivalence
>                same one equals other
>                 concepts similaritys
>                  one dimension truth
>                   same among several
>                    known trade value
>                     given for trades
>                      same values for
>                       property value
>                        this for that
>                         num for item
>                          tis for dat
>                           here gimme
>                            identitys
>                             abstract
>                              numbers
>                               equals
>                                ideal
>                                 same
>                                  val
>                                   to
>                                    u
>
>+++ end merit scholar discussion +++
>
>what is the question
>
>the best logician in the country,
>thats me, the author of the above,
>is seeking shelter sanctuary and support,
>from retarded men with weapons, from
>negatively designed credit systems,
>from being imprisoned by retards,
>in places where force chemicals
>are used by low intelligences
>upon higher ones.  the tools
>they have are keys locks
>weapons vehicles force
>low education cells
>lack of repsect
>dirty prisons
>ignorance
>plagues
>apathy
>
>oxygen deprivation
> is major suspect
>  environmental
>   condition
>suggest a snorkel
> on the roof top
>  for pregnant
>   women here
>
>have many good theorems
> of fundamental nature
>  plus good practical
>   results for
>    teachers
>
>please i need
> places to
>  stuffs
>
>++++
>
>
>
>_______________________________________________________________________________\
_____
>Need a vacation? Get great deals
>to amazing places on Yahoo! Travel.
>http://travel.yahoo.com/
>
>
>
>Yahoo! Groups Links
>
>
>
>
>

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 calm
communication
and control.
civilians
lament.


see the discussion below,
judge for yourselves.
btw, in discussions
with my family,
i call myself
"the best logician in the country".

so please forgive any apparent
egolog about the title,
and ignore the basic
theorems already
presented here,
just as you
have been
doing.

maps, maps, maps, towards the future,
are nay as simple as we all hope.
good competent tools are needed.
the triangular form and the
plus transformation, for
removing many negations
from complex issues,
are valuable tools.
also, quadratic
intelligence
structures,
extremely
valuable,
period.

as the best logician in my country,
part of my job is to help people
who must use computers at work.
very johnny hard job.

a study of conceptual structures,
valuable for computers, people,
future man relations machine,
in draft but justified form,
is provided underneath.
the method needs work,
but very promising
for the language
community needs.

general issues to compare include:
compare partial meritocracy
with total idiocracy,
as government form.
which is better.

daniel


+++ merit values discussion +++

   what is merit for truth scholarship worth?
    theorems within the theorys of truths
     by the best logician in the country
      seeking food shelter clothing
       in trade for valued knowhow


gifts to country requesting trade
the best logician in the country
subjective position description
completed well complexity done
uses new triangular invention
discussion of value question
logician fighting for right
fair value jobs allocation
metaphysical equivalences
chemical lobotomy threat
from by retarded people
subjects contents pure
kidnap beaten ransoms
where are sanctuarys
false imprisonments
abstract valuation
home food clothes
spoon fork knife
trade agreement
transportation
knowledge for
major goods
friendship
requested


  what is merit for truth scholarship worth?

    merit means rewards for jobs well done
     places to continue delivery of goods
     participation in benefits of goods
     jobs well done implys gifts given
      presentations made clear to man
       complexity problems made clean
        language independent formula
         translation easy by scribe
          more longlasting values


    next what is truth scholarship
     truths made sure pure simpler
      explanation available widely
       understanding of principles
        foundations of sure truths
         for building civilization
          groups of formal reasons
           knowledge of principles
            equivalent sanity sets
             pure structure simple
              brevitys appreciated
               the study of reason
                the plus transform
                 removals of minus
                  works of numbers
                   how to do truth
                    proofs designs
                     small is good
                      step by step
                       progression
                        steadiness
                         validitys
                          theorems
                           theorys
                            lemmas
                             forms
                              sets
                               how
                                do
                                 u

    worth worthy worthiness valuations
     positive relation to civilization
      presume trustworthy constructive
       sincere noble high learned good
        merit equals goods trust value
         good ideals beliefs moralitys
          for know how you trades this
           measures of qualitys valued
            honorable true equivalence
             some thing equals another
              abstract dimensional map
               through shallow symbols
                desirables equivalence
                 same one equals other
                  concepts similaritys
                   one dimension truth
                    same among several
                     known trade value
                      given for trades
                       same values for
                        property value
                         this for that
                          num for item
                           tis for dat
                            here gimme
                             identitys
                              abstract
                               numbers
                                equals
                                 ideal
                                  same
                                   val
                                    to
                                     u

+++ end merit scholar discussion +++

what is the question

the best logician in the country,
thats me, the author of the above,
is seeking shelter sanctuary and support,
from retarded men with weapons, from
negatively designed credit systems,
from being imprisoned by retards,
in places where force chemicals
are used by low intelligences
upon higher ones.  the tools
they have are keys locks
weapons vehicles force
low education cells
lack of repsect
dirty prisons
ignorance
plagues
apathy

oxygen deprivation
  is major suspect
   environmental
    condition
suggest a snorkel
  on the roof top
   for pregnant
    women here

have many good theorems
  of fundamental nature
   plus good practical
    results for
     teachers

please i need
  places to
   stuffs

++++



________________________________________________________________________________\
____
Need a vacation? Get great deals
to amazing places on Yahoo! Travel.
http://travel.yahoo.com/

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 government machines,
and the complexity of the contents
in any single triangular form is
bounded quadratically.
Very handy property.

Its close to a demonstration.  The idea
helps focus writing, and also makes
reading easier too, once acclimated.

The real subject I would love
to be discussing is hillberg:
The Twenty One Graph Theorems
were proven using a program
for converting pspace forms,
expressed as conjunctive
normal forms, into a set
of two cnfs.  But no one
in computer science seems
to have a clue how valuable
such conversions would be,
or what all the two cnfs,
would look similar to.

Could not get any american response
on the string matching either,
which indicates some severe
system problems, thus the
chosen topic for the
demonstration of
triangular
forms.

sincerely daniel

--- "Mike N. Christoff" <michael_christoff@...>
wrote:

> 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 to me. What is the purpose/benefit you
> see in these for
> yourself and the group?
>
> > competency notes for the analysts
> > for merit pays rewards chairs
> > may be done upon by the YES
> > on who best at giving the
> > final passed ordering
> > counts by committees
> > for skill levels
> > is good idea
> > the least
> > skilled
> > among
> > many
> > may
> > be
> > pleasant jocular booby lame prize
>
>
> For example, what is the meaning of the passage
> above?
>
>
> Thanks,
>
>
>
> -mike
>
>
> --- In comp-sci-theory@yahoogroups.com, "pehoushek1"
> <pehoushek1@...>
> wrote:
> >
> >
> >  on average pspace is
> >   probably quadratic
> >    the twenty one
> >     regular color
> >      theorems are
> >       good early
> >        evidence
> >
>
> [snip]
>
>




________________________________________________________________________________\
____
Choose the right car based on your needs.  Check out Yahoo! Autos new Car Finder
tool.
http://autos.yahoo.com/carfinder/

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 to me. What is the purpose/benefit you see in these for
yourself and the group?

> competency notes for the analysts
> for merit pays rewards chairs
> may be done upon by the YES
> on who best at giving the
> final passed ordering
> counts by committees
> for skill levels
> is good idea
> the least
> skilled
> among
> many
> may
> be
> pleasant jocular booby lame prize


For example, what is the meaning of the passage above?


Thanks,



-mike


--- In comp-sci-theory@yahoogroups.com, "pehoushek1" <pehoushek1@...>
wrote:
>
>
>  on average pspace is
>   probably quadratic
>    the twenty one
>     regular color
>      theorems are
>       good early
>        evidence
>

[snip]

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
     presented in
      simplified
       form

  triangular forms
  translation is
  also easy too
  to any other
  languages
  perhaps

+++++++++++++++++++++++++++++++++++

  off we go to see the wizard
  into triangular form we go
  complex ideas presented
  in simplest available
  quadratic formulas
  with most lines
  smaller than
  previous
  lines

  +++++++++++++++++++++++++++++++++++++

  issue comparison trees
  these may be called
  more than formally
  the trees of good
  good governing
  an art form
  reasoning
  decently
  simply
  good

// tish note which name is more formal
// may be debated  sometimes longer
// may seem more formal however
// clear and  short has
// fairly good claim


  where the top ten  or top N  issues
  all given as positively said forms
  goal of orderly sorted estimation
  through weights votes and studys
  the procedural idea is smooth
  where for actual sort effort
  which issue is least valued
  in future dropping purpose


  good good
  when sorted
  top ten agendas
  gives leaders clues
  to the important issues


  parliamentary trades of
   top ten agendas
    for perusal
     for study
      for plan
       is good
  eventually formally pass
   the top ten agenda
    on to Governors
     completion
      ceremonys
       properly
        for the
         ending
          good

  +++ Voting Organization +++

  with very superbly organized voting
   one hundred issues may be sorted
    with just eight hundred votes
     into single comparison tree
      however beginners should
       start with ten issues
        a fixed sized limit
         on agenda sizes or
          number of issues
           helps prevent
            thrashings
  with poorly organized comparison voting
   one hundred issues may require as many
    as five thousand comparison votes
     top ten issues are handled even
      with poorly organized
       comparison votes
        worrys are few
         when isssues
          are few


  the suggested comparison metric
      between any two issues:

      When the first issue is
        More Important
      than the second issue,
        the vote is YES.

  only YES votes really need
  to be counted when doing
  two issue comparisons
  total of members
  who are present
  is tallied
  with YES
  votes



  competency notes for the analysts
  for merit pays rewards chairs
  may be done upon by the YES
  on who best at giving the
  final passed ordering
  counts by committees
  for skill levels
  is good idea
  the least
  skilled
  among
  many
  may
  be
  pleasant jocular booby lame prize



  very ideally only
   issue placement
    among existing
     set of issues
      with only lg
       comparisons
        the final
         ordering
          votes
    are real nitpickers
    leaders who
    studied knuth
    sorting chapter
    have great skill


  when starting up
   trees of good
    long session
     is expected
  in the extreme case
   issue importance
    grows larger as
     more examined
  then number of comparison
   votes may grow too
    equalling near N
     the size of set
      too many times
       then long
        sessions


  my main suggestion for large N ordering
   is that somewhat random comparisons
    be the most useful operation
     upon new issues for judding
  who chooses issue pairs to compare
   would be the parliament leader
    votes may be quick easy sure
     final formal order passage
      session closure operation


  Weightd voting, where some business
  or industry wants a vote, is done
  through lobbying.  I am nay against
  gifts for attention services.  Those
  were standard for a long time.  But
  precisely how to do weighted voting
  is quite messy.  Gifts should always
  be accepted, but the outcome is
  surely  nay gauranteed. Punctuation
  remains in this messy topic.


  who thankfully recieves agenda lists
  possibly subsets of main complex
  yay still in the given order
  many ministerial positions
  presidential positions
  ambassador positions
  business positions
  general scholars
  utility leaders
  school boards
  citys mayors
  governors
  editors
  good

  smaller regions and territorys
  may reorder the trees of good
  contributing to nations list
  skilled civilian solutions
  some issues found missing
  number shortage problems
  big deal next sessions
  tree merge operations
  are underknown about
  very plausible idea
  region by region
  in clockwisely
  methodolgy
  good good

  so Issue Comparison Trees are really important
  although this discussion is somewhat shallow
  the possible depths of triangular forms
  may adjust over time as skills grow

  +++ End Introduction to Trees of Good +++

  ++++ remaining contents being design ++++

  Treating Issues as a data structure,
  there are seven discussions:

    How Many Issues
    What is logN
    Comparison Operation
    Adding an issue
    Moving an issue
    Issue Identity
    Dropping an issue

  ++++ end remaining contents ++++

  +++ How many issues +++

  how many trees is
  closely related to
  the number of issues

  With N issues use at most O(logN) trees.
  O(logN) means some constant, such as two,
  times the log of N.  However please note
  that the big oh notation was not actually
  designed for heavy use with logarithms.
  maintaining sufficiently small N
  is an issue formulation item.
  to remove duplication items
  using discovery procedures
  the plus transform helps
  purify the sentences
  for title managers
  improved ability
  is the result
  translations
  are likely
  as well
  good

  ++ quality issue form

  positively stated issues are normal form
   there are formal reasons for positively
    stated issues to be most preferred.
     issue duplication is overwhelming
      one sample to illuminate efforts
       may be immigration reform bill
        preferred to invasion reforms
         for much more pleasant issue
          although understanding the
           flipsides may be present

  high quality is given with clear simple
   positively stated issues and titles
    coherent knowledge books  orderly
     quality normal summary reasoning
      the plus transform useful good
       for more pleasant formulation
        sincere savings of mentality
         the simple facts once done
          the results are good for
           leadership planning
  issues with negative words
   cause way too much
    headache anyway
     also confused
      way to lose
       nay good

  ++ lgN name duplications limit

  how many duplications
   among the good trees
    is for human design
     some small number
      of general items

  this truly is pure theory
   that needs illumination
    more than this here is
     here is where lgN
      is very useful
       for designers
        generally
         a small
          is lgN
           good

  issues names in more than one place
  these may be common type of issues
  nay too many though where types
  are such as funding staffing
  as few of those as possible
  typical departmental stuff
  reflection and sanity item
   for when one department
    dominates parliament
     then all others
      tend to suffer
       thrashingness
  common department headings
   may be well known already
    should be done rarely
     with principles then
      sixteen departments
       doing the same job
        would be humorous
// for the david david show

  ++ discovery process

  the discovery process
  may do compares with
  the least issue
  many many time
  After deciding which tree,
  then the design point of view,
  the process point of view,
  the most important thing is
  what issue is least important.
  in fully developed designs
  the least issue may be
  removed by something
  more important.

  which tree the issue goes,
  is identity screening

  the issue tree size helps
  to define small numbers
  the use of lgN is good
  valuable smallness is
  for cabinet positions
  how many departments
  how many committees
  any small numbers


  ++ the final product

  given then to the leadership view,
  the need to know valuable issues
  which the parliaments all over
  have done mighty collective
  effort at figuring out.
  often only top issues
  with ignorance of
  mighty sorting
  large efforts
  good good
  good

  +++ End How many trees +++

  +++ What is logN +++

  logN

  The log function is studied briefly in high school.
  The natural log uses base e, 2.7something,
  is the mathematicians favorite.  Base two
  is easy, and good enough for government work,
  lgN is very useful for providing small nums.


  the number of bits in base two
  as lgN is the shorthand for
  log base two of N samples:
  N=16, lgN = 4, 2^4 =16.
  N=32, lgN = 5, 2^5 =32.
  ...
  N=128, lgN = 7.

  given the lgN limit then the tree method says
  that 128 issues may be formed into at most
  seven issue comparison trees for order
  for some limitations on complexity

  each tree is fairly easy to handle
   which issue goes into which tree
    is an identity discovery and
     screening procedure.
  after some skills are well developed, issue
   identity may become easy and well known
    to long time members of parliaments.

  +++ End What is logN +++

  +++  The Comparison Operator +++

  "More Important"  is the favored comparison.
  There may be funding comparisons too,
  but those are not entirely the same
  as "More Important".

  For example, just because some issue
  in a department recieves the least
  amount of funding, does nay mean
  an issue drops off when a
  More Important  issue
  becomes apparent.

  Funding votes are somewhat valuable, but,
  the ordering that leadership needs most
  is the "More Important" issue ordering.
  Could have words such as Significance
  or some other good thesaurus word
  from a word master.  Since I torched
  my thesaurus last year, well...
  perhaps I should nay
  have done that.

  The Truth about Leaders is that large
   More Important comparison trees,
    after significant examinations,
     hard for leaders to create.
  leaders may add many good suggestions
   however the bulk of the efforts are
    by a large group of knowledgeable
     people in concerted organization

  With properly designed sorting procedures,
  issue thrashing may be much easier to avoid.

  +++ End Comparison Operator +++

  +++ Adding an Issue +++

  Presuming an issue tree is too full,
   when a new issue is added, it must
    be clearly  More Important  than
     the least issue,  because the
      least issue shall be dropped.

  There are several procedures
   about dropped issues, but,
    mainly, dropped means other
     issues are fairly clearly
      more important for leaders.

  +++ End Adding an Issue +++

  +++ Moving An Issue +++

  Motions to move an issue to a different tree
  should be rare; those may be more common
  with a new issue than with an old issue.

  Such motions have large effect on major
  government departments.  New issues
  may be moved around twice.  Twice
  is an arbitray small constant.

  +++ End Moving An Issue +++

  +++ Identity Of an issue +++

  discovery process of
  screening an issue, or,
  which tree does it go into.
  Formulation of the issue in
  a completely positive wording
  helps a great deal in identity.

  is some new issue identical
  to some presently or previously
  known issue, but stated differently,
  is nay an easy or trivial operation.

  nitpicks about the new way of saying
  older issues a more clear formation
  and description.  issue renaming
  is for good identity operation.
  "the right to choose life"
  may be well known sample

  at first it may seem strange
  but all lowercase, with
  zero punctuation,
  appears best at
  formulations
  triangular
  simplest

  as for details on is some new issue
  the same as some old dropped issue,
  hmmm. good luck.
  That area of logic is called Equality
  and is surprisingly difficult.

  As for which tree an issue goes into,
  out of lgN, that too is an art.

  the data structure is fairly new
  hopefully skilled people shall
  develop it further than here

  +++ End Identity of an issue +++

  +++ Dropping an Issue +++

  to avoid much thrashing
  least important issues
  tend to get dropped
  from common agenda


  when the agenda list is rather old
  and fairly stable, but large,
  then issue dropping is very
  necessary for clear good
  actions and prioritys.


  when longtime issues finally get dropped,
  there are definitely some ceremonys
  and procedures, perhaps wine party
  those are small things unknown by
  most of civilization saying bye
  to an old unimportant friend


  dropped issues also go into the Identity
   screening book, for future reference,
    and for scholarly digging.

  reclaimations of resources from
   dropped issues are also
    important procedures.
  when to do that, how fast,
   who should be informed,
    reconsiderations,
     et cetera.

  For instance, when the former leader
  of the Senate says some issue
  is very important, then he
  may know whereof he speaks.
  Hopefully these changes in
  procedure may make such
  issues easier to address,
  with less thrashing around.

  +++ End Dropping an Issue +++

  +++++++++++++++++++++++++++++++++++++
  deleteable footnotes

  +++ One Hundred Days Problem +++
  footnote on this file:
  this is not the main topic,
  but the topic does belong to parliaments.

  Time Space issue about parliaments:
   One Hundred Days
  This is the well known Newt Estimate
  of effectiveness of a parliament.
  Why it is only one hundred days
  is unknown, but could be the bugs
  in the imported surveillance devices.
  Possibly with better design, parliaments
  may be effective for much longer duration.

  In any case, parliaments should try to
  have  some fairly good plans going in.

  My suggestion is they try to provide
  good solid leadership agendas that may
  then be spread out amongst leaders.
  +++ End One Hundred Days Problem +++
  +++ egolog, footnotes +++
  Often, even businesses have such prioritys,
  as a fundamental part of the business plan.

  Utilitys may too have specialized
  Issue Comparison Trees.

  As for familys, churches, schools,
  well, if they want to learn how
  the effective government works,
  they may adopt some if they wish,
  but I am not so bold as to say
  those shall... such may be
  good parenting materials.
  +++ end egolog +++

+++ presidents request +++

the truth is the president
was also somewhat concerned
about struggles with agendas
among generating priority sets

+++ end presidents request +++

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 my messages
  i hardly see them
  for some unknown
  or misguided
  reasoning

  so how good is triangular form
  for simpler presentation
  of high value thoughts

  for theoreticians
  triangular form
  considerations
  our americans
  three colors
  somewhat
  encoded
  due to
  heat

  forgive if off topic
  but other posts on
  theory topics are
  recieving little
  positive reply
  so heres a
  flaming
  topic

  could antilove colors
  be artificially
  created thru
  poor color
  usages
  inthe
  dark

  before explaining antilove
  first of all many people
  may understand those
  components already
  but what should
  be done about
  the issue
  solution
  should
  given
  red
  be

  nostalgia of one red cherry
  would do major repairs
  upon diagnosis below
  one red flasher was
  old clearly visble
  in the dark long
  ago with zero
  assault upon
  flag love

  +++ onward to the issue +++

  is the following a "computed" thing
  or just a two decade olden day
  poor decision unnoticed by US

  negative construction assault
  upon civilian love of country
  presume an innocent country
  with love of its flag
  people and nation

  how to "hate" the love
  until it disappears
  what art of war
  is this thing

  first of all the colors are
  very recognizable colors
  even in complete dark
  the flag colors art

  now choose some class of vehicles
  that hardly any citizen loves
  whose color was formerly one
  say a single red cherry one
  then when overseas create
  really cheap tricolored
  replacement cherrys
  for unloved cars
  over the heads
  of some mens
  but realy
  cheap

  now then those colors
  used in the darkness
  in low intelligence
  assaults repeated
  upon civilians
  what effect
  on country
  love then
  happens

  is antilove computable
  or was that idea
  just from some
  psychologys
  department

  the psychological warfare
  is fairly clear and wide
  something done sooner
  should be than later
  solution one red
  cherry in dark
  is fine fine
  answer old





________________________________________________________________________________\
____
Sick sense of humor? Visit Yahoo! TV's
Comedy with an Edge to see what's on, when.
http://tv.yahoo.com/collections/222

hi theoreticians.

  heres a new informa form
  recently discovered
  using very little
  punctuations,
  translation
  is easy to
  languages
  normally
  for man
  kind

  the triangular message form
  of message construction
  has multiple features
  what do you think?
  tends to focus
  both writers
  and readers
  seamless
  reading
  speeds

  the general idea is an agreement between
  the writers and readers of triangulars
  that the deep idea under discussion
  within one single passage of text
  has some line by line tendency
  to reduce in complexity with
  each step in the triangle
  is perhaps valuable for
  translation of many
  difficult ideas
  with limitted
  resources
  to play
  with

  since the recent sublinear
  simple string matching
  via alpha skip search
  did not generate
  too much debate
  though mostly
  how to do it
  was unknown
  as O(n/m)
  lets try
  a newer
  topic

  how about conversion from medium sized cnf to set of 2cnfs
  is a complexity topic made simple of any value these days
  could such deeply fundamental computational algorithms
  be adequately discussed using a fairly small alphabet
  with comprehendable words placed in sensible lines
  then what forms would expositions of pspaces take
  hmm  maybe this topic could be leading somewhere
  as each deep portion of a pspace is explained
  in some simple well known form such as 2cnf
  then each remaining piece of the pspace is
  revealed also in well known formulations
  in a step by step method of simplify
  where the time needed to understand
  the entire solution of the pspaces
  is perhaps tringular within given
  initial logical descriptions
  peeling two cnf layer after
  two cnf layer one by one
  until the entire space
  of initial the logic
  is made obviously
  to many who know
  whatsa 2cnf doc
  questions begs
  how many are
  triangles
  needed

  anyway the hillberg equations were actually used
  to prove twenty one regular graph color theorems
  previously posted on this mail list.  each of
  those theorems was harder than the original
  four color planar graph theorem, and each
  required several hours of time on an old
  dead pc.  would love to get some money
  for such works as alpha solution or
  medium sized omega theory problem
  answers;  with near zero replys
  is difficult to find anyone
  with some bank number on
  disk for sharing supply
  for food or shelters.
  perhaps though with
  steady generation
  of major results
  someone in my
  country will
  support my
  efforts.

  by the way the subtle hints in the above discussion
  are that most pspacey things are decomposable in a
  roughly quadratic space of 2cnf expositions.
  could be a major result eh? even for just
  medium sized pspacey things, quadratic
  formal expositions would be valuable.
  at least, as part of the two week
  theoretical computer science
  doctoral degree program.

  sincerely daniel

  ps
  if powdered soap on the ocean south of arizona
  to reduce surface tension and increase clouds
  has been succeeding very well then other
  locations near mountain regions
  may be added to the list
  to restore snowpacks
  around the world
  while some are
  able to do
  airlifts
  of soap
  locals
  cool
  way

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 me an email and I'll
provide all the details. Just be sure to make all cheques out
to 'Michael Christoff'... ;)


Cheers,

-mike

--- In comp-sci-theory@yahoogroups.com, Keith Alexander <kalex23@...>
wrote:
>
> 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 group for
> something other than what it was intended. Keep up the good work!
>
>     BTW, how come I'm not seeing any more posts about how I can get
a
> Master's or PhD in Computer Science in two weeks without ever
setting
> foot in a classroom????
> :)
>
> Keith
>
> --
> "There's a fine line between
> 'hobby' and 'mental illness'."
>
> Dave Barry
>

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 group for
something other than what it was intended. Keep up the good work!

     BTW, how come I'm not seeing any more posts about how I can get a
Master's or PhD in Computer Science in two weeks without ever setting
foot in a classroom????
:)

Keith

--
"There's a fine line between
'hobby' and 'mental illness'."

Dave Barry

You've been banned. Goodbye.

--- In comp-sci-theory@yahoogroups.com, Cycles Studies
<cyclesstudies53@...> wrote:
>
> They are giving away a 2007- 2008 membership to cycles
> magazine at
> http://techsignal@.../register.htm In addition,
> I'm told that if you registered
> for the 2006- 2007 membership that they are extending
> it and you don't have to
> re-register. Anthony
>
>
>
>
________________________________________________________________________________\
____
> Boardwalk for $500? In 2007? Ha! Play Monopoly Here and Now (it's
updated for today's economy) at Yahoo! Games.
> http://get.games.yahoo.com/proddesc?gamekey=monopolyherenow
>

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 able to use small alphabets
has some different applications than
you would normally think of.

While reading words and word recognition
cover a fairly large area of usages,
there are some others, too, where
matching strings may be useful.

1 Genes analysis for better vegetables
   in inclement weather ... uses the
   small alphabet in genes (is that
   four letters?)

2 Wumpus hunting on networks.

Can theoreticians list any others?

+++ +++ +++

How about two dimensions?

All the above are using one dimensional
string matching.  Is there such a thing
as two dimensional string matching?
hmmm... whats in a picture... hmmm
corners of objects could be similar to
primitive letters in an alphabet,
perhaps.

+++

Of course, all the above is much
different from conversion of any
cnf to a set of twocnfs.
Does anyone want to discuss uses for
that one?  Its only really useful
for solving medium sized
pspacey thingys...

anyway,
sincerely Daniel


PS
Below is a recapitulation of
three levels of BigOh plus almost
how to do string matching.


> > (ie. when m is superlogarithmic in n), in general
>
> 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 programs whose names... )
>
> So I am sure the m term should be
> included for those who know BigOh.
>
> Since string matching is a valued
> information theory topic, there
> are several levels to regard, for
> added job security for theorists :)
>
> So how are these levels of Big Oh:
>
>  O( n/m )
>  Executive Summary BigOh:
>  ignoring lesser contributing
>  addition terms... while making
>  the main lead term very clear.
>
>  O( n/m + m )
>  Theory of Summary BigOh:
>  where independent plus terms
>  are always included so they
>  may be analyzed;  as when m,
>  the pattern size, is near to
>  the square root of n.
>
>  Question begger says:
>  In what order are terms?
>  Decreasing terms is a
>  good canonical approach,
>  which helps greatly with:
>
>  Then theres the logs. Oh my.
>  O((n/m + m)*(log base A of m))
>
>  Theory of Logs BigOh:
>
>  For publishing papers,
>  log factors do count alot.
>  So when log factors count,
>  try to use base two, or
>  base e, or some smallest
>  available base that is
>  not a problem variable.
>
>  Since lgm is reasonably close
>  to log base A of m, then:
>    O((n/m + m)*lgm)
>  is much preferable than
>  introducing another variable
>  such as A the alphabet size,
>  into the analysis.
>
>  For program designers, A is
>  quite important. Every skip
>  location collects a small
>  piece of the text, with size
>  log base A of m, for lookup
>  in the pattern structure...
>
>  With though BigOh, try to not
>  include extra variables...
>
>  So do you like these three BigOhs:
>    Executive Summary  BigOh
>    Theory of Summary  BigOh
>    Theory of Logtimes BigOh
>    with decreasing terms as
>    one of the general rules.
>
>>
>> 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"   is  text size, could be very large.
>> "m"   is  pattern size, could be large.
>>
>> "A"   is  finite alphabet size, two or more.
>> log m is  log base A of m.
>>
>> In Alpha Skip Search, the text is
>> skipped through in chunks the size
>> of the pattern, which gives n/m
>> average performance on random text.
>> The question is about logm, and
>> the pre and postprocessing on pattern.
>>
>>
>> Preprocessing requires:   m * (log m)
>>
>> Main processing does  n/m  skips,
>> with  (log m)  average work per skip,
>> for an O( n/m  * logm ).
>>
>> Postprocessing requires cleanup
>> of the pattern data structre,
>> which is same or less work as
>> preprocessing.
>>


      
________________________________________________________________________________\
____
Shape Yahoo! in your own image.  Join our Network Research Panel today!  
http://surveylink.yahoo.com/gmrs/yahoo_panel_invite.asp?a=7

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,
Ching-Lueh

--- In comp-sci-theory@yahoogroups.com, "pehoushek1"
<pehoushek1@...> wrote:
>
>
>  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"   is  text size, could be very large.
>  "m"   is  pattern size, could be large.
>
>  "A"   is  finite alphabet size, two or more.
>  log m is  log base A of m.
>
>  In Alpha Skip Search, the text is
>  skipped through in chunks the size
>  of the pattern, which gives n/m
>  average performance on random text.
>  The question is about logm, and
>  the pre and postprocessing on pattern.
>
>
>  Preprocessing requires:   m * (log m)
>
>  Main processing does  n/m  skips,
>  with  (log m)  average work per skip,
>  for an O( n/m  * logm ).
>
>  Postprocessing requires cleanup
>  of the pattern data structre,
>  which is same or less work as
>  preprocessing.
>
>  So the random average work is
>    O( logm * ( m + n/m ) )
>
>  +++
>
>    The nitty questions are
>    what may be reduced from
>      O( logm * ( m + n/m ) )?
>
>  log base A of m  is very small.
>  But when A is size two, with large m,
>  one may wish to count it.
>
>  If you are the type who removes
>  log factors from big Oh,
>  then what remains is
>     O( m + n/m ).
>
>  Now, often m is much less than n.
>  For an extreme example, n could be
>  as large as everything thats ever
>  been written onto disks, in ascii
>  characters, while m may be only
>  one chapter of one book...
>
>  Could m be dropped, for the result of
>  O( n/m ) as the stated average work
>  for random string matching?
>
>  Tesh note:
>  Worst cases with this method
>  have texts and patterns with
>  alphabet size that is "essentially"
>  close to one, or very nonrandom,
>  and are no better than KMP or BoyerMoore.
>
>  Sincerely Daniel.
>
>  PS
>
>  Brief history of Alpha Skip Search method:
>  Discovered 1980, first algorithm course.
>  First commercial availability in
>  Golden Common Lisp, in middle 1980s.
>  Published 1997 with T. Lecroq of France,
>  when I tried, and failed, to make money
>  on my work...
>

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 mentioned that n/A^m is the expected number of matches. That is
true. Indeed, the expectation
E[number of matches]
= \sum_{k\geq 1} Pr[there are exactly k matches] * k
\geq \sum{k\geq 1} Pr[there are exactly k matches]
= Pr[a match occurs],
So that the expected number of matches is also an upper bound on the
probability that a match occurs. :)

Best,
Ching-Lueh

--- In comp-sci-theory@yahoogroups.com, r95922079@... wrote:
>
> > 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 other characters?
> >
> > I don't have much clue for the problem for now. The only
observation
> > that I have made is that, when m is super-logarithmic
> > in n, then we can almost surely output ``no, the pattern does not
> > appear in the text.'' The reason is that, when the pattern P or
the
> > text T is chosen uniformly at random (from {0,1}^m or {0,1}^n
> > respectively), the probability that P matches T at any given
index i
> > is exactly 1/A^m, assuming m \le n. By the union bound, the
> > probability that the pattern appears in T at all is at most
n*1/A^m,
> > which is o(1) when m is superlogarithmic in n.
>
> 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 random variables
>
> I(i) = 1, a match occurs at position i
>         0, o.w.
>
> Then the n*1/A^m you derived is in fact the expected number of
matches
> between the two strings. Unfortunately, even when this expectation
is o(1)
> (ie. when m is superlogarithmic in n), in general one can't claim
that no
> matches occur "for almost sure", since the tail probability is not
bounded.
>
> In a model where the characters X[1...n] of the text string are
chosen
> independently uniformly at random, we may let r.v. Y be the number
of matches,
> and define r.v. Z(i) = E[Y | X(1),...,X(i)]. Then the sequence Z
(1),...,Z(n)
> forms a Doob martingale, and thus we may apply the Azuma-Hoeffding
inequality
> to obtain Pr{ |Y - E[Y]| >= t } <= 2exp(-t^2/2nm^2). Note that
this is not a
> asymptotic result, but is true for all n and m.
>
> An immediate observation is that, IF this bound is tight, then
chance of
> matches may increase as n grows, even though m is superlogarithmic
in n
> and the expected number of matches is o(1).
>
> Best,
> ericpony
>
> >
> > Thank you for providing such an interesting new topic. :)
> >
> > Best,
> > Ching-Lueh
> >
> > --- In comp-sci-theory@yahoogroups.com, "pehoushek1"
> > <pehoushek1@> wrote:
> >>
> >>
> >> 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"   is  text size, could be very large.
> >> "m"   is  pattern size, could be large.
> >>
> >> "A"   is  finite alphabet size, two or more.
> >> log m is  log base A of m.
> >>
> >> In Alpha Skip Search, the text is
> >> skipped through in chunks the size
> >> of the pattern, which gives n/m
> >> average performance on random text.
> >> The question is about logm, and
> >> the pre and postprocessing on pattern.
> >>
> >>
> >> Preprocessing requires:   m * (log m)
> >>
> >> Main processing does  n/m  skips,
> >> with  (log m)  average work per skip,
> >> for an O( n/m  * logm ).
> >>
> >> Postprocessing requires cleanup
> >> of the pattern data structre,
> >> which is same or less work as
> >> preprocessing.
> >>
> >> So the random average work is
> >>   O( logm * ( m + n/m ) )
> >>
> >> +++
> >>
> >>   The nitty questions are
> >>   what may be reduced from
> >>     O( logm * ( m + n/m ) )?
> >>
> >> log base A of m  is very small.
> >> But when A is size two, with large m,
> >> one may wish to count it.
> >>
> >> If you are the type who removes
> >> log factors from big Oh,
> >> then what remains is
> >>    O( m + n/m ).
> >>
> >> Now, often m is much less than n.
> >> For an extreme example, n could be
> >> as large as everything thats ever
> >> been written onto disks, in ascii
> >> characters, while m may be only
> >> one chapter of one book...
> >>
> >> Could m be dropped, for the result of
> >> O( n/m ) as the stated average work
> >> for random string matching?
> >>
> >> Tesh note:
> >> Worst cases with this method
> >> have texts and patterns with
> >> alphabet size that is "essentially"
> >> close to one, or very nonrandom,
> >> and are no better than KMP or BoyerMoore.
> >>
> >> Sincerely Daniel.
>

> (ie. when m is superlogarithmic in n), in general

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 programs whose names... )

So I am sure the m term should be
included for those who know BigOh.

Since string matching is a valued
information theory topic, there
are several levels to regard, for
added job security for theorists :)

So how are these levels of Big Oh:

  O( n/m )
  Executive Summary BigOh:
  ignoring lesser contributing
  addition terms... while making
  the main lead term very clear.

  O( n/m + m )
  Theory of Summary BigOh:
  where independent plus terms
  are always included so they
  may be analyzed;  as when m,
  the pattern size, is near to
  the square root of n.

  Question begger says:
  In what order are terms?
  Decreasing terms is a
  good canonical approach,
  which helps greatly with:

  Then theres the logs. Oh my.
  O((n/m + m)*(log base A of m))

  Theory of Logs BigOh:

  For publishing papers,
  log factors do count alot.
  So when log factors count,
  try to use base two, or
  base e, or some smallest
  available base that is
  not a problem variable.

  Since lgm is reasonably close
  to log base A of m, then:
    O((n/m + m)*lgm)
  is much preferable than
  introducing another variable
  such as A the alphabet size,
  into the analysis.

  For program designers, A is
  quite important. Every skip
  location collects a small
  piece of the text, with size
  log base A of m, for lookup
  in the pattern structure...

  With though BigOh, try to not
  include extra variables...

  So do you like these three BigOhs:
    Executive Summary  BigOh
    Theory of Summary  BigOh
    Theory of Logtimes BigOh
    with decreasing terms as
    one of the general rules.

  Sincerely Daniel

--- r95922079@... wrote:

> > 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 other characters?
> >
> > I don't have much clue for the problem for now.
> The only observation
> > that I have made is that, when m is
> super-logarithmic
> > in n, then we can almost surely output ``no, the
> pattern does not
> > appear in the text.'' The reason is that, when the
> pattern P or the
> > text T is chosen uniformly at random (from {0,1}^m
> or {0,1}^n
> > respectively), the probability that P matches T at
> any given index i
> > is exactly 1/A^m, assuming m \le n. By the union
> bound, the
> > probability that the pattern appears in T at all
> is at most n*1/A^m,
> > which is o(1) when m is superlogarithmic in n.
>
> 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 random variables
>
> I(i) = 1, a match occurs at position i
>         0, o.w.
>
> Then the n*1/A^m you derived is in fact the expected
> number of matches
> between the two strings. Unfortunately, even when
> this expectation is o(1)
> (ie. when m is superlogarithmic in n), in general
> one can't claim that no
> matches occur "for almost sure", since the tail
> probability is not bounded.
>
> In a model where the characters X[1...n] of the text
> string are chosen
> independently uniformly at random, we may let r.v. Y
> be the number of matches,
> and define r.v. Z(i) = E[Y | X(1),...,X(i)]. Then
> the sequence Z(1),...,Z(n)
> forms a Doob martingale, and thus we may apply the
> Azuma-Hoeffding inequality
> to obtain Pr{ |Y - E[Y]| >= t } <= 2exp(-t^2/2nm^2).
> Note that this is not a
> asymptotic result, but is true for all n and m.
>
> An immediate observation is that, IF this bound is
> tight, then chance of
> matches may increase as n grows, even though m is
> superlogarithmic in n
> and the expected number of matches is o(1).
>
> Best,
> ericpony
>
> >
> > Thank you for providing such an interesting new
> topic. :)
> >
> > Best,
> > Ching-Lueh
> >
> > --- In comp-sci-theory@yahoogroups.com,
> "pehoushek1"
> > <pehoushek1@...> wrote:
> >>
> >>
> >> 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"   is  text size, could be very large.
> >> "m"   is  pattern size, could be large.
> >>
> >> "A"   is  finite alphabet size, two or more.
> >> log m is  log base A of m.
> >>
> >> In Alpha Skip Search, the text is
> >> skipped through in chunks the size
> >> of the pattern, which gives n/m
> >> average performance on random text.
> >> The question is about logm, and
> >> the pre and postprocessing on pattern.
> >>
> >>
> >> Preprocessing requires:   m * (log m)
> >>
> >> Main processing does  n/m  skips,
> >> with  (log m)  average work per skip,
> >> for an O( n/m  * logm ).
> >>
> >> Postprocessing requires cleanup
> >> of the pattern data structre,
> >> which is same or less work as
> >> preprocessing.
> >>
> >> So the random average work is
> >>   O( logm * ( m + n/m ) )
> >>
> >> +++
> >>
> >>   The nitty questions are
> >>   what may be reduced from
> >>     O( logm * ( m + n/m ) )?
> >>
> >> log base A of m  is very small.
> >> But when A is size two, with large m,
> >> one may wish to count it.
> >>
> >> If you are the type who removes
> >> log factors from big Oh,
> >> then what remains is
> >>    O( m + n/m ).
> >>
> >> Now, often m is much less than n.
> >> For an extreme example, n could be
> >> as large as everything thats ever
> >> been written onto disks, in ascii
> >> characters, while m may be only
> >> one chapter of one book...
> >>
> >> Could m be dropped, for the result of
> >> O( n/m ) as the stated average work
> >> for random string matching?
> >>
> >> Tesh note:
> >> Worst cases with this method
> >> have texts and patterns with
> >> alphabet size that is "essentially"
> >> close to one, or very nonrandom,
> >> and are no better than KMP or BoyerMoore.
> >>
> >> Sincerely Daniel.
>
>




________________________________________________________________________________\
____
Building a website is a piece of cake. Yahoo! Small Business gives you all the
tools to get online.
http://smallbusiness.yahoo.com/webhosting

> 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 other characters?
>
> I don't have much clue for the problem for now. The only observation
> that I have made is that, when m is super-logarithmic
> in n, then we can almost surely output ``no, the pattern does not
> appear in the text.'' The reason is that, when the pattern P or the
> text T is chosen uniformly at random (from {0,1}^m or {0,1}^n
> respectively), the probability that P matches T at any given index i
> is exactly 1/A^m, assuming m \le n. By the union bound, the
> probability that the pattern appears in T at all is at most n*1/A^m,
> which is o(1) when m is superlogarithmic in n.

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 random variables

I(i) = 1, a match occurs at position i
         0, o.w.

Then the n*1/A^m you derived is in fact the expected number of matches
between the two strings. Unfortunately, even when this expectation is o(1)
(ie. when m is superlogarithmic in n), in general one can't claim that no
matches occur "for almost sure", since the tail probability is not bounded.

In a model where the characters X[1...n] of the text string are chosen
independently uniformly at random, we may let r.v. Y be the number of matches,
and define r.v. Z(i) = E[Y | X(1),...,X(i)]. Then the sequence Z(1),...,Z(n)
forms a Doob martingale, and thus we may apply the Azuma-Hoeffding inequality
to obtain Pr{ |Y - E[Y]| >= t } <= 2exp(-t^2/2nm^2). Note that this is not a
asymptotic result, but is true for all n and m.

An immediate observation is that, IF this bound is tight, then chance of
matches may increase as n grows, even though m is superlogarithmic in n
and the expected number of matches is o(1).

Best,
ericpony

>
> Thank you for providing such an interesting new topic. :)
>
> Best,
> Ching-Lueh
>
> --- In comp-sci-theory@yahoogroups.com, "pehoushek1"
> <pehoushek1@...> wrote:
>>
>>
>> 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"   is  text size, could be very large.
>> "m"   is  pattern size, could be large.
>>
>> "A"   is  finite alphabet size, two or more.
>> log m is  log base A of m.
>>
>> In Alpha Skip Search, the text is
>> skipped through in chunks the size
>> of the pattern, which gives n/m
>> average performance on random text.
>> The question is about logm, and
>> the pre and postprocessing on pattern.
>>
>>
>> Preprocessing requires:   m * (log m)
>>
>> Main processing does  n/m  skips,
>> with  (log m)  average work per skip,
>> for an O( n/m  * logm ).
>>
>> Postprocessing requires cleanup
>> of the pattern data structre,
>> which is same or less work as
>> preprocessing.
>>
>> So the random average work is
>>   O( logm * ( m + n/m ) )
>>
>> +++
>>
>>   The nitty questions are
>>   what may be reduced from
>>     O( logm * ( m + n/m ) )?
>>
>> log base A of m  is very small.
>> But when A is size two, with large m,
>> one may wish to count it.
>>
>> If you are the type who removes
>> log factors from big Oh,
>> then what remains is
>>    O( m + n/m ).
>>
>> Now, often m is much less than n.
>> For an extreme example, n could be
>> as large as everything thats ever
>> been written onto disks, in ascii
>> characters, while m may be only
>> one chapter of one book...
>>
>> Could m be dropped, for the result of
>> O( n/m ) as the stated average work
>> for random string matching?
>>
>> Tesh note:
>> Worst cases with this method
>> have texts and patterns with
>> alphabet size that is "essentially"
>> close to one, or very nonrandom,
>> and are no better than KMP or BoyerMoore.
>>
>> Sincerely Daniel.

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 other characters?

I don't have much clue for the problem for now. The only observation
that I have made is that, when m is super-logarithmic
in n, then we can almost surely output ``no, the pattern does not
appear in the text.'' The reason is that, when the pattern P or the
text T is chosen uniformly at random (from {0,1}^m or {0,1}^n
respectively), the probability that P matches T at any given index i
is exactly 1/A^m, assuming m \le n. By the union bound, the
probability that the pattern appears in T at all is at most n*1/A^m,
which is o(1) when m is superlogarithmic in n.

Thank you for providing such an interesting new topic. :)

Best,
Ching-Lueh

--- In comp-sci-theory@yahoogroups.com, "pehoushek1"
<pehoushek1@...> wrote:
>
>
>  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"   is  text size, could be very large.
>  "m"   is  pattern size, could be large.
>
>  "A"   is  finite alphabet size, two or more.
>  log m is  log base A of m.
>
>  In Alpha Skip Search, the text is
>  skipped through in chunks the size
>  of the pattern, which gives n/m
>  average performance on random text.
>  The question is about logm, and
>  the pre and postprocessing on pattern.
>
>
>  Preprocessing requires:   m * (log m)
>
>  Main processing does  n/m  skips,
>  with  (log m)  average work per skip,
>  for an O( n/m  * logm ).
>
>  Postprocessing requires cleanup
>  of the pattern data structre,
>  which is same or less work as
>  preprocessing.
>
>  So the random average work is
>    O( logm * ( m + n/m ) )
>
>  +++
>
>    The nitty questions are
>    what may be reduced from
>      O( logm * ( m + n/m ) )?
>
>  log base A of m  is very small.
>  But when A is size two, with large m,
>  one may wish to count it.
>
>  If you are the type who removes
>  log factors from big Oh,
>  then what remains is
>     O( m + n/m ).
>
>  Now, often m is much less than n.
>  For an extreme example, n could be
>  as large as everything thats ever
>  been written onto disks, in ascii
>  characters, while m may be only
>  one chapter of one book...
>
>  Could m be dropped, for the result of
>  O( n/m ) as the stated average work
>  for random string matching?
>
>  Tesh note:
>  Worst cases with this method
>  have texts and patterns with
>  alphabet size that is "essentially"
>  close to one, or very nonrandom,
>  and are no better than KMP or BoyerMoore.
>
>  Sincerely Daniel.
>
>  PS
>
>  Brief history of Alpha Skip Search method:
>  Discovered 1980, first algorithm course.
>  First commercial availability in
>  Golden Common Lisp, in middle 1980s.
>  Published 1997 with T. Lecroq of France,
>  when I tried, and failed, to make money
>  on my work...
>

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"   is  text size, could be very large.
  "m"   is  pattern size, could be large.

  "A"   is  finite alphabet size, two or more.
  log m is  log base A of m.

  In Alpha Skip Search, the text is
  skipped through in chunks the size
  of the pattern, which gives n/m
  average performance on random text.
  The question is about logm, and
  the pre and postprocessing on pattern.


  Preprocessing requires:   m * (log m)

  Main processing does  n/m  skips,
  with  (log m)  average work per skip,
  for an O( n/m  * logm ).

  Postprocessing requires cleanup
  of the pattern data structre,
  which is same or less work as
  preprocessing.

  So the random average work is
    O( logm * ( m + n/m ) )

  +++

    The nitty questions are
    what may be reduced from
      O( logm * ( m + n/m ) )?

  log base A of m  is very small.
  But when A is size two, with large m,
  one may wish to count it.

  If you are the type who removes
  log factors from big Oh,
  then what remains is
     O( m + n/m ).

  Now, often m is much less than n.
  For an extreme example, n could be
  as large as everything thats ever
  been written onto disks, in ascii
  characters, while m may be only
  one chapter of one book...

  Could m be dropped, for the result of
  O( n/m ) as the stated average work
  for random string matching?

  Tesh note:
  Worst cases with this method
  have texts and patterns with
  alphabet size that is "essentially"
  close to one, or very nonrandom,
  and are no better than KMP or BoyerMoore.

  Sincerely Daniel.

  PS

  Brief history of Alpha Skip Search method:
  Discovered 1980, first algorithm course.
  First commercial availability in
  Golden Common Lisp, in middle 1980s.
  Published 1997 with T. Lecroq of France,
  when I tried, and failed, to make money
  on my work...

--- In comp-sci-theory@yahoogroups.com, "Hatem Abd-Elghani"
<hatemghani@...> wrote:
>
> Hello
>
> Could somebody provide me with ideas about how to prove DSPACE(n) =/=
NP?
>

Suppose for contradiction that DSPACE(n)=NP. Then every language L \in
DSPACE(n^2) can be padded to yield a language L' \in DSPACE(n)=NP. But
L' \in NP would imply L \in NP, too. As a result, we have DSPACE(n^2)
\subseteq NP=DSPACE(n), contradicting the space hierarchy theorem.

Best,
Chang