Let the alphabet $\Sigma$ be extended to include $\bullet$, the concatenation point character. Define concatenation of such strings to be: (by example):

$$ s\cdot t = (\omega \bullet \gamma ) \cdot t = \omega t \gamma $$

$s$ inherits $t$'s concatenation points obviously.

If $s$ has multiple concatenation points you fill in the concatenation points from left-to-right and if you're out of concatenation points, concatenate $t$ to the end of $s$ to get the result.

So then a syntax tree can be encoded as a member of the the weird algebraic structure.

Then we have a way of concatenating two syntax trees.

  • $\begingroup$ I don't understand your definition. What are $\omega$ and $\gamma$? How do they relate to $s$ and $t$? $\endgroup$ – J.-E. Pin Sep 20 '13 at 4:47

I am not sure if I get your question right, but this sounds a bit like an extension to Tree Substitution Grammars or Tree Adjoining Grammars (https://en.wikipedia.org/wiki/Tree_adjoining_grammar)

I think a string with concatenation points can be interpreted as a tree with replacable nodes. The concatenation replaces the node and the tree is afterwards interpreted as a strign again. Add a default if there are no concatenation points and you are there.

There is a lot of work on "weird algebraic structures" like this. Check out http://stp.lingfil.uu.se/atanlp/2012/koller.pdf for a quick look if this is what you looking for.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.