<p>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 (<a href="https://en.wikipedia.org/wiki/Tree_adjoining_grammar" rel="nofollow">https://en.wikipedia.org/wiki/Tree_adjoining_grammar</a>)</p>

<p>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.</p>

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

CC BY-SA 3.0
2013-09-19T21:30:45.840Z
2013-09-19T21:30:45.840Z
Anna Melzer
<p>Let the alphabet $\Sigma$ be extended to include $\bullet$, the concatenation point character.   Define concatenation of such strings to be:
(by example):</p>

<p>$$
s\cdot t = (\omega \bullet \gamma ) \cdot t = \omega t \gamma 
$$</p>

<p>$s$ inherits $t$'s concatenation points obviously.</p>

<p>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.</p>

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

<p>Then we have a way of concatenating two syntax trees.</p>

CC BY-SA 3.0
2013-09-20T04:47:18.897Z
I don't understand your definition. What are $\omega$ and $\gamma$? How do they relate to $s$ and $t$?
J.-E. Pin
<fl.formal-languages><tree><parsing>
Has anyone ever mixed strings in a language with position?
Daniel Donnelly
# Has anyone ever mixed strings in a language with position?

(Asked by: username_0 on 2013-09-19)

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.

**Tags:** fl.formal-languages, tree, parsing

> **Comments:**
> **username_1**: I don't understand your definition. What are $\omega$ and $\gamma$? How do they relate to $s$ and $t$?  

---

## 1 answers

### Answer by username_2 on 2013-09-19. Score: 2 | Accepted answer

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.


---

