Induction question, help needed.  
Author Message
stegen123





PostPosted: 2003-9-24 13:19:00 Top

java-programmer, Induction question, help needed. Help needed on this question. Any help is appreciated. Thanks in
advance.

Given a binary string (i.e. a finite sequence of 0's and 1's) we
choose any two digit substring 01 and replace it by a string of the
form 100...0 using an arbitrary (but finite) number of zeros. Prove
by induction that this transformation can not be performed infinitely
many times, i.e. this sequence of transformations must terminate for
any input string.
 
gramlich





PostPosted: 2003-9-24 19:58:00 Top

java-programmer >> Induction question, help needed.
In article <email***@***.com>,
email***@***.com (Jack Smith) writes:
>Help needed on this question. Any help is appreciated. Thanks in
>advance.
>
>Given a binary string (i.e. a finite sequence of 0's and 1's) we
>choose any two digit substring 01 and replace it by a string of the
>form 100...0 using an arbitrary (but finite) number of zeros. Prove
>by induction that this transformation can not be performed infinitely
>many times, i.e. this sequence of transformations must terminate for
>any input string.

This is a well-known (solved) type of termination problem in string
rewriting, a subfield of term rewriting. Here are some related links:

term rewriting homepage:
http://rewriting.loria.fr/
journal paper (AAECC 2000) by Zantema/Geser on this topic:
pdf:
http://www.springerlink.com/app/home/content.asp?wasp=f83ebu4j807jtj4e67vl&referrer=contribution&format=2&page=1&pagecount=25
abstract:
http://www.springerlink.com/app/home/contribution.asp?wasp=1lbfddxhqncvtk6lwvtp&referrer=parent&backto=issue,1,5;journal,19,44;linkingpublicationresults,id:100499,1
conference paper (RTA 1995) on this topic:
http://www.informatik.uni-trier.de/~ley/db/conf/rta/rta95.html#ZantemaG95
technical report version (1994) from Zantema's homepage:
ftp://ftp.cs.ruu.nl/pub/RUU/CS/techreps/CS-1994/1994-44.ps.gz
Hans Zantema's homepage:
http://www.win.tue.nl/~hzantema/
Alfons Geser's homepage:
http://research.nianet.org/~geser/

Hope this helps,
Bernhard Gramlich.

========================================================================
Bernhard Gramlich Vienna University of Technology
e-mail: email***@***.com www: http://www.logic.at/staff/gramlich
========================================================================
--
========================================================================
Bernhard Gramlich Vienna University of Technology
e-mail: email***@***.com www: http://www.logic.at/staff/gramlich
========================================================================
 
Christopher Blunck





PostPosted: 2003-9-25 11:05:00 Top

java-programmer >> Induction question, help needed. On Tue, 23 Sep 2003 22:18:31 -0700, Jack Smith wrote:

> Help needed on this question. Any help is appreciated. Thanks in
> advance.
>
> Given a binary string (i.e. a finite sequence of 0's and 1's) we
> choose any two digit substring 01 and replace it by a string of the
> form 100...0 using an arbitrary (but finite) number of zeros. Prove
> by induction that this transformation can not be performed infinitely
> many times, i.e. this sequence of transformations must terminate for
> any input string.


Hey donkey-

Why'd don't you do one of two things:
- pick up a CS book and expend brain power to determine how to solve your
CS assignment
- reboot your computer, launch MS Windows, and switch to a major other than
computer science.


You brain dead idiots that mistakenly believe you can find solutions to your CS
assignments on usenet are the reason why our profession is filled with
dimwitted neandethrals.

Here's a quarter - go to your career center and switch majors to something
that will allow you to play XBox, PS2, or whatever the hell other gaming
system that you mistaked for "computer science".


People like you make me sick,
-c


 
 
stegen123





PostPosted: 2003-9-26 2:39:00 Top

java-programmer >> Induction question, help needed. Now I have been working on the question...and I decided to do
induction on the length of the binary string.

So for the base case x=0 or x=1...which obviously terminates.

then I assumed for k>=0 it terminates for all |x|<=k

Now I am trying to prove the Induction Step...but I am having trouble.


ANy hints on how I can prove this?? Or maybe I am performing induction
on the wrong property? Any help is appreciated. Thanks.
 
 
Bart Demoen





PostPosted: 2003-9-26 3:57:00 Top

java-programmer >> Induction question, help needed. Jack Smith wrote:

> Now I have been working on the question...and I decided to do
> induction on the length of the binary string.
>
> So for the base case x=0 or x=1...which obviously terminates.
>
> then I assumed for k>=0 it terminates for all |x|<=k
>
> Now I am trying to prove the Induction Step...but I am having trouble.
>
> ANy hints on how I can prove this?? Or maybe I am performing induction
> on the wrong property? Any help is appreciated. Thanks.

Try induction on the number of 1s in the string and prove also
that after a finite number of replacements, a 1 will show up at the
left (use the induction hypothesis for that)
if you chop off that leftmost 1, you have a string with one 1 less ...

Cheers

Bart Demoen

 
 
schigh





PostPosted: 2003-9-27 3:47:00 Top

java-programmer >> Induction question, help needed. "Christopher Blunck" <email***@***.com> wrote in message news:<email***@***.com>...
> On Tue, 23 Sep 2003 22:18:31 -0700, Jack Smith wrote:
>
> > Help needed on this question. Any help is appreciated. Thanks in
> > advance.
> >
> > Given a binary string (i.e. a finite sequence of 0's and 1's) we
> > choose any two digit substring 01 and replace it by a string of the
> > form 100...0 using an arbitrary (but finite) number of zeros. Prove
> > by induction that this transformation can not be performed infinitely
> > many times, i.e. this sequence of transformations must terminate for
> > any input string.
>
>
> Hey donkey-
>
> Why'd don't you do one of two things:
> - pick up a CS book and expend brain power to determine how to solve your
> CS assignment
> - reboot your computer, launch MS Windows, and switch to a major other than
> computer science.
>
>
> You brain dead idiots that mistakenly believe you can find solutions to your CS
> assignments on usenet are the reason why our profession is filled with
> dimwitted neandethrals.
>
> Here's a quarter - go to your career center and switch majors to something
> that will allow you to play XBox, PS2, or whatever the hell other gaming
> system that you mistaked for "computer science".
>
>
> People like you make me sick,
> -c


Why don't you tell us how you really feel.