String Rewriting System (SRS): Difference between revisions
Jump to navigation
Jump to search
No edit summary |
No edit summary |
||
| Line 6: | Line 6: | ||
** It can enable the simulation of [[Computation Models]] by providing a means to model the behavior of [[Turing Machines]] and other [[Automata]]. | ** 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 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. | |||
** ... | ** ... | ||
* <B>Example(s):</B> | * <B>Example(s):</B> | ||
** a [[Post Canonical System]] that showcases the generative power of simple rewriting rules. | ** 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. | ** a [[Markov Algorithm]] that demonstrates the application of string rewriting in algorithmic processes. | ||
** an [[A::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-system]]s, which use string rewriting to model the growth and morphology of plants and other biological structures. | |||
** [[Thue System]]s, [[semi-Thue system]]s. | |||
** [[Tagged Rewriting Systems]], which extend basic SRSs with additional tagging mechanisms to control rule application and increase expressiveness. | |||
** ... | ** ... | ||
* <B>Counter-Example(s):</B> | * <B>Counter-Example(s):</B> | ||
Revision as of 18:34, 25 April 2024
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.