String Rewriting System (SRS)
Jump to navigation
Jump to search
A String Rewriting System (SRS) is a formal mathematical system that involves the manipulation and transformation of strings of symbols based on a set of rules.
- Context:
- It can (typically) use Rewriting Rules to replace specific sequences of symbols within a string to transform the string into a new form.
- It can (often) be applied in Formal Language Theory, where it serves as a mechanism for defining language generation or transformation.
- It can range from being a Deterministic Rewriting System, where rules apply in a predictable manner, to being a Non-deterministic Rewriting System, where multiple rules might apply.
- It can enable the simulation of Computation Models by providing a means to model the behavior of Turing Machines and other Automata.
- It can be analyzed for properties such as Confluence and Termination, which determine the behavior of the system under repeated application of rules.
- It can be represented with an Abstract Rewriting System, where objects are strings, and the relations are defined by the rewriting rules applicable to these strings.
- ...
- Example(s):
- a Post Canonical System that showcases the generative power of simple rewriting rules.
- a Markov Algorithm that demonstrates the application of string rewriting in algorithmic processes.
- an B System, with 4 tokens (A#, #A, B#, #B) and rewrite rules that eliminate or swap neighboring tokens when their # symbols face each other.
- L-systems, which use string rewriting to model the growth and morphology of plants and other biological structures.
- Thue Systems, semi-Thue systems.
- Tagged Rewriting Systems, which extend basic SRSs with additional tagging mechanisms to control rule application and increase expressiveness.
- ...
- Counter-Example(s):
- Context-Free Grammars, which use production rules in a structured format distinct from the direct symbol replacement used in SRS.
- ...
- See: Rewriting Rule, Formal Language Theory, Confluence, Termination, Abstract Rewriting System.