1
$\begingroup$

Expanding on Question 79182 I am sure there must be an active area of research for deriving parameterised patterns. What I am looking for is something like - given the input AByyDABxxDMOO

the process returns the expansion rule(s) ⌽f(x)=ABxD and the expansion ⌽f(yy)⌽f(xx)MOO

Needless to say, what I am looking for handles recursive generation, such as..

ABaAByyDABxxDDMOO => ⌽f(a⌽f(yy)⌽f(xx))MOO

And multiple functions - not just the one as demonstrated here. I recognise that there are multiple correct results - so some sort of optimisation based on non-repetition, and parsimony would be really good.

While I can imagine that genetics and decryption methods may have some sort of approach to this, I do not know where to look - or even how to begin. I know that compression does some of this - but it's based upon positions and works 'from left to right'. I'm looking for something which is more like a grammar derivation.

Improve this question
$\endgroup$
3
  • $\begingroup$ A lot seems to depend on 1) which strings you want to apply this to: single strings? finite sets? infinite sets? are they completely random or do they satisfy certain patterns or are certain patterns more probable? 2) which functions and intermediate values you want to allow and 3) the cost of applying those functions. If all the functions can do is replace strings with strings, you're asking for the smallest context-free grammar of a certain type that can generate a given string (or set of strings). Relevant terms in the literature: context-free grammar learning / regular expression learning. $\endgroup$ Commented Apr 10, 2024 at 14:20
  • $\begingroup$ Does Kolmogorov complexity have the properties you're looking for? $\endgroup$ Commented Apr 11, 2024 at 13:50
  • $\begingroup$ Thanks for the comments. In my specific case, I am mainly looking to find am means of deriving an LLR grammar using a few hundred web pages (normally from the same website) as the input. Kolmogorov complexity, as I understand it, is a metric which could be useful for measuring comparative success of various approaches. Given, for example, that the footer of a website does not change, I can envisage a footer expansion (which may include a parameter that indicates 'current page', or any other variable part of the general expansion. l $\endgroup$ Commented Apr 11, 2024 at 23:22

0

Reset to default

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.