12.1376, Disc: How Do You Demonstrate Recursion?

[The LINGUIST Network]

LINGUIST List:  Vol-12-1376. Sat May 19 2001. ISSN: 1068-4875.

Subject: 12.1376, Disc: How Do You Demonstrate Recursion?

Moderators: Anthony Aristar, Wayne State U.<aristar at linguistlist.org>
            Helen Dry, Eastern Michigan U. <hdry at linguistlist.org>
            Andrew Carnie, U. of Arizona <carnie at linguistlist.org>

Reviews (reviews at linguistlist.org):
	Simin Karimi, U. of Arizona
	Terence Langendoen, U. of Arizona

Editors (linguist at linguistlist.org):
	Karen Milligan, WSU 		Naomi Ogasawara, EMU
	Lydia Grebenyova, EMU		Jody Huellmantel, WSU
	James Yuells, WSU		Michael Appleby, EMU
	Marie Klopfenstein, WSU		Ljuba Veselinova, Stockholm U.
	Heather Taylor-Loring, EMU	Dina Kapetangianni, EMU

Software: John Remmers, E. Michigan U. <remmers at emunix.emich.edu>
          Gayathri Sriram, E. Michigan U. <gayatri at linguistlist.org>

Home Page:  http://linguistlist.org/

The LINGUIST List is funded by Eastern Michigan University, Wayne
State University, and donations from subscribers and publishers.



Editor for this issue: Karen Milligan <karen at linguistlist.org>

=================================Directory=================================

1)
Date:  Fri, 18 May 2001 17:49:08 -0400
From:  Mark_Mandel at dragonsys.com
Subject:  Disc: How do you demonstrate recursion?

2)
Date:  Fri, 18 May 2001 17:51:02 -0400
From:  "Job M. van Zuijlen" <zuijlen at attglobal.net>
Subject:  Re: Disc: New: How do you demonstrate recursion?

-------------------------------- Message 1 -------------------------------

Date:  Fri, 18 May 2001 17:49:08 -0400
From:  Mark_Mandel at dragonsys.com
Subject:  Disc: How do you demonstrate recursion?

Dorothea Cogill <dcogill at metz.une.edu.au> wrote in LINGUIST List 12.1345:

>>>>>
What does it take for someone or something to show a grasp of recursive rules?

Assume you have a communication system in which some symbols stand for
actions (let's make those symbols the vowels A E I O & U, but they could be
anything you please), and other symbols stand for objects to which the
actions can be applied (let's make these symbols the consonants of the
alphabet - whatever).  Put two symbols in order, and they amount to a
command to perform that action on that object.  The correct order is set;
say it's ACTION + OBJECT, for example.  Then (for the symbols offered
above) a string like "A Q" is a command to perform action A on object Q;
throw a ball, for example, if A is  'throw' and Q is 'ball'.

     [...]

The question is - well, I guess there are two questions.
1. does your system possess recursion?  After all, if a sentence S is
ACTION + OBJECT, then two in a row can be written S-> S(S), which can be
expanded indefinitely  (I hope your computer is translating these symbols
correctly!).
<<<<<

I wouldn't call that recursion, but simply compounding. As I understand the
term, you don't have recursion until the output of an operation can serve
as the input to another instance of the same operation, whether directly or
via a chain of intervening operations. The system as described above has
just one rule:
     1:   action + object  =>  command
which by itself has no room for recursion. In CFG notation this would be
"command -> action object", or S -> V N if you like, but the first way I
wrote it shows "input" and "output" more clearly.

Now, suppose you issue the command "E A Q", where "E" means 'pretend, act
out', and the translation of this command is 'pretend to throw the ball,
act out throwing the ball'. *Then* you'll have recursion. We've added the
rule
     2:   command  =>  object
which allows a command to be used as an object in rule 1, creating the loop
that defines recursion. Of course, not all combinations are meaningful,
such as *"A A Q" 'throw the throwing of the ball'.

This may not be what you wanted to know about, but it seems to me to be
what your question purports to be about.

   Mark A. Mandel : Dragon Systems, a Lernout & Hauspie company
          Mark_Mandel at dragonsys.com : Senior Linguist
 320 Nevada St., Newton, MA 02460, USA : http://www.dragonsys.com


-------------------------------- Message 2 -------------------------------

Date:  Fri, 18 May 2001 17:51:02 -0400
From:  "Job M. van Zuijlen" <zuijlen at attglobal.net>
Subject:  Re: Disc: New: How do you demonstrate recursion?

The example you give does not count as recursion, I think.  But to
investigate that, you would first look at the kind of grammar that would
be able to generate sequences like "AQEP".  It seems that a simple
regular expression would be sufficient, for example,
([A,E,..,U][B,C,..,Z]*), which means one element from the first list
(the vowels), followed by one element from the second list (the
consonants), repeated indefinitely (indicated by the '*').  So endless
repetition does not necessarily require recursion.

Another way to look at this, is to see what kind of automaton you need
to recognize your language, and you will find that a finite-state
automaton will be sufficient.

A less technical way to look at your problem is to observe that each
pair can be generated independently, like when we perform a sequence of
tasks without any particular order.  For recursion to become necessary,
you need something more complicated.  For example, you're on the
telephone and then another call comes in, which you handle, and then you
go back to the first call.  This requires a "stack", you put the first
person on hold (put him/her on the stack), take the call from the second
person, and the "pop" the first person from the stack and continue your
conversation.  You can even imagine more elaborate scenario's.

I hope this helps.

Job van Zuijlen

---------------------------------------------------------------------------
LINGUIST List: Vol-12-1376