Re: Extending REG-EXP to 2-Dimension.

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

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