\documentclass[12pt,titlepage]{article}

\usepackage{amsmath}
\usepackage{mathrsfs}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{mathtools}
\usepackage{graphicx}
\usepackage{color}
\usepackage{ucs}
\usepackage[utf8x]{inputenc}
\usepackage{xparse}
\usepackage{hyperref}

%----Macros----------
%
% Unresolved issues:
%
%  \righttoleftarrow
%  \lefttorightarrow
%
%  \color{} with HTML colorspec
%  \bgcolor
%  \array with options (without options, it's equivalent to the matrix environment)

% Of the standard HTML named colors, white, black, red, green, blue and yellow
% are predefined in the color package. Here are the rest.
\definecolor{aqua}{rgb}{0, 1.0, 1.0}
\definecolor{fuschia}{rgb}{1.0, 0, 1.0}
\definecolor{gray}{rgb}{0.502, 0.502, 0.502}
\definecolor{lime}{rgb}{0, 1.0, 0}
\definecolor{maroon}{rgb}{0.502, 0, 0}
\definecolor{navy}{rgb}{0, 0, 0.502}
\definecolor{olive}{rgb}{0.502, 0.502, 0}
\definecolor{purple}{rgb}{0.502, 0, 0.502}
\definecolor{silver}{rgb}{0.753, 0.753, 0.753}
\definecolor{teal}{rgb}{0, 0.502, 0.502}

% Because of conflicts, \space and \mathop are converted to
% \itexspace and \operatorname during preprocessing.

% itex: \space{ht}{dp}{wd}
%
% Height and baseline depth measurements are in units of tenths of an ex while
% the width is measured in tenths of an em.
\makeatletter
\newdimen\itex@wd%
\newdimen\itex@dp%
\newdimen\itex@thd%
\def\itexspace#1#2#3{\itex@wd=#3em%
\itex@wd=0.1\itex@wd%
\itex@dp=#2ex%
\itex@dp=0.1\itex@dp%
\itex@thd=#1ex%
\itex@thd=0.1\itex@thd%
\advance\itex@thd\the\itex@dp%
\makebox[\the\itex@wd]{\rule[-\the\itex@dp]{0cm}{\the\itex@thd}}}
\makeatother

% \tensor and \multiscript
\makeatletter
\newif\if@sup
\newtoks\@sups
\def\append@sup#1{\edef\act{\noexpand\@sups={\the\@sups #1}}\act}%
\def\reset@sup{\@supfalse\@sups={}}%
\def\mk@scripts#1#2{\if #2/ \if@sup ^{\the\@sups}\fi \else%
  \ifx #1_ \if@sup ^{\the\@sups}\reset@sup \fi {}_{#2}%
  \else \append@sup#2 \@suptrue \fi%
  \expandafter\mk@scripts\fi}
\def\tensor#1#2{\reset@sup#1\mk@scripts#2_/}
\def\multiscripts#1#2#3{\reset@sup{}\mk@scripts#1_/#2%
  \reset@sup\mk@scripts#3_/}
\makeatother

% \slash
\makeatletter
\newbox\slashbox \setbox\slashbox=\hbox{$/$}
\def\itex@pslash#1{\setbox\@tempboxa=\hbox{$#1$}
  \@tempdima=0.5\wd\slashbox \advance\@tempdima 0.5\wd\@tempboxa
  \copy\slashbox \kern-\@tempdima \box\@tempboxa}
\def\slash{\protect\itex@pslash}
\makeatother

% math-mode versions of \rlap, etc
% from Alexander Perlis, "A complement to \smash, \llap, and lap"
%   http://math.arizona.edu/~aprl/publications/mathclap/
\def\clap#1{\hbox to 0pt{\hss#1\hss}}
\def\mathllap{\mathpalette\mathllapinternal}
\def\mathrlap{\mathpalette\mathrlapinternal}
\def\mathclap{\mathpalette\mathclapinternal}
\def\mathllapinternal#1#2{\llap{$\mathsurround=0pt#1{#2}$}}
\def\mathrlapinternal#1#2{\rlap{$\mathsurround=0pt#1{#2}$}}
\def\mathclapinternal#1#2{\clap{$\mathsurround=0pt#1{#2}$}}

