Re: Extending REG-EXP to 2-Dimension.

pwk@eb.ele.tue.nl (Pieter Kuppens)
Mon, 5 Dec 1994 08:06:44 GMT

          From comp.compilers
Related articles
Extending REG-EXP to 2-Dimension. mosh@ramanujan.cs.albany.edu (1994-11-21)
Re: Extending REG-EXP to 2-Dimension. steve@cegelecproj.co.uk (1994-11-30)
Re: Extending REG-EXP to 2-Dimension. ruiter@ruls41.fsw.leidenuniv.nl (1994-12-01)
Re: Extending REG-EXP to 2-Dimension. rockwell@nova.umd.edu (1994-12-03)
Re: Extending REG-EXP to 2-Dimension. lloyd@kauri.vuw.ac.nz (1994-12-05)
Re: Extending REG-EXP to 2-Dimension. pwk@eb.ele.tue.nl (1994-12-05)
Re: Extending REG-EXP to 2-Dimension. steve@cegelecproj.co.uk (1994-12-05)
Re: Extending REG-EXP to 2-Dimension. bakul@netcom.com (1994-12-08)
| List of all articles for this month |
Newsgroups: comp.compilers
From: pwk@eb.ele.tue.nl (Pieter Kuppens)
Keywords: lex, DFA
Organization: Eindhoven University of Technology, The Netherlands
References: 94-11-137 94-12-021
Date: Mon, 5 Dec 1994 08:06:44 GMT

ruiter@ruls41.fsw.leidenuniv.nl (Jan-Peter de Ruiter) writes:


>[ Request for regexp systems that work on "boxes" of text ]


>This is a really hard problem that has been discussed once
>in the Icon newsgroup.


>As far as I know it has not been solved in any way. The problem
>is that you need to extend the notion of linearity (characters
>following other characters) in 2 dimensions.


>This could perhaps be done by using a 'circular' approach,
>for instance like this:


> CCCCC
> CBBBC
> CBABC
> CBBBC
> CCCCC


>I'd be interested if anyone has any comments or 'pointers'
>regarding this idea.


I have a small comment. If you would reduce this problem to the upper
right corner, it reminds me of the famous Tiling problem.


As we all know, Tiling is NP-complete.


I have to say I know a great deal more of NP-completeness than I know
of regular expressions and what to do with them in those situations.




Pieter
--

Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.