Reduktionssystem

I matematisk logik og teoretisk datalogi står udtrykket reduktionssystem eller abstrakt reduktionssystem eller kort sagt ARS for en generalisering af termomskrivningssystemer . I sin enkleste form er en ARS et sæt objekter sammen med en binær relation , som normalt kaldes. På trods af sin enkelhed er en ARS tilstrækkelig til at beskrive vigtige egenskaber ved termomskrivningssystemer, såsom B. normale former , opsigelse og forskellige sammenløbskoncepter . ${\ displaystyle \ rightarrow}$

Historisk set har der været flere forskellige abstraktioner af termomskrivning, hver med sine egne detaljer. Den mest anvendte formalisering i dag, som følges her, er baseret på Gérard Huets arbejde (1980).

definition

En ARS består af et sæt A , objekterne sammen med en binær relation på A , normalt betegnet med. Denne relation kaldes reduktionsforhold eller simpelthen reduktion .${\ displaystyle \ rightarrow}$

Som et matematisk objekt er en ARS det samme som et umarkeret overgangssystem . Ikke desto mindre er fokus og terminologi forskellige på disse to områder: I et overgangssystem er man interesseret i at fortolke markeringerne som handlinger, mens i en ARS er fokus på, hvordan objekter omdannes (reduceres) til andre.

eksempel

Sættet med objekter er T = { a , b , c } og den binære relation → defineres som følger: → ; dette skrives normalt som ${\ displaystyle = \ {(a, b), (b, a), (a, c), (b, c) \}}$

Hvis man læser dette som regler, hvormed elementer kan omdannes til andre, ser man, at både a og b kan omdannes (reduceres) til c . Tilsyneladende er dette en vigtig egenskab ved systemet. På en måde er c et "enkleste" objekt i systemet, da ingen af ​​reglerne kan anvendes på c for yderligere at transformere dette element.

Grundlæggende vilkår

Ovenstående eksempel fører til nogle vigtige udtryk i forbindelse med en ARS.

• ${\ displaystyle {\ stackrel {*} {\ rightarrow}}}$er den transitive skal af , hvor = er identiteten ; d. H. er den mindste kvasi-orden ( refleksiv og transitiv relation), der indeholder. Det er også den refleksive og transitive skal af .${\ displaystyle \ rightarrow \ cup =}$${\ displaystyle {\ stackrel {*} {\ rightarrow}}}$${\ displaystyle \ rightarrow}$${\ displaystyle \ rightarrow}$

• ${\ displaystyle \ leftrightarrow}$er , d. H. foreningen af ​​forholdet med dets omvendte forhold ; kaldes også den symmetriske kuvert af .${\ displaystyle \ rightarrow \ cup \ rightarrow ^ {- 1}}$${\ displaystyle \ rightarrow}$${\ displaystyle \ leftrightarrow}$${\ displaystyle \ rightarrow}$
• ${\ displaystyle {\ stackrel {*} {\ leftrightarrow}}}$er det transitive skrog af , dvs. H. er den mindste ækvivalensrelation, der indeholder. Det kaldes også den refleksive transitive symmetriske kuvert af .${\ displaystyle \ leftrightarrow \ cup =}$${\ displaystyle {\ stackrel {*} {\ leftrightarrow}}}$${\ displaystyle \ rightarrow}$${\ displaystyle \ rightarrow}$

Normale former og ordproblemet

Et objekt x i A siges at være reducerbart, hvis der er et objekt y i A forskelligt fra x med ; ellers kaldes det irreducible eller en normal form . Et objekt y kaldes den normale form for x, hvis det holder, og y er irreducerbart. Hvis x har en unik normal form, betegnes dette med. ${\ displaystyle x \ rightarrow y}$${\ displaystyle x {\ stackrel {*} {\ rightarrow}} y}$${\ displaystyle x \ downarrow}$

I eksemplet ovenfor er c en normal form for a og b . Da a og b er reducerbare, er c endog den eneste normale form for disse elementer . Hvis hvert objekt har mindst en normal form, kaldes ARS normalisering . ${\ displaystyle c = a \ downarrow = b \ downarrow}$

Et af de vigtige problemer, der kan formuleres i sammenhæng med en ARS er ordet problem : Givet x og y , er disse to objekter svarende under forhold ? Dette er en meget generel ramme for ordproblemet; så er z. B. ordproblemet for grupper er et specielt tilfælde af ARS-ordproblemet. Ordproblemet er lettere at håndtere, når der er unikke normale former: i dette tilfælde er to objekter med samme normale form ækvivalente nedenfor . Ordproblemet for en ARS kan generelt ikke afgøres . ${\ displaystyle {\ stackrel {*} {\ leftrightarrow}}}$${\ displaystyle {\ stackrel {*} {\ leftrightarrow}}}$

For undersøgelsen af ​​spørgsmålet om, hvorvidt der findes normale former, er betingelserne for Church-Rossers ejendom og sammenløb af central betydning.

svulme

• Franz Baader, Tobias Nipkow: Omskrivning af term og alt det der. Cambridge University Press, 1998. Velegnet til begyndere.
• Nachum Dershowitz og Jean-Pierre Jouannaud Rewrite Systems , kapitel 6 i Jan van Leeuwen (red.), Handbook of Theoretical Computer Science. Bind B: formelle modeller og semantik. Elsevier / MIT Press, 1990, ISBN 0-444-88074-7 , s. 243-320.
• Ronald V. Book , Friedrich Otto: Strengomskrivningssystemer. Springer, Berlin 1993. Kapitel 1: Abstrakte reduktionssystemer. ISBN 0-387-97965-4 .
• Marc Bezem, JW Klop, Roel de Vrijer: Systemer til omskrivning af begreber. Cambridge University Press, 2003, ISBN 0-521-39115-6 , kapitel 1. (Dette er en omfattende monografi).
• John Harrison: Handbook of Practical Logic and Automated Reasoning. Cambridge University Press, 2009, ISBN 978-0-521-89957-4 , kapitel 4: Ligestilling.
• Gérard Huet: Confluent Reductions: Abstract Properties og Applications to Term Rewriting Systems. I: Journal of the ACM (JACM), bind 27, nr. 4, oktober 1980, s. 797-821.

Individuelle beviser

1. ↑ Ronald V. Bog, Friedrich Otto: String omskrivning systemer. S. 9.
2. ^ Ronald V. Book, Friedrich Otto: String rewriting systems. S. 10.
3. ↑ Marc Bezem, JW Klop, Roel de Vrijer: Term omskrivning systemer. Pp. 7-8.
4. ^ Franz Baader, Tobias Nipkow: Termomskrivning og alt det der. Pp. 8-9.
5. ^ Franz Baader, Tobias Nipkow: Termomskrivning og alt det der. S. 11 f.