4 ms·
It's a Semi-Thue system[0], a particular form of term rewriting system that is almost 30 years older than tag systems; introduced over a hundred years ago to fo
by mmarx 8y ago
It's a Semi-Thue system[0], a particular form of term rewriting system that is almost 30 years older than tag systems; introduced over a hundred years ago to formalise word problems in finitely presented semigroups (that's where the semi-part of the name comes from).
[0] https://en.wikipedia.org/wiki/Semi-Thue_system https://en.wikipedia.org/wiki/Semi-Thue_system
- Avshalom 8y agoThat's cool, so I'm drunk and on my phone, but it seems like tag systems are then a sort of subset of thue systems? specifically an only concatenative subset, which makes me feel like some one should definitely add a reference to the tag systems page.