% Renames \sqrt as \oldsqrt and redefine root to result in \sqrt[#1]{#2}
\let\oldroot\root
\def\root#1#2{\oldroot #1 \of{#2}}
\renewcommand{\sqrt}[2][]{\oldroot #1 \of{#2}}

% Manually declare the txfonts symbolsC font
\DeclareSymbolFont{symbolsC}{U}{txsyc}{m}{n}
\SetSymbolFont{symbolsC}{bold}{U}{txsyc}{bx}{n}
\DeclareFontSubstitution{U}{txsyc}{m}{n}

% Manually declare the stmaryrd font
\DeclareSymbolFont{stmry}{U}{stmry}{m}{n}
\SetSymbolFont{stmry}{bold}{U}{stmry}{b}{n}

% Manually declare the MnSymbolE font
\DeclareFontFamily{OMX}{MnSymbolE}{}
\DeclareSymbolFont{mnomx}{OMX}{MnSymbolE}{m}{n}
\SetSymbolFont{mnomx}{bold}{OMX}{MnSymbolE}{b}{n}
\DeclareFontShape{OMX}{MnSymbolE}{m}{n}{
    <-6>  MnSymbolE5
   <6-7>  MnSymbolE6
   <7-8>  MnSymbolE7
   <8-9>  MnSymbolE8
   <9-10> MnSymbolE9
  <10-12> MnSymbolE10
  <12->   MnSymbolE12}{}

% Declare specific arrows from txfonts without loading the full package
\makeatletter
\def\re@DeclareMathSymbol#1#2#3#4{%
    \let#1=\undefined
    \DeclareMathSymbol{#1}{#2}{#3}{#4}}
\re@DeclareMathSymbol{\neArrow}{\mathrel}{symbolsC}{116}
\re@DeclareMathSymbol{\neArr}{\mathrel}{symbolsC}{116}
\re@DeclareMathSymbol{\seArrow}{\mathrel}{symbolsC}{117}
\re@DeclareMathSymbol{\seArr}{\mathrel}{symbolsC}{117}
\re@DeclareMathSymbol{\nwArrow}{\mathrel}{symbolsC}{118}
\re@DeclareMathSymbol{\nwArr}{\mathrel}{symbolsC}{118}
\re@DeclareMathSymbol{\swArrow}{\mathrel}{symbolsC}{119}
\re@DeclareMathSymbol{\swArr}{\mathrel}{symbolsC}{119}
\re@DeclareMathSymbol{\nequiv}{\mathrel}{symbolsC}{46}
\re@DeclareMathSymbol{\Perp}{\mathrel}{symbolsC}{121}
\re@DeclareMathSymbol{\Vbar}{\mathrel}{symbolsC}{121}
\re@DeclareMathSymbol{\sslash}{\mathrel}{stmry}{12}
\re@DeclareMathSymbol{\bigsqcap}{\mathop}{stmry}{"64}
\re@DeclareMathSymbol{\biginterleave}{\mathop}{stmry}{"6}
\re@DeclareMathSymbol{\invamp}{\mathrel}{symbolsC}{77}
\re@DeclareMathSymbol{\parr}{\mathrel}{symbolsC}{77}
\makeatother

% \llangle, \rrangle, \lmoustache and \rmoustache from MnSymbolE
\makeatletter
\def\Decl@Mn@Delim#1#2#3#4{%
  \if\relax\noexpand#1%
    \let#1\undefined
  \fi
  \DeclareMathDelimiter{#1}{#2}{#3}{#4}{#3}{#4}}
\def\Decl@Mn@Open#1#2#3{\Decl@Mn@Delim{#1}{\mathopen}{#2}{#3}}
\def\Decl@Mn@Close#1#2#3{\Decl@Mn@Delim{#1}{\mathclose}{#2}{#3}}
\Decl@Mn@Open{\llangle}{mnomx}{'164}
\Decl@Mn@Close{\rrangle}{mnomx}{'171}
\Decl@Mn@Open{\lmoustache}{mnomx}{'245}
\Decl@Mn@Close{\rmoustache}{mnomx}{'244}
\makeatother

% Widecheck
\makeatletter
\DeclareRobustCommand\widecheck[1]{{\mathpalette\@widecheck{#1}}}
\def\@widecheck#1#2{%
    \setbox\z@\hbox{\m@th$#1#2$}%
    \setbox\tw@\hbox{\m@th$#1%
       \widehat{%
          \vrule\@width\z@\@height\ht\z@
          \vrule\@height\z@\@width\wd\z@}$}%
    \dp\tw@-\ht\z@
    \@tempdima\ht\z@ \advance\@tempdima2\ht\tw@ \divide\@tempdima\thr@@
    \setbox\tw@\hbox{%
       \raise\@tempdima\hbox{\scalebox{1}[-1]{\lower\@tempdima\box
\tw@}}}%
    {\ooalign{\box\tw@ \cr \box\z@}}}
\makeatother

% \mathraisebox{voffset}[height][depth]{something}
\makeatletter
\NewDocumentCommand\mathraisebox{moom}{%
\IfNoValueTF{#2}{\def\@temp##1##2{\raisebox{#1}{$\m@th##1##2$}}}{%
\IfNoValueTF{#3}{\def\@temp##1##2{\raisebox{#1}[#2]{$\m@th##1##2$}}%
}{\def\@temp##1##2{\raisebox{#1}[#2][#3]{$\m@th##1##2$}}}}%
\mathpalette\@temp{#4}}
\makeatletter

% udots (taken from yhmath)
\makeatletter
\def\udots{\mathinner{\mkern2mu\raise\p@\hbox{.}
\mkern2mu\raise4\p@\hbox{.}\mkern1mu
\raise7\p@\vbox{\kern7\p@\hbox{.}}\mkern1mu}}
\makeatother

%% Fix array
\newcommand{\itexarray}[1]{\begin{matrix}#1\end{matrix}}
%% \itexnum is a noop
\newcommand{\itexnum}[1]{#1}

%% Renaming existing commands
\newcommand{\underoverset}[3]{\underset{#1}{\overset{#2}{#3}}}
\newcommand{\widevec}{\overrightarrow}
\newcommand{\darr}{\downarrow}
\newcommand{\nearr}{\nearrow}
\newcommand{\nwarr}{\nwarrow}
\newcommand{\searr}{\searrow}
\newcommand{\swarr}{\swarrow}
\newcommand{\curvearrowbotright}{\curvearrowright}
\newcommand{\uparr}{\uparrow}
\newcommand{\downuparrow}{\updownarrow}
\newcommand{\duparr}{\updownarrow}
\newcommand{\updarr}{\updownarrow}
\newcommand{\gt}{>}
\newcommand{\lt}{<}
\newcommand{\map}{\mapsto}
\newcommand{\embedsin}{\hookrightarrow}
\newcommand{\Alpha}{A}
\newcommand{\Beta}{B}
\newcommand{\Zeta}{Z}
\newcommand{\Eta}{H}
\newcommand{\Iota}{I}
\newcommand{\Kappa}{K}
\newcommand{\Mu}{M}
\newcommand{\Nu}{N}
\newcommand{\Rho}{P}
\newcommand{\Tau}{T}
\newcommand{\Upsi}{\Upsilon}
\newcommand{\omicron}{o}
\newcommand{\lang}{\langle}
\newcommand{\rang}{\rangle}
\newcommand{\Union}{\bigcup}
\newcommand{\Intersection}{\bigcap}
\newcommand{\Oplus}{\bigoplus}
\newcommand{\Otimes}{\bigotimes}
\newcommand{\Wedge}{\bigwedge}
\newcommand{\Vee}{\bigvee}
\newcommand{\coproduct}{\coprod}
\newcommand{\product}{\prod}
\newcommand{\closure}{\overline}
\newcommand{\integral}{\int}
\newcommand{\doubleintegral}{\iint}
\newcommand{\tripleintegral}{\iiint}
\newcommand{\quadrupleintegral}{\iiiint}
\newcommand{\conint}{\oint}
\newcommand{\contourintegral}{\oint}
\newcommand{\infinity}{\infty}
\newcommand{\bottom}{\bot}
\newcommand{\minusb}{\boxminus}
\newcommand{\plusb}{\boxplus}
\newcommand{\timesb}{\boxtimes}
\newcommand{\intersection}{\cap}
\newcommand{\union}{\cup}
\newcommand{\Del}{\nabla}
\newcommand{\odash}{\circleddash}
\newcommand{\negspace}{\!}
\newcommand{\widebar}{\overline}
\newcommand{\textsize}{\normalsize}
\renewcommand{\scriptsize}{\scriptstyle}
\newcommand{\scriptscriptsize}{\scriptscriptstyle}
\newcommand{\mathfr}{\mathfrak}
\newcommand{\statusline}[2]{#2}
\newcommand{\tooltip}[2]{#2}
\newcommand{\toggle}[2]{#2}

% Theorem Environments
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{prop}{Proposition}
\newtheorem{cor}{Corollary}
\newtheorem*{utheorem}{Theorem}
\newtheorem*{ulemma}{Lemma}
\newtheorem*{uprop}{Proposition}
\newtheorem*{ucor}{Corollary}
\theoremstyle{definition}
\newtheorem{defn}{Definition}
\newtheorem{example}{Example}
\newtheorem*{udefn}{Definition}
\newtheorem*{uexample}{Example}
\theoremstyle{remark}
\newtheorem{remark}{Remark}
\newtheorem{note}{Note}
\newtheorem*{uremark}{Remark}
\newtheorem*{unote}{Note}

%-------------------------------------------------------------------

\begin{document}

%-------------------------------------------------------------------


\section*{path category}

\hypertarget{contex}{}\subsubsection*{{Contex}}\label{contex}

\hypertarget{category_theory}{}\paragraph*{{Category theory}}\label{category_theory}

[[!include category theory - contents]]

\hypertarget{contents}{}\section*{{Contents}}\label{contents}

\noindent\hyperlink{idea}{Idea}\dotfill \pageref*{idea} \linebreak
\noindent\hyperlink{free_category_on_a_directed_graph}{Free category on a directed graph}\dotfill \pageref*{free_category_on_a_directed_graph} \linebreak
\noindent\hyperlink{remark}{Remark}\dotfill \pageref*{remark} \linebreak
\noindent\hyperlink{path_category_of_a_space}{Path category of a space}\dotfill \pageref*{path_category_of_a_space} \linebreak
\noindent\hyperlink{arrow_category}{Arrow category}\dotfill \pageref*{arrow_category} \linebreak
\noindent\hyperlink{related_concepts}{Related concepts}\dotfill \pageref*{related_concepts} \linebreak
\noindent\hyperlink{references}{References}\dotfill \pageref*{references} \linebreak


\hypertarget{idea}{}\subsection*{{Idea}}\label{idea}

One can view the concept of a [[morphism]] or arrow in a [[category]] as an extreme abstraction of the concept of a spatial trajectory. It therefore comes with no surprise that (notions of) paths stemming from various conceptualizations of `space' like e.g. [[quivers]] or [[topological spaces]] arrange themselves in appropriate categories thereby giving rise to several \emph{different notions} of \textbf{path category}.

\hypertarget{free_category_on_a_directed_graph}{}\subsection*{{Free category on a directed graph}}\label{free_category_on_a_directed_graph}

There is a [[forgetful functor]] from [[small category|small]] [[strict category|strict]] [[categories]] to [[quivers]]. This forgetful functor has a [[left adjoint]], giving the \textbf{[[free category]]} or \textbf{path category} of a quiver, whose [[objects]] are the vertices of the quiver. The [[morphisms]] from $a$ to $b$ in this free category are \emph{not} merely the arrows from $a$ to $b$ in the quiver but instead are [[lists]] of the form $(a_n,f_n,a_{n-1},\ldots,a_{1},f_1,a_0)$ where $n \geq 0$ is a [[natural number]], $a_0,a_1,\ldots,a_n$ are vertices of the graph, $a = a_0$, $b = a_n$, and for all $0 \lt i \leq n$, $f_i\colon a_{i-1} \to a_i$ is an edge from $a_{i-1}$ to $a_i$. The [[composition]] is given by the concatenation

\begin{displaymath}
(a_n,f_n,a_{n-1},\ldots,a_{1},f_1,a_0)\circ (b_m,g_m,a_{m-1},\ldots,b_{1},g_1,b_0) := (a_n,f_n,a_{n-1},\ldots,a_{1},f_1,a_0= b_m,g_m,a_{m-1},\ldots,b_{1},g_1,b_0)
\end{displaymath}
whenever $a_0 = b_m$, and the [[target]] and [[source]] maps are given by $s(a_n,f_n,a_{n-1},\ldots,a_{1},f_1,a_0)=a_0$ and $t(a_n,f_n,a_{n-1},\ldots,a_{1},f_1,a_0) = a_n$. One informally writes $f$ for the morphism $(b,f,a)\colon a \to b$ in the free category and the [[identity morphism|identities]] of the free category are $id_a = (a,a)$; thus

\begin{displaymath}
f_n \circ f_{n-1} \circ \ldots \circ f_1 = (t(f_n),f_n,t(f_{n-1}),\ldots,t(f_1),f_1,s(f_1))\quad .
\end{displaymath}
\hypertarget{remark}{}\subsubsection*{{Remark}}\label{remark}

With free objects, one is often primarily interested in taking quotients whence a free category over a graph is usually a somewhat auxiliary gadget its main interest lying in the role it plays in defining [[category of fractions|categories of fractions]] (cf. [[Gabriel-Zisman]] 1967 pp.1,6; probably the original source of the path category in this sense).

But similar techniques apply to various notions of graphs or more restricted classes of categories with forgetful functors to graphs permitting to syntactically generate various notions of free categories with extra structure and in some of these cases it occurs that the corresponding free category (of paths) is indeed interesting in itself e.g. the [[free topos]] arises this way and the syntactic derivations of context free grammars arrange themselves into such categories of paths as explored in Walters (\hyperlink{Walters1}{1989a},\hyperlink{Walters2}{1989b}) or Latch (\hyperlink{Latch}{1991}).

\hypertarget{path_category_of_a_space}{}\subsection*{{Path category of a space}}\label{path_category_of_a_space}

Given a [[topological space]] $X$ (or some other kind of [[space]] with a notion of maps from [[intervals]] into it), there are various ways to obtain a [[small category|small]] [[strict category|strict]] [[category]] whose objects are the points of $X$ and whose morphisms are [[paths]] in $X$. This is also often called a \emph{path category}.

\begin{itemize}%
\item In particular, for every topological space there is its [[fundamental groupoid]] whose morphisms are [[homotopy]] classes of paths in $X$.


\item If $X$ is a [[directed space]] there is a notion of path category called the [[fundamental category]] of $X$.


\item When $X$ is a [[smooth space]], there is a notion of path category where less than homotopy of paths is divided out: just \emph{thin} homotopy. This yields a notion of [[path groupoid]].


\item If \emph{parameterized} paths are used, there is a way to get a category of paths without dividing out any equivalence relation: this is the [[Moore path category]].



\end{itemize}
\hypertarget{arrow_category}{}\subsection*{{Arrow category}}\label{arrow_category}

Given a [[category]] $X$, the [[functor category]] $[I,X]$ for $I$ the [[interval category]] might be called a ``directed path category of $X$'' (similar to [[path space]]). However, this functor category is referred to instead as the [[arrow category]] of $X$ and sometimes even denoted $Arr(X)$.

\hypertarget{related_concepts}{}\subsection*{{Related concepts}}\label{related_concepts}

\begin{itemize}%
\item [[free groupoid]]


\item [[free diagram]]


\item [[free monoid]], [[free operad]]


\item [[free topos]]



\end{itemize}
\hypertarget{references}{}\subsection*{{References}}\label{references}

The [[free category]] on a graph has a section in

\begin{itemize}%
\item [[Francis Borceux]], \emph{Handbook of categorical Algebra vol. 1} , Cambridge UP 1994.

\end{itemize}
or in

\begin{itemize}%
\item [[Saunders MacLane]], \emph{Categories for the Working Mathematician} , Springer 1998.

\end{itemize}
The following is another source for this, even an open source:

\begin{itemize}%
\item [[Michael Barr]] and [[Charles Wells]], \emph{Category Theory for Computing Science} \href{http://www.math.mcgill.ca/triples/Barr-Wells-ctcs.pdf}{PDF}

\end{itemize}
The path categories of context free grammars are explored in

\begin{itemize}%
\item Dana Latch, \emph{The connection between the fundamental groupoid and a unification algorithm for syntactil algebras (extended abstract)} , Cah. Top. G\'e{}om. Diff. Cat. \textbf{XXXII} (1991). (\href{http://www.numdam.org/item?id=CTGDC_1991__32_3_203_0}{link})


\item [[Bob Walters]], \emph{The free category with products on a multigraph} , JPAA \textbf{62} (1989). (\href{http://www.sciencedirect.com/science/article/pii/0022404989901527}{link})


\item [[Bob Walters]], \emph{A note on context-free languages} , JPAA \textbf{62} (1989). (\href{http://www.sciencedirect.com/science/article/pii/0022404989901515}{link})



\end{itemize}
Since the perspective on categories as `graphs with operations' is closely related to their `logico-deductive' side, it figures prominently in the work of [[Jim Lambek]] and [[Phil Scott]] (cf. the references at [[free topos]]).

[[!redirects path category]] [[!redirects path categories]]



\end{document}