Sat, 3 Dec 1994 18:38:20 GMT

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) |

Newsgroups: | comp.compilers |

From: | rockwell@nova.umd.edu (Raul Deluth Miller) |

Keywords: | lex |

Organization: | University of Maryland University College |

References: | 94-11-137 94-12-021 |

Date: | Sat, 3 Dec 1994 18:38:20 GMT |

Jan-Peter de Ruiter:

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

*: 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.*

Or, more generally, you would have to take a step back and enumerate

some notions of structure, and the information required for such

classification.

*: This could perhaps be done by using a 'circular' approach,*

*: for instance like this:*

*:*

*: CCCCC*

*: CBBBC*

*: CBABC*

*: CBBBC*

*: CCCCC*

This is a fun example. Here's some interpretations:

(A) you're looking for an exact match.

-- easily implementable using a finite automata, but boring.

(B)

*: So in the expression "ABC", A, B and C are all regexps that*

*: describe properties of a 'circle' of text. These expressions*

*: themselves should be modified to be able to describe circular*

*: structures, and the relations between these circular expressions*

*: should be formalized in some way or other.*

So vague as to be useless. More specifically, describing an arbitrary

"circle" is not a problem for a finite automata -- like parenthesis

matching, it involves counting.

(C) Perhaps there's some sort of general "finite automata that can

make turns". Here, a circle might be a closed sequence involving four

right turns.

(D) Perhaps there's some sort of concept of "a restricted indefinite

automata that spawns finite automata." Here, you'd want to invent

some sort of concept of a rendevous of (e.g. 2) finite automata to

achieve anything meaningful. I suspect this would be turing

equivalent for the general case (where it can be thrown at arbitrarily

large regions of text).

(E) You could introduce the concept of a finite automata without

backtracking which is first used to transform the region of text in

one direction followed by a similar finite automata without

backtracking which is used to transform the region of text in some

other direction. Call this the "ledger" model.

(F) And then there's the whole field of cellular automata. (e.g. John

Horton Conway's game of "Life"). Perhaps define a class of cellular

automata which reduce the outer borders with each generation?

--

Raul D. Miller

<rockwell@nova.umd.edu>

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.