Title: Theory / Unimportant / CS / Fundamental / Graph / Graph Structure and Monadic Second-Order Logic=
Tags: fromMath mathToDef examplesSwitchExample1 toBinaryFunction hasSeenConjDef récupéré
On every note of this deck, unless a note says otherwise:
Chapter: 1

Name: Context-free grammar
Definition: A finite set of rewriting rules defined with two alphabets, a terminal alphabet \(A\) and a nonterminal alphabet \(N\).
Page: 18

Name: The language over \(A\) generated by \(G\) from \(S\)
Page: 18
Variables: \(G=(A,N)\) a context-free language
\(S\in N\)
Notation: \(L(G,S)\)

Name: A simple graph
Definition: A graph without parallel edges.
Page: 18

Name: A loop
Definition: An edge with equal ends.
Page: 18

Page: 18
Section: 1
Notation: \(\oplus\)
Variables: \(G,H\in\mathcal G^u\)
Definition: The function sending two graphs to their disjoint unions.
Commutative: commutative
Associative: Associative
Context: Graph

Page: 18
Section: 1
Notation: \(\otimes\) on \(\mathcal G^u\)
Definition: Sends two disjoint graphs \(G\) and \(H\) to their disjoint union, plus the edges \((g,h)\) for each \(g\in G\), \(h\in H\).
Commutative: commutative
Associative: Associative

Definition: One vertex, no edge.
Page: 19
Notation: \(\mathbf 1\) graph

Name: The set of cographs
Definition: The least set of graphs satisfying the equation \(C=(C\oplus C)\cup (C\otimes C)\cup \{\mathbf 1\}\).
Page: 19

Name: An ambiguous grammar
Definition: A grammar such that an objects admits two distinct derivations.
Page: 20

Name: Class of simple graph
Page: 20
Notation: A class name containing \(G\)
Index: 4
Kind: Footnote
Example: \(\mathcal G^u\), \(\mathbb G^u\)

Name: Class of graph with potential multiple edges
Page: 20
Notation: A class whose notation contains \(J\)
Index: 4
Kind: Footnote

Name: Class of directed graph
Page: 20
Context: Graph
Notation: A class name with superscript \(d\)
Index: 4
Kind: Footnote
Example: \(\mathcal J^d_2\)

Name: Class of undirected graph
Page: 20
Notation: superscript \(u\)
Index: 4
Kind: Footnote

Name: with \(n\) sources
Page: 20
Variables: \(n\in\mathbb N\)
Context: Class of graphs
Notation: class name with subscript \(n\)
Index: 4
Kind: Footnote
Example: \(\mathcal J^d_2\)

Definition: The directed graph \((\{a,b\}, \{(a,b)\})\).
Page: 20
Notation: The graph \(e\)

Definition: The \(i\)-th source of \(G\).
Page: 20
Variables: \(G\in \mathcal J^d_2\)
\(i\) be 1 or 2
Notation: \(src_{G}(i)\)

