On 3/1/2013 2:51 AM, Rich Cooper wrote:
> From the bio, [Chetan Dube] was a Math Prof at NYU with a specialty
> in finite state automata before going commercial... (01)
> So I started thinking about FSA parsers, perhaps using a Turing-like stack (02)
If you allow finite-state machines to call one other, you get much
more expressive power. If they can make direct or indirect recursive
calls, you get the ability to express context-free grammars. Such
things are sometimes called recursive transition nets. (03)
If you add the option of storing and accessing data from global
storage (the storage is sometimes called registers, and the data
is often called features), you get some context-sensitive capability.
If your features are sufficiently complex, you get the full power
of a Turing machine. (04)
A recursive transition net with features is sometimes called
an augmented transition net. (05)
In any case, finite state machines + feature structures with support
for recursion are widely used in computational linguistics. Ron Kaplan
and his group at Xerox PARC developed them in great detail as a formal
system, but they can also be used very informally (i.e., typical hacks). (06)
And Kaplan's group left Xerox to form PowerSet, which was absorbed
into Microsoft's Bing. (07)
Summary: There is a continuum from Eliza-like hacks to highly
formal syntax and semantics. Variations of the same kinds of
technology can support any point along the continuum. (08)
John (09)
_________________________________________________________________
Message Archives: http://ontolog.cim3.net/forum/ontolog-forum/
Config Subscr: http://ontolog.cim3.net/mailman/listinfo/ontolog-forum/
Unsubscribe: mailto:ontolog-forum-leave@xxxxxxxxxxxxxxxx
Shared Files: http://ontolog.cim3.net/file/
Community Wiki: http://ontolog.cim3.net/wiki/
To join: http://ontolog.cim3.net/cgi-bin/wiki.pl?WikiHomePage#nid1J (010)
|