לדלג לתוכן

קובץ:Solving the word problem without and with completion.pdf

תוכן הדף אינו נתמך בשפות אחרות.
מתוך ויקיפדיה, האנציקלופדיה החופשית

לקובץ המקורי(1,210 × 1,239 פיקסלים, גודל הקובץ: 9 ק"ב, סוג MIME‏: application/pdf)

ויקישיתוף זהו קובץ שמקורו במיזם ויקישיתוף. תיאורו בדף תיאור הקובץ המקורי (בעברית) מוצג למטה.

תקציר

תיאור
English: Shows a simplified example of the search space for deciding the word problem, i.e., given a set E of equations and two terms s,t (represented by the left- and rightmost vertice), to decide if s=t follows from E. Proof search usually runs into dead ends (red paths); to find a valid proof (green path) may be infeasible without human intuition. However, if the Knuth-Bendix completion algorithm was able to compute from E an equivalent confluent (and terminating) term rewriting system R (shadow paths), deciding if s=t is simple: apply rules from R to s as long as possible to obtain a term s’ (s’ is unique, no matter in which the order rules are applied), rewrite t to some t’ in a similar way, then s=t if and only if s’=t’.
תאריך יצירה
מקור נוצר על־ידי מעלה היצירה
יוצר Jochen Burghardt
גרסאות אחרות File:Solving the word problem without and with completion svg.svg
LaTeX source Code
\documentclass[12pt]{article}
\usepackage[pdftex]{color}
\usepackage[paperwidth=205mm,paperheight=210mm]{geometry}
\setlength{\topmargin}{-36mm}
\setlength{\textwidth}{205mm}
\setlength{\textheight}{210mm}
\setlength{\evensidemargin}{-2.7cm}
\setlength{\oddsidemargin}{-2.5cm}
\setlength{\parindent}{0cm}
\setlength{\parskip}{1ex}
\setlength{\unitlength}{1mm}
\sloppy

%%%%% labyrinth convenience macros %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\conn}{\vector}
\newcounter{curX}       % current x coordinate (in unit lengths)
\newcounter{curY}       % current y coordinate (in unit lengths)

