nLab
free category

Contents

Contents

Idea

The free category on a “set of arrows”, hence on a directed graph, is the category whose morphisms are the tuples of composable arrows, hence the morphisms freely generated from these arrows. These morphisms may also be thought of as the “paths” that one may trace out in the directed graph by traversing in each step along an arrow, and therefore free categories are also called path categories.

More formally, there is a forgetful functor from the 1-category of categories to that of directed graphs, and the free category construction is the left adjoint to this functor.

References

The free category on a graph has a section in

  • Francis Borceux, Handbook of categorical Algebra vol. 1 , Cambridge UP 1994.

and in

The following is another source for this, even an open source:

The path categories of context free grammars are explored in

  • Dana Latch, The connection between the fundamental groupoid and a unification algorithm for syntactil algebras (extended abstract) , Cah. Top. Géom. Diff. Cat. XXXII (1991). (link)

  • Bob Walters, The free category with products on a multigraph , JPAA 62 (1989). (link)

  • Bob Walters, A note on context-free languages , JPAA 62 (1989). (link)

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).

Last revised on August 8, 2018 at 09:44:20. See the history of this page for a list of all contributions to it.