Wolfram Library Archive


All Collections Articles Books Conference Proceedings
Courseware Demos MathSource Technical Notes
Title Downloads

Rewriting Systems
Author

Jaime Rangel-Mondragón
Organization: Universidad Autonoma de Querétaro
Department: Facultad de Informatica
Revision date

2003-11-18
Description

Rewriting systems (RS), have been widely used in contexts in which formulae manipulation plays a prominent role, such as symbolic and functional programming, formal grammars,computer graphics, simulation, etc. This is due to their intrinsic ability to specify, through employing a set of directed transformational equations, the basic mechanism of subterm substitution.

RS are determined by a series of productions meant to be applied to specific objects. This application consists in the substitution of a pattern occurring on the object also appearing on the left side of a production, by the corresponding pattern on the right side of this production.

The aim of this work is to illustrate the application of RS on a variety of important settings throughout the following themes: One-dimensional Checkers, Group Theory, Equivalence Relations, Systems of Numeric Productions, Recursive Productions, L systems, From Binary Numbers to Compositions and Huffman Coding. A series of animations supplementing several parts of the text is also provided. We are using Mathematica version 5.
Subjects

*Applied Mathematics
*Applied Mathematics > Complex Systems
*Applied Mathematics > Computer Science
*Mathematics > Algebra
*Mathematics > Algebra > Group Theory
*Mathematics > Discrete Mathematics
*Mathematics > Discrete Mathematics > Combinatorics
*Mathematics > Number Theory
*Mathematics > Recreational Mathematics
*Wolfram Technology > Programming > Animations
Keywords

Rewriting Systems, group theory, equivalence relations, numeric productions, L systems, Checkers, Compositions, Huffman Coding, Koch snowflake
Downloads Download Wolfram CDF Player

Download
BinaryCompositions.gif (147 KB) - GIF animation
Download
DragonCurve.gif (339.4 KB) - GIF Animation
Download
KochCurve.gif (69.5 KB) - GIF Animation
Download
NumericProductions.gif (292 KB) - GIF Animation
Download
Osgood.gif (416.5 KB) - GIF Animation
Download
RewritingSystems.nb (529.7 KB) - Notebook for RS
Download
rewritingSystems.zip (94.2 KB) - Same notebook, zipped