Name: The parallel-composition of \(G\) and \(H\)
Definition: The disjoint union of \(G\) and \(H\), apart that the sources are merged.
Page: 20
Variables: \(G,H\in \mathcal J^d_2\)
Notation: \(G// H\)

Name: Their series-composition
Definition: The disjoint union of \(G\) and \(H\), apart that the source 2 of \(G\) is merged with the source \(1\) of \(H\).
Page: 20
Variables: \(G,H\in \mathcal J^d_2\)
Notation: \(G\cdot H\)

Name: The set of series-parallel graphs
Definition: The least subset of \(\mathcal J^d_2\) containing \(e\), clozed under parallel and series composition.
Page: 21
Section: 1.3

Name: A functional signature
Definition: A set of function symbols, each symbol associated with a nonnegattive arity.
Section: 1.4

Definition: The arity of \(f\).
Section: 1.4
Variables: \(f\) a function symbol
Notation: \(\rho(f)\)

Name: A constant symbol
Definition: A function symbol of arity 0.
Section: 1.4

Name: An \(F\)-algebra
Definition: \(M\) is a set and,
Section: 1.4
Variables: \(F\) a functional signature
Definition2: for each \(f\in F\), \(f_{\mathbb M}:M^{\rho(f)}\to M\).
Conjdef: such that
DefType: A tuple \(\mathbb M=\langle M,(f_{\mathbb M})_{f\in F}\rangle\)

Name: The domain of \(\mathbb M\)
Section: 1.4
Variables: \(F\) a functional signature
\(\mathbb M=\langle M,(f_{\mathbb M})_{f\in F}\rangle\) an \(F\)-algebra
Notation: \(M\)

Name: An operation of \(\mathbb M\)
Definition: \(f_{\mathbb M}\) for some \(m\in F\)
Section: 1.4
Variables: \(F\) a functional signature
\(\mathbb M=\langle M,(f_{\mathbb M})_{f\in F}\rangle\) an \(F\)-algebra

Name: A finite \(F\)-algebra
Definition: An \(F\)-algebra with finite domain
Page: 22
Section: 1.4
Variables: \(F\) a functional signature

Name: Unknown
Page: 22
Section: 1.4
Name2: Variable

Name: A mononomial
Definition: A term written with the symbols of \(F\cup X\), well formed with respect to arities
Page: 22
Section: 1.4
Variables: \(F\) a functional signature
\(X\) a set of unknowns
Context: Graph structure
Example: \(f(x,g(y))\) for \(x,y\) variables, \(f,g\) functions
Extra: As opposed to polynomials ,which also admit union symbol

Name: A polynomial
Definition: An union of monomial
Page: 22
Section: 1.4
Variables: \(F\) a functional signature
\(X\) a set of unknowns
Context: Graph structure

Name: A system of polynomial equations
Definition: A system of the form \(\langle x_1=p_1,\dots,x_n=p_n\rangle\) with \(p_i\)'s some polynomials
Page: 22
Section: 1.4
Variables: \(F\) a functional signature
\(X\) a set of unknowns
Context: Graph structure
Name2: An equation system

Name: A solution of \(S\)
Definition: An \(n\)-tuple \((L_1,\dots,L_n)\) with \(L_i\subseteq\mathcal P(M)\) that satisfies the equations of \(S\)
Page: 22
Section: 1.4
Variables: \(F\) a functional signature,
\(\mathbb M\) an \(F\)-algebra
\(X\) a set of unknowns,
\(S=\langle x_1=p_1,\dots,x_n=p_n\rangle \) a system of polynomial equations

Question: The set of solutions of \(S\) has
Answer: a least solution.
Page: 22
Chapter: 1
Section: 1.4
Variables: \(F\) a functional signature,
\(\mathbb M\) an \(F\)-algebra
\(X\) a set of unknowns,
\(S=\langle x_1=p_1,\dots,x_n=p_n\rangle \) a system of polynomial equations

Name: An equational set of \(\mathbb M\)
Definition: The least solution of an equation system.
Page: 23
Section: 1.4
Variables: \(F\) a functional signature,
\(\mathbb M\) an \(F\)-algebra

Name: The set of equational sets of \(\mathbb M\).
Page: 23
Section: 1.4
Variables: \(F\) a functional signature,
\(\mathbb M\) an \(F\)-algebra
Notation: [latex]\textbf{Equat}($\mathbb M$)[/latex]

Definition: The set of terms written with symbols of \(F\) and respect of arities.
Page: 23
Section: 1.4
Variables: \(F\) a functional signature
Notation: \(T(F)\)

Definition: The \(F\)-algebra \(\langle T(F), (f_{\mathbb T(F)})_{f\in F})\rangle \) where each function \(f_{\mathbb T(F)}\) consists in applying the term \(f\) to its arguments.
Page: 23
Section: 1.4
Variables: \(F\) a functional signature
Notation: \(\mathbb T(F)\)

Definition: \(f_{\mathbb M}(t_{1\mathbb M},\dots,t_{\rho(f)\mathbb M})\)
Page: 23
Section: 1.4
Variables: \(F\) a functional signature,
\(\mathbb M\) an \(F\)-algebra,
\(t=f(t_1,\dots,t_{\rho(f)})\in \)
Notation: \(t_{\mathbb M}\)
Notation2: \(val_{\mathbb M}\)

Name: Parse tree of \(w\)
Definition: Results of the syntactic analysis of \(w\).
Page: 25
Section: 1.5
Variables: \(w\) a word,
\(G\) a grammar

Name: A parsing algorithm for \(S\)
Definition: takes as input an element \(m\in M\),
Page: 25
Section: 1.5
Variables: \(F\) a functional vocabulary,
\(S\) be an equation system,
\(\mathbb M=\langle M,(f_{\mathbb M})_{f\in F}\rangle\) an algebra,
Definition2: computes a term \(t\) such that
Conjdef: An algorithm which
Definition3: \(t\) denotes \(m\) as specified by \(S\).
Hide remaining def: yes

Name: A derivation tree of \(w\)
Definition: \(r(p_{1},\dots, p_j)\) where \(r\) is the first rule applied to obtain \(w\), and \(p_i\) is the parse-tree obtained from the \(i\)-th non-terminal letter of the rule \(r\)
.
Page: 26
Section: 1.5
Variables: \(G=(A,N)\) a grammar,
\((r_i)\) a set of rules from \(N\) to an element of \((A+N)^*\)
\(w\) a word derived from \(G\)

Name: A parse tree of \(w\)
Definition: The tree whose head is the initial letter. Its childs are the parse tree of the rules applied.
Page: 26
Section: 1.5
Variables: \(G=(A,N)\) a grammar and a set of rules
\(w\) a word derived from \(G\)