% dir{X}{Y}: advance line in direction 10*X,10*Y
\newcommand{\dir}[2]{%
        \put(\arabic{curX},\arabic{curY}){\conn(#1,#2){10}}%
        \addtocounter{curX}{#1}\addtocounter{curX}{#1}%
        \addtocounter{curX}{#1}\addtocounter{curX}{#1}%
        \addtocounter{curX}{#1}\addtocounter{curX}{#1}%
        \addtocounter{curX}{#1}\addtocounter{curX}{#1}%
        \addtocounter{curX}{#1}\addtocounter{curX}{#1}%
        \addtocounter{curY}{#2}\addtocounter{curY}{#2}%
        \addtocounter{curY}{#2}\addtocounter{curY}{#2}%
        \addtocounter{curY}{#2}\addtocounter{curY}{#2}%
        \addtocounter{curY}{#2}\addtocounter{curY}{#2}%
        \addtocounter{curY}{#2}\addtocounter{curY}{#2}%
        \put(\arabic{curX},\arabic{curY}){\circle*{1}}%
}

% \go{X}{Y}: start line at X,Y
\newcommand{\go}[2]{%
        \setcounter{curX}{#1}%
        \setcounter{curY}{#2}%
        \put(\arabic{curX},\arabic{curY}){\circle*{1}}%
}

% windrose commands
\renewcommand{\ne}{\dir{+1}{+1}}
\newcommand{\nw}{\dir{-1}{+1}}
\newcommand{\sw}{\dir{-1}{-1}}
\newcommand{\se}{\dir{+1}{-1}}

%%%%% colors %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\definecolor{cSuc}      {rgb}{0.00,0.50,0.00}   % successful eqn proof
\definecolor{cFai}      {rgb}{0.99,0.30,0.30}   % failed eqn proof attempts
\definecolor{cAvl}      {rgb}{0.90,0.90,0.90}   % available rewrites
\definecolor{cUse}      {rgb}{0.40,0.40,0.40}   % used rewrites

\begin{document}
~
\begin{picture}(200,200)
% confluent and terminating rewriting system
\color{cAvl}
\multiput(0,97)(10,10){11}{\multiput(0,0)(10,-10){11}{\circle*{1}}}%
\multiput(0,97)(10,10){11}{\multiput(0,0)(10,-10){10}{\vector(1,-1){10}}}%
\multiput(100,197)(10,-10){11}{\multiput(0,0)(-10,-10){10}{\vector(-1,-1){10}}}%
% actually used to compute normal forms
\color{cUse}
\put(20,97){\circle*{2}}%                       left
\go{20}{97}\se\se\se\se\sw\se\se\se\se\se%
\put(170,107){\circle*{2}}%                     right
\go{170}{107}\sw\sw\se\sw\sw\se\sw\sw\sw\sw\sw%
\put(100,-4){\circle*{2}}%                      normal form

\renewcommand{\conn}{\line}%
\thicklines%
% unsuccessful equations
\color{cFai}%
\go{10}{90}\nw\ne\ne\ne\se\ne\nw\ne\se\se\ne\ne\nw\sw\nw\ne\ne\se\ne\ne\nw\sw%
\go{70}{130}\sw\sw\se\se%
\go{20}{100}\ne\se\se%
\go{190}{90}\ne\nw\nw\nw\nw\sw\sw\nw\nw\ne\nw\sw\nw\ne%
\go{160}{140}\nw\sw%
\go{110}{190}\se\se\se%
\go{20}{80}\se\se\se\ne\se\ne\ne\ne\ne\nw\nw%
\go{110}{130}\se\se\se\ne\ne
\go{100}{60}\sw\sw\sw\nw%
\go{140}{60}\sw\se\sw\nw\sw\nw\sw\sw\se\ne\se\ne\ne%
\go{170}{110}\se\se\sw\nw\sw\se\sw\sw%
\go{90}{10}\se%
% successful equations
\color{cSuc}%
\go{20}{100}\sw\se\ne\se\se\ne\se\ne\ne\nw\nw\ne\ne\ne\se\sw\se\se\se%
        \sw\sw\sw\se\ne\ne\se\ne\nw\ne\ne\ne%
\put(20,100){\circle*{2}}%
\put(170,110){\circle*{2}}%
\end{picture}
\end{document}

רישיון

אני, בעל זכויות היוצרים על עבודה זו, מפרסם בזאת את העבודה תחת הרישיון הבא:
w:he:Creative Commons
ייחוס שיתוף זהה
הקובץ הזה מתפרסם לפי תנאי רישיון קריאייטיב קומונז ייחוס-שיתוף זהה 3.0 לא מותאם.
הנכם רשאים:
  • לשתף – להעתיק, להפיץ ולהעביר את העבודה
  • לערבב בין עבודות – להתאים את העבודה
תחת התנאים הבאים:
  • ייחוס – יש לתת ייחוס הולם, לתת קישור לרישיון, ולציין אם נעשו שינויים. אפשר לעשות את זה בכל צורה סבירה, אבל לא בשום צורה שמשתמע ממנה שמעניק הרישיון תומך בך או בשימוש שלך.
  • שיתוף זהה – אם תיצרו רמיקס, תשנו, או תבנו על החומר, חובה עליכם להפיץ את התרומות שלך לפי תנאי רישיון זהה או תואם למקור.

כיתובים

נא להוסיף משפט שמסביר מה הקובץ מייצג

פריטים שמוצגים בקובץ הזה

מוצג

היסטוריית הקובץ

ניתן ללחוץ על תאריך/שעה כדי לראות את הקובץ כפי שנראה באותו זמן.

תאריך/שעהתמונה ממוזערתממדיםמשתמשהערה
נוכחית17:02, 9 ביוני 2014תמונה ממוזערת לגרסה מ־17:02, 9 ביוני 2014‪1,239 × 1,210‬ (9 ק"ב)Jochen Burghardtseveral possible normalizing paths in canonical rewrite system
23:49, 6 ביוני 2014אין תמונה ממוזערת‪0 × 0‬ (14 ק"ב)Jochen BurghardtUser created page with UploadWizard

אין בוויקיפדיה דפים המשתמשים בקובץ זה.

מטא־נתונים