TITLE: How to prove that a function is bijective?
QUESTION [1 upvotes]: I just began learning about mathematical proofs (the questions I have in homework are mainly about proving bijections between sets) and I found this subject extremely puzzling and confusing and it seems like I can't understand this damn subject...
I understand that if you show that if $f(a)=f(b)$, then $a=b$ and the function is injective. So if I have a function from set $A$ (which is the set of odd natural numbers (without zero)) to set $B$ (even natural numbers (without zero)) $f(a)=a+1$ then you show that it is injective by saying that $a=b$ if $f(a)=f(b)$ because we can take $f(a)=f(b) = a+1=b+1$ and remove $1$ from both sides and turn it to $a=b$. This is a "proof" that the function is injective? Why? Because I could use some operations to turn $a+1=b+1$ to $a=b$?. And how do you prove that a function is surjective?

REPLY [1 votes]: Yes that a correct proof for injectivity.
For sujectivity we need to prove that for every $n$ even exists $a$ odd such that $f(a)=a+1=n$ which is true.
Therefore $f$ is injective and surjective and thus invertible.


TITLE: Is there a Mizar-like sublanguage for Coq?
QUESTION [10 upvotes]: Isabelle has the frontend Isar which mimics some features of the Mizar system.
I'm curious if Coq has anything similar, i.e. an alternative to tactic scripts that's designed to be readable or similar to the mathematical vernacular.
This discussion on the Coq forums mentions Czar and SSReflect.

REPLY [11 votes]: There indeed used to be a "declarative language for Coq" often referred to as Czar, but it was removed (from Coq's core) a long time ago. If it had had any actual users, it would have been easy at the time to restore it as an external plugin though.
Having tested it when it was still there, my personal impression was that it was actually very difficult to use, and nowhere near what Isar has achieved for Isabelle. My understanding is that one of the main reason why Isar was so successful is thanks to SledgeHammer.
Fortunately today, Coq has CoqHammer (which is even available as part of the Coq Platform). Furthermore, Coq's tactics are pretty flexible for different styles. So, with a combination of tactics such as assert, enough, now_show, and CoqHammer tactics, it is actually possible to reconstruct the Isar style in Coq (no need for a specific proof mode for this).
Another declarative-style set of tactic is provided by the coq-waterproof package (see an example in their README). The proof style looks very much like mathematical text. However, while Czar was suffering from a lack of IDE support (it's almost impossible to remember exactly how to write a "natural language" proof in what is in fact a controlled language), coq-waterproof is a support package for the Waterproof IDE (which is targeted at students). So this might be close to what you are looking for, but for pedagogical purposes. If the goal is to reproduce the Isar style with productivity in mind, then I would still rather recommend relying on Coq's tactics like assert and enough + CoqHammer.
Finally, SSReflect was also mentioned. It is in fact very different from a declarative mode because it is very "procedural". However, the style in which SSReflect users write their proof is supposed to be close to the style of proofs in mathematical texts (one line per significant mathematical step) and reliance on the have: tactic to clarify the most important steps. The main difference between the SSReflect style and the Isar style is that SSReflect only relies on very small-scale automation, making the proofs in SSReflect very robust to evolution in the underlying Coq language, libraries or specifications.


TITLE: Prove that D is a linear transformation.
QUESTION [1 upvotes]: Let $S$ be the subspace formed by $e^x$,$xe^x$, and $x^2e^x$. Let $D$ be the differentiation operator on $S$. Prove that $D$ is a linear transformation.
I am not sure about my setup and confused with my result for scalar multiplication.
$T(0) = 0 \frac{d}{dx} = 0$
Let $u = a_0e^x + a_1xe^x+a_2x^2e^x$, $v= b_0e^x + b_1xe^x+b_2x^2e^x$.
Then, $T(u+v) = (a_0+b_0)e^x\frac{d}{dx} + (a_1+b_1)xe^x\frac{d}{dx} +(a_2+b_2)x^2e^x$
$\Rightarrow$.....$\Rightarrow$ $(a_0+a_1)e^x + (a_1+2a_2)xe^x + (a_2)x^2e^x + (b_0+b_1)e^x$...
$=T(u)+T(v)$
Then for, $T(cu) = ce^x\frac{d}{dx} + cxe^x\frac{d}{dx} + cx^2e^x\frac{d}{dx}$
we get, $\Rightarrow 2ce^x+ 3cxe^x + cx^2e^x$ ?

REPLY [2 votes]: Scalar multiplication....
you need to show that $T(c\mathbf u) = cT(\mathbf u)$
$\mathbf u = a_0 e^x + a_1 x e^x + a_2 x^2 e^x$
$T(\mathbf u) = (a_0 + a_1) e^x + (a_1 + 2a_2) x e^x + a_2 e^x\\
T(c\mathbf u) = (ca_0 + ca_1) e^x + (ca_1 + 2ca_2) x e^x + ca_2 e^x = cT(\mathbf u)$


TITLE: Prove that $2^x < \prod_{p\le x} p < (13/4)^x$ for sufficiently large x
QUESTION [4 upvotes]: Prove that $2^x < \prod_{p\le x} p < (13/4)^x$ for sufficiently large x. Here $p$ is prime.

So if we take logs we need to show for sufficiently large x, $x\log 2 < \sum_{p\le x}\log p < x\log(13/4)$. Also according to http://en.wikipedia.org/wiki/Primorial
Asymptotically, primorials ''pn#'' grow according to:
$p_n\# = e^{(1 + o(1)) n \log n}$
where $o(\cdot)$ is the little o notation.

REPLY [1 votes]: Rosser and Schoenfeld prove, in their Theorem 4, that
$$
x\left(1-\frac{1}{2 \log x}\right) < \vartheta(x) < x \left( 1+\frac{1}{2 \log x} \right)
$$
for $x\ge 563$, where
$$
\vartheta(x) =\sum_{p\le x} \log p.$$
This yields your required bounds.


TITLE: How to integrate$\int_0^1 \frac{\ln x}{x-1}dx$ without power series expansion
QUESTION [11 upvotes]: I happen to watch the video here,
which gives a solution to the definite integral below using the power series approach. Then answer is $\frac{\pi^2}{6}$, given by:

$$\int_0^1 \frac{\ln x}{x-1}dx=\int_{-1}^0 \frac{\ln(1+u)}{u}du=\sum_{n=0}^{\infty}\frac{1}{(n+1)^2}=\frac{\pi^2}{6},$$

where the power seires expansion of the function $\ln(1+u)$ is used.
I tried for some time, but could not find another approach. Does anyone know any alternative methods to evaluate above definite integral without using the infinite series expansion?
Any comments, or ideas, are really appreciated.

REPLY [0 votes]: Using diagamma function

$$\begin{align*}
& \color{blue}{I = \int_0^1 \frac {\ln x}{x-1}dx}\\
\end{align*}$$
Now,
$$\color{red}{\psi_0 (z) = -\gamma + \int_0^{1} \frac {x^{z-1}-1}{x-1}dx}$$
We'll differentiate and that is trigamma function $\psi_1(z)$
$$\implies \frac {\partial\psi_0}{\partial z}= \psi_1 (z) = \int_0^1 \frac {x^{z-1}\ln x}{x-1}dx$$
$$\color{green}{I = \left[\psi_1(z)\right]_{z=1} = \frac {\pi^2}{6}}$$
I have copied this answer from my old answer


TITLE: Analyzing the affine scheme Spec $K[x]_{(x)}$
QUESTION [1 upvotes]: I'm new to all this scheme stuff, so I'm trying to get a handle of them with what I think is supposed to be an easy example.
Let $K$ be a field, and let $R = K[x]_{(x)} = \{\frac{f(x)}{g(x)} | f(x), g(x) \in K[x], g(0) \neq 0\}.$ I know that Spec $R$ has two points, being the ideals $(0)$ and $(x).$ The topological space is also pretty small, containing the sets $\emptyset, \{(0)\},$ and $\{(0), (x)\} =$ Spec $R.$ However, I don't really understand the structure sheaf. I know that $\mathcal{O}_{\text{Spec } R}(\text{Spec } R) = R,$ but I don't know why. I also need help understanding why $\mathcal{O}_{\text{Spec } R}(\{(0)\}) = K(x).$ The definition I'm working with is to let $\mathcal{O}_{\text{Spec } R}(D(f))$ be the localization of the $R$ at the multiplicative set of all functions that do not vanish outside of $V(f).$ With that in mind, how can I calculate the structure sheaves here?

REPLY [1 votes]: $D(x)$ is an open set containing the prime ideals that don't contain $x$. In this case, $D(x) = \{(0)\}$. Therefore, $O_{Spec(R)}(0) = O_{Spec(R)}(D(x)) = R_x = (K[x]_{(x)})_x$.
Can you show this is isomorphic to $K(x)$ now?


TITLE: Understanding Conditional Probability Basics
QUESTION [0 upvotes]: In many online sources I've read a statement similar to:

Probability of B happening given A is equal to the probability of A and B both happening divided by B happening

or
$p(A | B) = p(A \cap B) / p(B)$
But what is the difference between "B happening given A" and "A and B happening at the same time" ? If B happens given A, didn't A and B happen at the same time ? Why is that chance smaller than the intersection ?

REPLY [2 votes]: "If B happens given A, didn't A and B happen at the same time?"  Yes that is true (or it could be true--it could also be considering sequential events--not necessarily simultaneous ones).  However, A and B happening together might be "unlikely" (really it just means they might not always happen together).
So consider that you have three outcomes and exactly two always occur together.  That is there are three possible outcomes: A and B, A and C, or B and C.  Now what is the probability that A occurs given that B occurs?  Well the probability that they both occur is $\frac{1}{3}$ (since A and B is only one possible outcome out of three).  But what is the probability that given that B occurs that A occurs?  Well there are only two events such that B occurs: either A and B or B and C.  Therefore given that B occurs the probability that A also occurs is $\frac{1}{2}$ (because you have excluded the possibility that A and C occur since you assumed B occurred).
This is indeed inline with Bayes' Theorem.  The probability of B occurring is $\frac{2}{3}$ and the probability of A and B occurring is $\frac{1}{3}$ therefore the probability of A given B is: $\frac{\frac{1}{3}}{\frac{2}{3}} = \frac{1}{2}$. (this is probably a poor example of Bayes' Theorem because, in this case, if you chose any two events, you'd always get $p(x|y \neq x) = \frac{1}{2}$)
Second Example: Independent Events
Consider that you flip a (fair) coin twice, sequentially.  What are the possible outcomes?  You can have $\{HH, TT, HT, TH\}$ (since it's a fair coin, each of these possibilities are equally likely--that's important here although we could extend to situations where they are not equally likely--but then we start getting more into the Bernoulli random variable rather than conditional probabilities).  What is the probability that you get a heads on the first flip?  Clearly from the above we get $\frac{2}{4} = \frac{1}{2}$.
Now, what is the probability that you flip a heads given that the first flip is heads?  There is only a single outcome that satisfies this (i.e. that you get two heads in a row).  However there is only one other event, $HT$, such that heads was rolled first, therefore the probability that you get a heads given that the first flip was heads is $\frac{1}{2}$.  Again, this is the same as the probability of two heads (heads both times), $\frac{1}{4}$, divided by the probability of getting heads the first time, $\frac{2}{4}$: $\frac{\frac{1}{4}}{\frac{2}{4}} = \frac{1}{2}$.
Indeed we see by the above that the probability of getting heads given an initial flip of heads is the same as the probability of getting heads on the second roll--both are $\frac{1}{2}$.  This tells us that each flip is independent of the other since the probability of getting heads isn't affected by the previous flip.


text:
\begin{document}

\title{The SCC-recursiveness Principle in Fuzzy Argumentation Frameworks\let\thefootnote\relax\footnotetext{E-mail address: wujiachao1981@163.com}}

\author
{Zongshun Wang, Jiachao Wu$^{*}$
\\
 \texttt{wujiachao1981@163.com}
 \\
 School of Mathematics and Statistics, Shandong Normal University,
\\
Jinan 250014, China
\\
}

  \date{}
\maketitle

\begin{abstract}
Dung's abstract argumentation theory plays a guiding role in the field of formal argumentation.
The properties of argumentation semantics have been deeply explored in the previous literature.
The SCC-recursiveness principle is a property of the extensions which relies on the graph-theoretical notion of strongly connected components.
It provides a general recursive schema for argumentation semantics, which is an efficient and incremental algorithm for computing the argumentation semantics.
However, in argumentation frameworks with uncertain arguments and uncertain attack relation, the SCC-recursive theory is absence.
This paper is an exploration of the SCC-recursive theory in fuzzy argumentation frameworks (FAFs), which add numbers as fuzzy degrees to the arguments and attacks.
In this paper, in order to extend the SCC-recursiveness principle to FAFs, we first modify the reinstatement principle and directionality principle to fit the FAFs.
Then the SCC-recursiveness principle in FAFs is formalized by the modified principles.
Additionally, some illustrating examples show that the SCC-recursiveness principle also provides an efficient and incremental algorithm for simplify the computation of argumentation semantics in FAFs.

Keywords: Fuzzy argumentation frameworks; Argumentation semantics; SCC-recursiveness principle

\end{abstract}

\section{introduction}

Dung's theory \cite{dung1995acceptability} of argumentation frameworks (AFs) played an increasingly important role in artificial intelligence.
This theory plays an incremental role in artificial intelligence and non-monotonic reasoning.

After Dung's pioneering paper, abstract AFs are extended in various ways.
For example, qualitative approaches extended Dung's AF by considering support relation between arguments \cite{amgoud2008bipolarity},
higher order attacks \cite{boella2008attack,baroni2011afra};
preferences \cite{amgoud2002reasoning}.
In order to handle the uncertainty, incompleteness, and inconsistency of information, various kinds of quantitative AFs are proposed.
More specifically, in quantitative AFs, numerical values are combined with arguments and attacks.
Quantitative approaches extended Dung's AF by considering probabilistic AFs \cite{hunter2013probabilistic,li2011probabilistic},
FAFs \cite{da2011changing,dondio2014multi,janssen2008fuzzy,wu2016godel},
weighted AFs \cite{dunne2011weighted} and so on.
In the current paper, we intend to explore some principles of quantitative AFs.

The SCC-recursiveness principle is provided by Baroni et al. in \cite{baroni2005scc}.
It is a property of the argumentation semantics which relies on the graph-theoretical notion of strongly connected components.
And it provides a general scheme for argumentation semantics and searches for novel semantics in AFs.

As for various quantitative AFs, the exploration of various principles is a gap.
In this paper, we explore the SCC-recursiveness principle in FAFs.
Intrinsically, this principle is based on the restatement principle and directionality principle.
Thus, we first modify the reinstatement principle and directionality principle to fit the FAFs.
Then, the SCC-recursiveness principle in FAFs is formalized by the modified principles.
By utilizing the SCC-recursiveness principle, each FAF is partitioned into many reduced sub-frameworks based on the graph-theoretical definition `strongly connected components'.
We then prove that the semantics of the FAF coincide with the combination semantics of these reduced sub-frameworks.
Therefore, the SCC-recursiveness principle provides efficient and incremental algorithms based on local computation at the level of strongly connected components.

The remaining part of this paper is structured as follows.
Section 2 reviews some basic concepts.
In Section 3, we establish the basic theory of the SCC-recursiveness principle in FAFs.
In Section 4, we provide the SCC-recursive semantics in FAFs.
In Section 5, we show some examples to illustrate the efficiency of the SCC-recursiveness principle in FAFs.
In Section 6, we discuss the distinction of the SCC-recursiveness principle between AFs and FAFs.
The paper ends with conclusions and remarks about future work.

\section{Preliminaries}

We recall some definitions of fuzzy set and fuzzy argumentation frameworks.

\subsection{Fuzzy Set Theory}
We only show some notions of fuzzy set theory \cite{zadeh1965fuzzy} that appear in this paper.

Let $X$ be a nonempty set.
A fuzzy set $(X, S)$ is determined by its membership function $S$: $X\rightarrow[0, 1]$, such that for each $x\in X$ the value $S(x)$ is interpreted as the grade of membership of $x$ within $X$.
Given some constant set X, we may denote a fuzzy set $(X, S)$ as $S$ for convenience.
A crisp set $S'$ is a classical set, namely for any $x\in X$, $S'(x)=0$ or $S'(x)=1$.

A fuzzy set $S$ is contained in another fuzzy set $S^{'}$, if $\forall x\in X$, $S(x)\le S^{'}(x)$.
And we denote the set inclusion by $S\subseteq S^{'}$.

A fuzzy set $S$ is called a fuzzy point if its support is a single point $x\in X$, and is denoted by $\big(x, S(x)\big)$. A fuzzy point $\big(x, S(x)\big)$ is contained in a fuzzy set $S$ if it is a subset of $S$.

In this paper, the t-norm is a binary operator on $[0,1]$.
In this paper, we focus on G\"{o}del t-norm.
G\"{o}del t-norm $T: [0,1]\times [0,1]\rightarrow [0,1]$ such that $\forall x, y\in [0,1]$, $T(x, y)=min\{x,y\}$.
For simplify, in this paper, we denote $*$ as G\"{o}del t-norm, namely for any $x, y\in [0,1]$, $x*y=T(x,y)=min\{x,y\}$.

\subsection{Fuzzy Argumentation Frameworks}

In this paper, our discussion is built on the argumentation systems given by \cite{wu2016godel}.

\begin{defn}
A fuzzy argumentation framework is a tuple $\langle\mathcal{A}, \rho\rangle$ where $\mathcal{A}: Args \rightarrow (0, 1]$ and $\rho: Args \times Args \rightarrow (0, 1]$ are total functions. We refer to $\mathcal{A}$ as a fuzzy set of arguments, and $\rho$ as a fuzzy set of attacks, while Args is a crisp set of arguments.
\end{defn}

From \cite{wu2016godel}, we call the elements in $\mathcal{A}$ fuzzy arguments and the elements in $\rho$ fuzzy attack.
And the extension semantics is established under the G{\"o}del t-norm.

An important distinction between the FAFs and AFs is that the attack relation may be ignored when we choose the acceptable arguments in FAFs.
In \cite{wu2016godel}, the connection between the fuzzy degree of $B$ and $\rho_{_{BA}}$ is selected to be the G{\"o}del t-norm $min$.
Then the tolerable and sufficient attacks are extended to general FAFs.

\begin{defn}
Given two fuzzy arguments $(A, a)$, $(B, b)$, and an attack $\big((A, B), \rho_{_{AB}}\big)$, if $\min\{a,\rho_{_{AB}}\}+b\le1$, then the attack is tolerable, otherwise it is sufficient.
\end{defn}

If $(A,a)$ sufficiently attacks $(B,b)$, then $B$'s degree $b$ should be revised.
The weakening relation is introduced as follows.

\begin{defn}

Suppose $(A, a)$ and $(B, b)$ are two fuzzy arguments in an $FAF$.
we say $(A, a)$ weakens $(B, b)$ to $(B, b')$, $b$ is revised to $b'$ where $b'= min\big\{1 - min\{a, \rho_{_{AB}}\}, b\big\}$.
\end{defn}

The acceptability in \cite{wu2016godel} is called the \emph{weakening defence}.
It indicates how a fuzzy set weakening defends a fuzzy argument.

\begin{defn}
Given an $FAF=\langle\mathcal{A}, \rho\rangle$, a fuzzy set $S\subseteq\mathcal{A}$ weakening defends a fuzzy argument $(C, c)$ in $\mathcal{A}$ if for any $(B, b) \in \mathcal{A}$ there is some $(A, a) \in S$ such that $(A, a)$ weakens $(B, b)$ to $(B, b^{'})$ and $(B, b^{'})$ tolerably attacks $(C, c)$.
\end{defn}

\begin{defn}
The characteristic function of a fuzzy argumentation frameworks $FAF=\langle\mathcal{A},\rho\rangle$ is a function F from the set of all the subsets of $\mathcal{A}$ to itself, such that $\forall S\subseteq \mathcal{A}$, $F(S) = \{(A, a) \mid S \text{ weakening defends } (A, a)\}$.
\end{defn}

In \cite{wu2016godel}, the extension-based approach to argumentation semantics in FAFs has been proposed. We list it as follows.

\begin{defn}
Given a $\emph{FAF}=\langle\mathcal{A},\rho\rangle$ and $S \subseteq \mathcal{A}$.

A fuzzy set S is a conflict-free set if all attacks between the fuzzy arguments in S are tolerable.

A conflict-free set S is an admissible extension if S weakening defends each element in S.

A conflict-free set S is a complete extension if it contains all the fuzzy arguments in $\mathcal{A}$ that S weakening defends.

An admissible extension is a preferred extension if it is maximal w.r.t. set inclusion.

A complete extension is a grounded extension if it is minimal w.r.t. set inclusion.

A conflict-free set E is stable if it sufficiently attacks every element in $\mathcal{A}$ not in E.
\end{defn}

Particularly, the stable extensions coincide with the preferred extensions.

\section{The Base Notions of the SCC-recursiveness Principle}

\subsection{Some Notations}

As described in \cite{baroni2005scc}, the SCC-recursiveness principle provides a general scheme for computing the argumentation semantics of AFs.
A Dung's AF is essentially a directed graph.
The SCC-recursiveness principle provides a decomposition of the directed graph by the graph-theoretical notion of \emph{strongly connected components}.
To begin with, we need to combine the fuzzy argumentation frameworks with graph theory.
Indeed, an FAF is essentially a directed graph that is combined with fuzzy degree (or weight).
For simplicity, we borrow some notations from \cite{baroni2005scc}.
And we reestablish these notations in fuzzy argumentation frameworks.

\begin{defn}
Given a fuzzy argumentation framework $FAF=\langle\mathcal{A},\rho\rangle$ and an argument $A\in Args$, we define $parents(A)=\{(B,\mathcal{A}(B))\mid \rho_{_{BA}}\neq 0\}$.
If $parents(A)=\emptyset$, then A is called an \emph{initial} node.
\end{defn}

\begin{defn}
Given a fuzzy argumentation framework $FAF=\langle\mathcal{A},\rho\rangle$, a fuzzy argument $(A,a)\in \mathcal{A}$ and two fuzzy sets S and P, we define:

S attacks $(A,a)$ if and only if $\exists (B,b)\in S$ s.t. $(B,A)\in Supp(\rho)$,

$(A,a)$ attacks S if and only if $\exists (B,b)\in S$ s.t. $(A,B)\in Supp(\rho)$,

S attacks P if and only if $\exists (A,a)\in S \text{ and } (B,b)\in P$ s.t. $(A,B)\in Supp(\rho)$,

S sufficiently attacks $(A,a)$ if and only if $\exists (B,b)\in S$ s.t. $(B,b)$ sufficiently attacks $(A,a)$,

$(A,a)$ sufficiently attacks S if and only if $\exists (B,b)\in S$ s.t. $(A,a)$ sufficiently attacks $(B,b)$,

$S_1$ sufficiently attacks $S_2$ if and only if $\exists (A,a)\in S_1 \text{ and } (B,b)\in S_2$ s.t. $(A,a)$ sufficiently attacks $(B,b)$,

$outparents_{FAF}(S)=\{(A,a)\in \mathcal{A}\mid A\notin Supp(S) \text{ and } (A,a) \text{ attacks }S\}$.
\end{defn}

We then introduce the notions of \emph{strongly connected components} in FAFs.

\begin{defn}
Given a fuzzy argumentation framework $FAF=\langle\mathcal{A},\rho\rangle$, the binary relation of path-equivalence between nodes, denoted as $PE_{FAF}\subseteq Args\times Args$, is defined as follows:
\begin{itemize}
  \item $\forall A\in Args$, $(A,A)\in PE_{FAF}$,
  \item given two distinct arguments $A,B\in Args,(A,B)\in PE_{FAF}$ if and only if there is a chain of attack relation from A to B and a chain of attack relation from B to A.
\end{itemize}
\end{defn}

\begin{defn}
The strongly connected components of FAF are the equivalence classes of nodes with the belief degree in $\mathcal{A}$ under the relation of path-equivalence.
Given a node $A\in Args$, we define the strongly connected component $A$ belongs to is denoted as $SCC_{FAF}(A)$ where $SCC_{FAF}(A)=\{(B,\mathcal{A}(B))\mid (A,B)\in PE_{FAF}\}$.
The set of the strongly connected components of FAF is denoted as $SCCS_{FAF}$.
\end{defn}

We extend to strongly connected components the notion of parents,
denoting the set of the other strongly connected components that attack a strongly connected component S as $sccparents_{FAF}(S)$,
and we introduce the definition of proper ancestors, denoted as $sccanc_{FAF}(S)$:

\begin{defn}
Given a fuzzy argumentation framework $FAF =\langle \mathcal{A},\rho\rangle$ and a strongly connected component $S\in SCCS_{FAF}$, we define
\begin{displaymath}
\begin{aligned}
sccpar & ents_{FAF}(S)=\{P\in SCCS_{FAF}\mid P\neq S \text{ and P attacks S}\} \\
sccanc & _{FAF}(S)=sccparents_{FAF}(S)\cup \bigcup\limits_{P\in sccparents_{FAF}(S)} sccanc_{FAF}(P)
\end{aligned}
\end{displaymath}
A strongly connected component S such that $sccparents_{FAF}(S)=\varnothing$ is called \emph{initial}.
\end{defn}

To formalize the decomposition of FAFs, we provide the definition of restriction of fuzzy argumentation frameworks:
\begin{defn}
Given a fuzzy argumentation framework $FAF=\langle\mathcal{A},\rho\rangle$, a fuzzy set $S\subseteq \mathcal{A}$. The restriction of FAF to S is the fuzzy argumentation framework
\begin{center}
${FAF\downarrow}_S=\langle S,\rho\cap\rho_{supp(S)}\rangle$
\end{center}
\end{defn}

\subsection{Basic Theory}

In the previous subsection, we combine the graph theory with fuzzy argumentation frameworks.
Based on the definition of strongly connected components of FAFs, all the fuzzy arguments of an FAF can be divided into several parts along the strongly connected components.
Then we should analyze the properties of these strongly connected components and formalize the SCC-recursiveness principle in this subsection.
Essentially, the SCC-recursiveness principle in Dung's AFs is based on the reinstatement principle and directionality principle.
However, due to the distinction of AFs and FAFs, we cannot apply these two principles directly to FAF.
We need to modify the reinstatement principle and directionality principle to fit the FAFs.
Thus, we first provide the basic notions of the reinstatement principle and the directionality principle in FAFs.

\textbf{Reinstatement principle of FAF}:
Given an argumentation semantics $\mathcal{S}$ and $E\in \mathcal{E}_{\mathcal{S}}(FAF)$.
If $(A,a)$ is chosen to the extension E and $(B,b)$ is sufficiently attacked by $(A,a)$,
we then have that at least $a*\rho_{_{AB}}$ belief degree of B should be limited so that it cannot be chosen to E.
And this part plays no role in the selection of fuzzy arguments to be included in E.
Namely, this part causes no influence in this system.
This is because this part is completely defeated by $(A,a)$ so that $(B,b)$ is always weakened to $(B,1-a*\rho_{_{AB}})$.
In addition, the relative attack relation w.r.t. B may be reduced since it may be always tolerable.
Then, we directly draw a conclusion: the maximal acceptable belief degree of B is limited to $1-a*\rho_{_{AB}}$.
If not, suppose $(B,b')\in E$ and $b'>1-a*\rho_{_{AB}}$, then $(A,a)$ sufficiently attacks $(B,b')$ clearly holds by  $b'+a*\rho_{_{BA}}>1-a*\rho_{_{AB}}+a*\rho_{_{BA}}=1$.
Therefore, $E$ violates the \emph{conflict-freeness}.
Thus, this statement implies that the limited part has no influence in the FAFs and the maximal acceptable belief degree of a generic argument cannot greater than the negation of the limited belief degree.
Taking into account the decomposition into strongly connected components,
the application of this principle can be examined considering separately,
for a given strongly connected component S, the limited part w.r.t. E inside and outside S.
Inside S, the principle entails that the limited part (denoted as $L_{FAF}(S,E)$) can be reduced from the strongly connected components.
Namely, we only need to consider the residual part (denoted as $R_{FAF}(S,E)$) of the strongly connected component S.
At the same time, it is notable that if the limited part $L_{FAF}(S,E)$ is reduced from the strongly connected component S, the power of the relevant attack relations may be suppressed.
This is because the relevant attack relation may cause no influence in the reduced system, i.e., the attack relation is always tolerable in the reduced FAF.
This implies that the selection within S of the fuzzy arguments to be included in an extension E has to be carried out on a sort of reduced FAF, consisting in $R_{FAF}(S,E)$,
completely reducing the limited part (i.e., $L_{FAF}(S,E)$).

\textbf{Directionality principle of FAF}:
The acceptable belief degree of an argument A only depends on the belief degrees of its attackers (which in turn are affected by their attackers and so on).
Thus, if there exists no path from B to A, then B has no influence on B.
Similar to Dung's AF, the complete, grounded and preferred semantics satisfy the directionality principle in FAF.
This is because $\forall E\in \mathcal{AE}_{\mathcal{CO}} (FAF,U)$, there exists no fuzzy argument in $E$ is sufficiently attacked by the fuzzy argument outside the unattacked set.
With reference to a given extension E, for any strongly connected component S of FAF, the choice of the subset of S to be included in E (i.e., $(E\cap S)$) only depends on the choices made in the strongly connected components of $sccanc_{FAF}(S)$, i.e., those that are antecedent to S in the acyclic graph made up of strongly connected components.

From the reinstatement principle and directionality principle of FAFs, with reference to a specific strongly connected component S, we can identify the part of fuzzy arguments that should be reduced from our system.
It is called `\emph{Limited Part}', denoted as $L_{FAF} (S,E)$, according to the reinstatement principle, it represents the belief degree of an argument that limited by the ancestor strongly connected components of S.
When reducing the limited part, the residual part is called as `\emph{Residual Part}'.
It represents the maximal belief degree of the arguments in S that cause influence in the reduced FAF.
The `\emph{Defended Part}' (denoted as $D_{FAF}$) of FAFs coincides with the defended arguments whose sufficiently attackers (out S) all are weakened to uncontroversial.
It represents the maximal belief degree of the arguments in S that can be chosen to a specific extension E.

\begin{defn}
Given a fuzzy argumentation framework $FAF=\langle\mathcal{A},\rho\rangle$, a fuzzy set $E\subseteq \mathcal{A}$ and a strongly connected component $S\in SCCS_{_{FAF}}$, we define:
\begin{itemize}
\setlength{\itemsep}{0pt}
\setlength{\parsep}{0pt}
\setlength{\parskip}{0pt}
  \item $L_{FAF} (S,E)=\{(A,a)\in S\mid\exists (B,b)\in E\cap outparents_{FAF}(S),a=\max \limits_{B \in Args} b*\rho_{_{BA}}\}$
  \item $R_{FAF} (S,E)=\{(A,a)\in S\mid a=min\{\mathcal{A}(A),1-L_{FAF} (S,E)(A)\}\}$.
  \item $D_{FAF} (S,E)=\{(A,a)\in R_{FAF} (S,E)\mid \forall (B,b)\in outparents_{FAF}(S),$ $\text{ if }(B,b)$ sufficiently attacks $(A,a)$,
then $\exists (C,c)\in E$ s.t. $c*\rho_{_{CB}}=a$, i.e., $(B,b)$ is weakened to uncontroversial with $(A,a)$ by $(C,c)$\}.
\end{itemize}

\end{defn}

From the above definition, the fuzzy set $L_{FAF}(S,E)$ consists of the fuzzy arguments of S attacked by E from outside S, i.e., it represents the belief degree of each argument that is limited by E outside S.
The fuzzy set $R_{FAF}(S,E)$ consists of the fuzzy arguments of S that are not limited by E from outside S, i.e., it represents the residual degree of each argument that is not limited by E outside S.
And the fuzzy set $D_{FAF}(S,E)$ consists of the fuzzy arguments in $R_{FAF}(S,E)$ that are not limited by E from outside S and are defended by E (i.e., their sufficient attackers (out S) are weakened to uncontroversial with the fuzzy arguments in $D_{FAF}(S,E)$ by E).
It is easy to verify that $L_{FAF}(S,E)$, $R_{FAF}(S,E)$ and $D_{FAF}(S,E)$ are determined only by the elements of E that belong to the strongly connected components in $sccanc_{FAF}(S)$.

From the above statement, the SCC-recursiveness principle of FAFs then can be introduced as follows:

\begin{defn}\label{The base definition of SCC-recursiveness in FAF}
A given argumentation semantics $\mathcal{S}$ is SCC-recursive if and only if for any fuzzy argumentation frameworks $FAF=\langle\mathcal{A},\rho\rangle$, $\mathcal{E}_\mathcal{S}(FAF)=\mathcal{GF}(FAF,\mathcal{A})$, where for any $FAF=\langle\mathcal{A},\rho\rangle$ and for any set $C\subseteq \mathcal{A}$, the function $\mathcal{GF}(FAF,C)\subseteq 2^\mathcal{A}$ is defined as follows:

\noindent for any $E\subseteq \mathcal{A}$, $E\in \mathcal{GF}(FAF,C)$ if and only if
\begin{itemize}
\item in case $|SCCS_{FAF}|=1$, $E\in \mathcal{BF}_\mathcal{S}(FAF, C)$,
\item otherwise, $\forall S\in SCCS_{FAF}$, $(E\cap S)\in \mathcal{GF}(FAF\downarrow_{R_{FAF}}(S,E),D_{FAF}(S,E)\cap C)$.
\end{itemize}
where $\mathcal{BF}_\mathcal{S}(FAF, C)$ is a function, called base function, that, given a fuzzy argumentation framework $FAF=\langle\mathcal{A},\rho\rangle$ such that $|SCCS_{FAF}|=1$ and a set $C\subseteq \mathcal{A}$, gives a subset of $2^\mathcal{A}$.
\end{defn}

Notably, the set of the extensions of the original fuzzy argumentation framework coincides with $\mathcal{GF}(FAF,\mathcal{A})$.
This is because there exists no outer attacker of $\mathcal{A}$.
The fuzzy set C thus coincides with $\mathcal{A}$.
It is notable that the definition of $\mathcal{GF}(FAF,C)$ is recursive with respect to the decomposition of FAF into strongly connected components.
From Definition \ref{The base definition of SCC-recursiveness in FAF}, $\mathcal{GF}(FAF,C)$ is applied to progressively more restricted FAFs.
In particular, the base of the recursion is given by the function $\mathcal{BF}_S(FAF,C)$, which returns the extensions of a generic FAF consisting of a unique strongly connected component.

Now, based on the SCC-recursiveness principle, we provide the general recursive scheme for computing the argumentation semantics according to the corresponding base function.
And the scheme is efficient by utilizing the reinstatement principle and directionality principle.
First, as far as the initial strongly connected components are concerned, for any initial strongly connected component S, since by definition there are no outer attacks, we have that $R_{FAF}(S,E) = D_{FAF}(S,E) = S$.
This gives rise to the invocation $\mathcal{GF}(FAF\downarrow_{S},S)$.
Since $FAF\downarrow_{S}$ obviously consists of a unique strongly connected component, according to Definition \ref{The base definition of SCC-recursiveness in FAF} the base function $\mathcal{BF}_S(FAF\downarrow_{S},S)$ is invoked, which returns the extensions of $FAF\downarrow_{S}$ according to the semantics S.
Therefore, the set of all the extensions of the initial strongly connected components can be computed by the base function of the specific semantics S.
Then the results of the initial strongly connected components are used to identify the subsequent restricted FAFs within the subsequent strongly connected components.

According to Definition \ref{The base definition of SCC-recursiveness in FAF}, the application procedure of the SCC-recursive scheme can be summarized as follows:
\begin{enumerate}
\setlength{\itemsep}{0pt}
\setlength{\parsep}{0pt}
\setlength{\parskip}{0pt}
  \item the FAF is partitioned into its strongly connected components; they form a partial order which encodes the dependencies existing among them according to the directionality principle;
  \item the possible choices for extensions within each initial strongly connected component are determined using a semantic-specific base function which returns the extensions of FAFs consisting of a single strongly connected component;
  \item for each possible choice determined at step 2, according to the reinstatement principle, the fuzzy arguments directly attacked within subsequent strongly connected components are limited and the fuzzy arguments with residual degree are taken into account;
  \item the steps 1–3 above are applied recursively on the restricted FAFs obtained at step 3.
\end{enumerate}

\section{The SCC-recursive Semantics in FAFs}

\subsection{Generalized Theory of Fuzzy Argumentation Frameworks}

Following \cite{baroni2005scc}, in order to develop an SCC-recursive characterization of semantics, it is necessary to redefine \emph{fuzzy argumentation frameworks} in generalized terms, by restating its fundamental concepts with reference to a specific subset $C\subseteq \mathcal{A}$,
from which acceptable fuzzy arguments (that compose the extensions) are selected
since it represents the subset of defended fuzzy arguments within $\mathcal{A}$.
Original FAF can be recovered letting $C =\mathcal{A}$.

Given an $FAF =\langle \mathcal{A},\rho\rangle$ and a set $C\subseteq \mathcal{A}$, we define admissible sets in C as follows:

\begin{defn}\label{the admissible extension in C}
Given an $FAF =\langle \mathcal{A},\rho\rangle$ and a set $C\subseteq \mathcal{A}$, a set $E\subseteq \mathcal{A}$ is an admissible set in C if and only if $E\subseteq C$ and $E\in \mathcal{AS}(FAF)$.
The set of admissible sets in C is denoted as $\mathcal{AS}(FAF,C)$.
\end{defn}

We introduce now the notion of complete, grounded, and preferred extensions in the generalized fuzzy argumentation frameworks.

\begin{defn}\label{the complete extension in C}
Given an $FAF =\langle \mathcal{A},\rho\rangle$ and a set $C\subseteq \mathcal{A}$,
a set $E\subseteq \mathcal{A}$ is a complete extension in C if and only if $E\in \mathcal{AS}(FAF,C)$,
and every argument $(A,a)\in C$ which is acceptable with respect to E belongs to E.
The set of complete extensions in C is denoted as $\mathcal{CE}(FAF,C)$.
\end{defn}

\begin{defn}\label{the preferred extension in C}
Given an $FAF =\langle \mathcal{A},\rho\rangle$ and a set $C\subseteq \mathcal{A}$,
a preferred extension in C is a maximal element (with respect to set inclusion) of $\mathcal{AS}(FAF,C)$.
The set of preferred extensions in C is denoted as $\mathcal{PE}(FAF,C)$.
\end{defn}

The following theorem shows that for any fuzzy argumentation frameworks FAF and for any set $C\subseteq \mathcal{A}$, the preferred extensions always exist.

\begin{thm}\label{the existense of preferred extensions}
Given an $FAF =\langle \mathcal{A},\rho\rangle$ and a set $C\subseteq \mathcal{A}$:
\begin{itemize}
  \item The elements of $\mathcal{AS}(FAF,C)$, i.e., the admissible subsets of C, form a complete partial order.
  \item For all $F\in\mathcal{AS}(FAF,C)$, there is $E\in \mathcal{PE}(FAF,C)$ such that $F\subseteq E$.
\end{itemize}
\end{thm}

Also in the generalized FAF, the grounded semantics can be defined in terms of the least fixed point of the characteristic function.

\begin{defn}
Given an $FAF =\langle \mathcal{A},\rho\rangle$ and a set $C\subseteq \mathcal{A}$, the function

\begin{itemize}
  \item $F_{FAF,C}:2^C\rightarrow 2^C$
  \item $F_{FAF,C}(S)=\{(A,a)\mid (A,a)\in C, (A,a) \text{ is acceptable with respect to } S\}$
\end{itemize}
is called the characteristic function of FAF in C.
\end{defn}

It is easy to see that $F_{FAF,C}$ is monotonic (with respect to set inclusion).

\begin{cor}
Given a fuzzy argumentation framework $FAF =\langle \mathcal{A},\rho\rangle$ and a set $C\subseteq \mathcal{A}$, $\mathcal{PE}(FAF,C)$ is nonempty, i.e., there is always a preferred extension $E\in \mathcal{PE}(FAF,C)$.
\end{cor}

\begin{defn}
Given a fuzzy argumentation framework $FAF =\langle \mathcal{A},\rho\rangle$ and a set $C\subseteq \mathcal{A}$, the function
\begin{displaymath}
\begin{aligned}
&F_{FAF,C}:2^C\rightarrow 2^C\\
&F_{FAF,C}(S)=\{(A,a)\mid (A,a)\in C, (A,a) \text{ is acceptable with respect to S}\}
\end{aligned}
\end{displaymath}
is called the \emph{characteristic function} of FAF in C.
\end{defn}

\begin{defn}\label{the grounded extension in C}
Given an $FAF =\langle \mathcal{A},\rho\rangle$ and a set $C\subseteq \mathcal{A}$,
the grounded extension of FAF in C, denoted as $GE(FAF,C)$, is the least (with respect to set inclusion) fixed point of $F_{FAF,C}$.
\end{defn}

Notice that by definition $GE(FAF,C)\subseteq C$. The following lemma shows that for any fuzzy argumentation frameworks FAF and for any set $C\subseteq \mathcal{A}$, the grounded extension always exists.

\begin{lem}\label{Grounded Lemma}
For any fuzzy argumentation framework $FAF =\langle \mathcal{A},\rho\rangle$ and for all sets $C\subseteq \mathcal{A}$,
$GE(FAF,C)$ exists and is unique.
\end{lem}

Finally, the following relations between grounded, preferred and complete extensions can be concluded:
\begin{prop}\label{Grounded}
Given an $FAF =\langle \mathcal{A},\rho\rangle$ and a set $C\subseteq \mathcal{A}$,
$GE(FAF,C)$ is the least (with respect to set inclusion) complete extension in C.
\end{prop}

\begin{prop}\label{Preferred}
Given an $FAF =\langle \mathcal{A},\rho\rangle$ and a set $C\subseteq \mathcal{A}$,
the preferred extensions $\mathcal{PE}(FAF,C)$ are the maximal (with respect to set inclusion) complete extensions in C.
\end{prop}

Since the original definitions are recovered by letting $C = \mathcal{A}$,
an SCC-recursive formulation of the extended definitions also covers the original ones.

\subsection{Admissible Semantics}

Since admissibility plays a basic role in argumentation semantics theory, we first characterize that admissible semantics are SCC-recursive.
And the characterization of admissible semantics based on SCC-recursiveness is the basis of the analysis of other semantics.
This is achieved by Proposition \ref{admissible proposition}, which requires two preliminary lemmas.

\begin{lem}\label{the lemma for the right arrow of admissible}
Given a fuzzy argumentation framework $FAF=\langle\mathcal{A},\rho\rangle$, an admissible extension of arguments $E\in \mathcal{AE}(FAF)$,
and a fuzzy argument $(A,a)\in F_{FAF}(E)$ is weakening defended by E, denoting $SCC_{FAF}(A)$ as S, it holds that:

\begin{itemize}
  \item $(A,a)\in D_{FAF}(S,E)$;
  \item $(A,a)$ is weakening defended by $(E\cap S)$ in the fuzzy argumentation framework $FAF\downarrow_{R_{FAF}(S,E)}$, i.e., $(A,a)\in F_{FAF\downarrow_{R_{FAF}(S,E)}} (E\cap S)$.
\end{itemize}
\end{lem}
\begin{proof}
We first show that $(A,a)\in R_{FAF}(S,E)$, i.e., $a\leq min\{\mathcal{A}(A),1-L_{FAF}(S,E)(A)\}$.
$a\leq \mathcal{A}(A)$ is evident.
From the definition of $L_{FAF}(S,E)$, we have that $\exists (C,c)\in E$ s.t. $c*\rho_{_{CA}}=L_{FAF}(S,E)(A)$.
If $a>1-L_{FAF}(S,E)(A)$, then $c*\rho_{_{CA}}+a>c*\rho_{_{CA}}+1-L_{FAF}(S,E)(A)= 1$, i.e., $(A,a)$ is sufficiently attacked by $(C,c)$.
Namely, there exists a fuzzy argument $(C,c)\in E$ sufficiently attacks $(A,a)$.
From the definition of characteristic function, we have that $\exists(D,d)\in E$ sufficiently attacks $(C,c)$.
Contradicted to that $E\in \mathcal{AE}(FAF)$.
From the definition of characteristic function and $(A,a)\in F_{FAF}(E)$, we have that for any $(B,b)$ sufficiently attacks $(A,a)$, there exists an fuzzy argument $(C,c)\in E$ s.t. $(B,b)$ is weakened by $(C,c)$ and then it is uncontroversial with $(A,a)$.
Therefore, for any $(B,b)\in outparents(S)$, if $(B,b)$ sufficiently attacks $(A,a)$, then there exists $(C,c)\in E$ s.t. $c*\rho_{_{CB}}=a$.
Namely $(B,b)$ is weakened to uncontroversial with $(A,a)$ by $(C,c)$.
Thus $(A,a)\in D_{FAF}(S,E)$.

Turning to the second part of the proof, since $E\in \mathcal{AE}(FAF)$, we have that all the elements of $E$ is acceptable w.r.t. $E$, i.e., $\forall (A,a)\in E$, $(A,a)\in F_{FAF}(E)$.
Thus, the first part of this lemma entails that $(E\cap S)\subseteq D_{FAF}(S,E)$.
Therefore $(E\cap S)$ is actually a set of fuzzy arguments in the fuzzy argumentation framework $FAF\downarrow_{R_{FAF}(S,E)}$.
For a generic fuzzy argument $(B,b)$ that sufficiently attacks $(A,a)$ in $FAF\downarrow_{R_{FAF}(S,E)}$, since $(A,a)\in F_{FAF}(E)$, there exists a fuzzy argument $(C,c)$ s.t. $c*\rho_{_{CB}}=a$.
Namely $(B,b)$ is weakened by $(C,c)$ and then it is uncontroversial with $(A,a)$ in FAF.
Since $(B,b)\in R_{FAF}(S,E)$, by the definition of $R_{FAF}(S,E)$, we have that there exists no fuzzy argument $(C,c)\in E$ outside S that sufficiently attacks $(B,b)$.
Thus, $(C,c)\in (E\cap S)$, and $c*\rho_{_{CB}}=a$.
Namely, $(A,a)$ is weakening defended by $(E\cap S)$ in $R_{FAF}(S,E)$, i.e., $(A,a)\in F_{FAF\downarrow_{R_{FAF}(S,E)}} (E\cap S)$.
\end{proof}
\begin{lem}\label{the lemma for the left arrow of admissible}
Given a fuzzy argumentation framework $FAF=\langle\mathcal{A},\rho\rangle$, let $E\subseteq \mathcal{A}$ be a set of fuzzy arguments such that  $\forall S\in SCCS_{FAF}$
\begin{center}
  $(E\cap S)\in \mathcal{AE}(FAF\downarrow_{R_{FAF}(S,E)}, D_{FAF}(S,E))$
\end{center}

Given a strongly connected component $\hat{S} \in SCCS_{FAF}$ and a fuzzy argument $(A,a)\in D_{FAF}(\hat{S},E)$ which is weakening defended by $(E\cap \hat{S})$ in the fuzzy argumentation framework $FAF\downarrow_{R_{FAF}(\hat{S},E)}$, i.e., $(A,a)\in F_{FAF\downarrow_{R_{FAF}}(\hat{S},E)}(E\cap \hat{S})$, $(A,a)$ is acceptable with respect to E in $FAF$, i.e., $(A,a)\in F_{FAF}(E)$.
\end{lem}

\begin{proof}
With reference to the fuzzy argumentation framework $\emph{FAF}$,
we have to prove that for any fuzzy argument $(B,b)$ sufficiently attacks $(A,a)$,
then there exists a fuzzy argument $(C,c)\in E$ s.t. $c*\rho_{_{CB}}=a$.
Namely $(B,b)$ is weakened by $(C,c)$ and then it is uncontroversial with $(A,a)$ in $FAF$.
We distinguish two cases for $(B,b)$.

First, let us support that $(B,b)\in SCC_{FAF}(A)=\hat{S}$.
If $(B,b)\notin R_{FAF}(\hat{S},E)$, namely $b>1-L_{FAF}(\hat{S},E)(A)$.
According to the definition of $L_{FAF}(\hat{S},E)$, then there exists a fuzzy argument $(C,c)\in E$ s.t. $(B,b)$ is weakened to $(B,b')$ and $(B,b')\in R_{FAF}(\hat{S},E)$.
If, on the other hand, $(B,b)\in R_{FAF}(\hat{S},E)$, then $(B,b)$ sufficiently attacks $(A,a)$ also holds in $FAF\downarrow_{R_{FAF}(\hat{S},E)}$,
therefore according to the hypothesis of acceptability concerning $(A,a)$ it must be the case that $\exists (D,d)\in (E\cap \hat{S})$ s.t. $d*\rho_{_{DB}}=a$ holds in $FAF\downarrow_{R_{FAF}(\hat{S},E)}$.
Obviously, such relation holds also in $FAF$, namely  $(A,a)$ is acceptable with respect to $E$ in $FAF$.

Let us consider the other case, $B\notin SCC_{FAF}(A)=\hat{S}$.
In this case, $(B,b)\in (outparents_{FAF}(\hat{S})\cap parents_{FAF}(A))$, while by the hypothesis $(A,a)\in D_{FAF}(\hat{S},E)$:
on the basis of the definition of $D_{FAF}(\hat{S},E)$, it must be the case that $\exists (C,c)\in E$ s.t. $c*\rho_{_{CB}}=a$ in $FAF$,
 namely  $(A,a)$ is acceptable with respect to $E$ in $FAF$.
The proof is complete.
\end{proof}
\begin{prop}\label{admissible proposition}
Given a fuzzy argumentation framework $FAF=\langle\mathcal{A},\rho\rangle$ and a set of fuzzy arguments $E\subseteq \mathcal{A}$, $\forall C\subseteq \mathcal{A}$, $E\in \mathcal{AE}(FAF, C)$ if and only if $\forall S\in SCCS_{FAF}$
\begin{displaymath}
(E\cap S)\in \mathcal{AE}(FAF\downarrow_{R_{FAF}(S,E)},D_{FAF}(S,E)\cap C)
\end{displaymath}

\end{prop}
\begin{proof}
$``\Rightarrow"$: If $E\in \mathcal{AE}(FAF, C)$, then we need prove that $\forall S\in SCCS_{FAF}$, $(E\cap S)\in \mathcal{AE}({FAF\downarrow}_{R_{FAF}(S,E)},D_{FAF}(S,E)\cap C)$.
According to the definition of $\mathcal{AE}(FAF, C)$, $E\subseteq C$ and $\forall (A,a)\in E$, $(A,a)$ is weakening defended by E,
namely $(A,a)\in F_{FAF}(E)$. From the Lemma \ref{the lemma for the right arrow of admissible},
we have that $\forall (A,a)\in (E\cap S)$, $(A,a)\in D_{FAF}(S,E)$.
Therefore $(E\cap S)\subseteq (D_{FAF}(S,E)\cap C)$.
Moreover, from the same lemma,
we have that $(A,a)$ is weakening defended by $(E\cap S)$ in the fuzzy argumentation framework $FAF\downarrow_{R_{FAF}(S,E)}$.
Furthermore, since that E is admissible and therefore conflict-free, entails that $(E\cap S)$ is admissible in ${FAF\downarrow}_{R_{FAF}(S,E)}$.
Hence, $(E\cap S)\in \mathcal{AE}(FAF\downarrow_{R_{FAF}(S,E)},D_{FAF}(S,E)\cap C)$.
$``\Leftarrow"$: If $\forall S\in SCCS_{FAF}$, $(E\cap S)\in \mathcal{AE}(FAF\downarrow_{R_{FAF}(S,E)},D_{FAF}(S,E)\cap C)$, then we have $(E\cap S)\subseteq (D_{FAF}(S,E)\cap C)\subseteq (S\cap C)$, therefore $E\subseteq C$. As a consequence, the next step is to prove that E is an admissible extension in FAF.
If E is not conflict-free, then there exists $(A,a),(B,b)\in E$ s.t. $(B,b)$ sufficiently attacks $(A,a)$. We denote $SCC_{FAF}(A)$ as S. Evidently that $(B,b)\notin S$, if not, in this case $(A,a),(B,b)\in (S\cap E)$ and $(S\cap E)$ is an admissible extension in ${FAF\downarrow}_{R_{FAF}(S,E)}$. Contradiction!
Thus $(B,b)\notin S$.
Then we have $(B,b)\in outparents(S)\cap E$.
Since $(A,a)\in D_{FAF}(S,E)$, from the definition of $D_{FAF}(S,E)$,
we have that $(B,b)$ is weakened by $E\cap parents(B)$, namely $(B,b)$ is sufficiently attacked by an argument in E.
As well as the fact that $(B,b)\in(E\cap SCC_{FAF}(B))\in \mathcal{AE}(FAF\downarrow_{R_{FAF}(SCC_{FAF}(B),E)},D_{FAF}(SCC_{FAF}(B),E)\cap C)$,
we have that $(B,b)\in D_{FAF}(SCC_{FAF}(B),E)$.
Thus from the similar analysis, there exists a fuzzy argument $(C,c)\in E\cap SCC_{FAF}(C)\neq SCC_{FAF}(B)$ s.t. $(C,c)$ sufficiently attacks $(B,b)$.
Hence we consider that the $SCCS_{FAF}$ is not infinite. There will always exists two fuzzy arguments $(F,f),(G,g)\in SCC_{FAF}(F)(=SCC_{FAF}(G))\cap E$ and $(F,f)$ sufficiently attacks $(G,g)$.
However, this contradicts to the fact that $(F,f),(G,g)\in (SCC_{FAF}(F)\cap E)\in \mathcal{AE}(FAF\downarrow_{R_{FAF}(SCC_{FAF}(F),E)},D_{FAF}(SCC_{FAF}(F),E)\cap C)$.
Then we prove that for any $(A,a)\in E$, $(A,a)$ is weakening defended by E.
If we denote $SCC_{FAF}(A)$ as S, we have that $(A,a)\in (E\cap S)$. From that $(E\cap S)\in \mathcal{AE}(FAF\downarrow_{R_{FAF}(S,E)}, D_{FAF}(S,E))$, $(A,a)\in D_{FAF}(S,E)$ and $(A,a)$ is weakening defended by $E\cap S$ in $FAF\downarrow_{R_{FAF}(S,E)}$.
Since that $\forall S\in SCCS_{FAF}$, $(E\cap S)\in \mathcal{AE}(FAF\downarrow_{R_{FAF}(S,E)},D_{FAF}(S,E)$
$\cap C)$, Lemma \ref{the lemma for the left arrow of admissible} can be applied to $(A,a)$, entailing that $(A,a)$ is weakening defended by $E$ in $FAF$.
Hence, $E$ is an admissible extension of $FAF$ in $C$.
\end{proof}

\subsection{Complete Semantics}

The following proposition shows that complete extensions also fit the SCC-recursiveness principle.

\begin{prop}\label{Complete Proposition}
Given a fuzzy argumentation framework $FAF=\langle\mathcal{A},\rho\rangle$ and a set of fuzzy arguments $E\subseteq \mathcal{A}$, $\forall C\subseteq \mathcal{A}$, $E\in \mathcal{CE}(FAF, C)$ if and only if $\forall S\in SCCS_{FAF}$
\begin{displaymath}
(E\cap S)\in \mathcal{CE}(FAF\downarrow_{R_{FAF}(S,E)},D_{FAF}(S,E)\cap C)
\end{displaymath}
\end{prop}

\begin{proof}
As for the first direction of the proof, if $E\in \mathcal{CE}(FAF, C)$ then in particular $E\in \mathcal{AE}(FAF, C)$, therefore Proposition \ref{admissible proposition} entails that
\begin{equation}\label{1}
  \forall S\in SCCS_{FAF}\text{ } (E\cap S)\in \mathcal{AE}(FAF\downarrow_{R_{FAF}(S,E)},D_{FAF}(S,E)\cap C) \tag{1}
\end{equation}
As a consequence, we have only to show that $\forall (A,a)\in (D_{FAF}(S,E)\cap C)$ such that $(A,a)$ is acceptable with respect to $(E\cap S)$ in $FAF\downarrow_{R_{FAF}(S,E)}$, $(A,a)\in (E\cap S)$.
First, we notice that Lemma \ref{the lemma for the left arrow of admissible} can be applied to $(A,a)$, since Equation (\ref{1}) entails that
$\forall S\in SCCS_{FAF}$ $(E\cap S)\in \mathcal{AE}(FAF\downarrow_{R_{FAF}(S,E)},D_{FAF}(S,E)\cap C)$.
On the basis of this lemma, $(A,a)$ is acceptable with respect to $E$ in $FAF$, i.e., $(A,a)\in F_{FAF}(E)$.
Moreover, $(A,a)\in (D_{FAF}(S,E)\cap C)$, therefore in particular $(A,a)\in C$.
As a consequence, from the hypothesis that $E\in \mathcal{CE}(FAF,C)$ it follows that $(A,a)\in E$ and therefore $(A,a)\in (E\cap S)$.
As for the other direction of the proof, according to Definition \ref{the complete extension in C} we have that $\forall S\in SCCS_{FAF}$ the following conditions hold:
\begin{equation}\label{2}
 (E\cap S)\in \mathcal{AE}(FAF\downarrow_{R_{FAF}(S,E)},D_{FAF}(S,E)\cap C) \tag{2}
\end{equation}
\begin{equation}\label{3}
 \forall (A,a)\in (D_{FAF}(S,E)\cap C): (A,a)\in F_{FAF\downarrow_{R_{FAF}(S,E)}}(E\cap S), (A,a)\in (E\cap S) \tag{3}
\end{equation}
Thus, on the basis of Equation \ref{2} Proposition \ref{admissible proposition} entails that $E\in \mathcal{AE}(FAF,C)$,
therefore we have only to prove that $\forall (A,a)\in C$ such that $(A,a)$ is acceptable with respect to $E$, $(A,a)\in E$,
i.e., $\forall (A,a)\in C: (A,a)\in F_{FAF}(E), (A,a)\in E$.
Denoting $SCC_{FAF}(A)$ as S, on the basis of Lemma \ref{the lemma for the right arrow of admissible} we have that $(A,a)\in D_{FAF}(S,E)$,
so that $(A,a)\in (D_{FAF}(S,E)\cap C)$, and $(A,a)$ is acceptable with respect to $(E\cap S)$ in $FAF\downarrow_{R_{FAF}(S,E)}$,
i.e., $(A,a)\in F_{FAF\downarrow_{R_{FAF}(S,E)}}(E,S)$.
Then, taking into account Equation \ref{3} we have that $(A,a)\in (E\cap S)$, therefore $(A,a)\in E$.
\end{proof}

\subsection{Preferred Semantics}

In this subsection, we show that the preferred extensions also fit the SCC-recursive decomposition scheme,
as shown by Proposition \ref{Preferred Proposition} based on the following lemma.

\begin{lem}\label{Preferred Lemma}
Given a fuzzy argumentation framework $FAF =\langle\mathcal{A},\rho\rangle$, an admissible set $E\in \mathcal{AE}(FAF)$, and a strongly connected component $S\in SCCS_{FAF}$, let $\hat{E}$ be a set of arguments such that:
\begin{itemize}
\setlength{\itemsep}{0pt}
\setlength{\parsep}{0pt}
\setlength{\parskip}{0pt}
  \item $(E\cap S)\subseteq \hat{E} \subseteq D_{FAF}(S,E)$;
  \item $\hat{E}$ is admissible in the fuzzy argumentation framework $FAF\downarrow_{R_{FAF}(S,E)}$, i.e., $\hat{E}\in \mathcal{AE}(FAF\downarrow_{R_{FAF}(S,E)})$.
\end{itemize}
It holds that $E\cup \hat{E}$ is admissible in $FAF$, i.e., $E\cup \hat{E}\in \mathcal{AE}(FAF)$.
\end{lem}

\begin{proof}
First, we prove that $(E\cup \hat{E})$ is conflict-free.
Evidently, $\hat{E}$ is conflict-free in $FAF\downarrow_{R_{FAF}(S,E)}$ by the hypothesis.
As a consequence, $\hat{E}$ is conflict-free also in FAF.
Since also $E$ is conflict-free in FAF by the hypothesis of admissibility,
we have to prove that $E$ doesn't sufficiently attack $\hat{E}$ and $\hat{E}$ doesn't sufficiently attack $E$, namely there exists no fuzzy arguments $(A,a)\in E$ and $(B,b)\in \hat{E}$ s.t. $(A,a)$ sufficiently attacks $(B,b)$ or $(B,b)$ sufficiently attacks $(A,a)$.
Since E is admissible in $FAF$, $\hat{E}$ sufficiently attacks $E$ entails that $E$ sufficiently attacks $\hat{E}$, therefore we have only to prove that $E$ sufficiently attacks $\hat{E}$.
Since $\hat{E}\subseteq D_{FAF}(S,E)$, $E\cap outparents(S)$ doesn't sufficiently attack $\hat{E}$. Otherwise $E$ is not conflict-free since the  sufficient attacker in $E\cap outparents(S)$ is sufficiently attacked by $E$ which contradict to that $E$ is admissible.
Therefore, $E$ sufficiently attacks $\hat{E}$ only if $E\cap S$ sufficiently attacks $\hat{E}$.
However, the situation is impossible since $(E\cap S)\in \hat{E}$ and $\hat{E}$ is conflict-free.

Now, with reference to the fuzzy argumentation framework FAF we have to prove that $\forall (A,a)\in E\cup \hat{E}$, for any $(B,b)$ sufficiently attacks $(A,a)$, there exists a fuzzy argument $(C,c)\in E\cup \hat{E}$ s.t. $c*\rho_{_{CB}}=a$, i.e., $E\cup \hat{E}\subseteq F_{FAF}(E\cup \hat{E})$.
In case $(B,b)$ sufficiently attacks $E$, the conclusion follows from admissibility of E.
On the other hand, if $(B,b)$ sufficiently attacks $\hat{E}$, we have that $(B,b)\in (outparents_{FAF}(S)\cup S)$ since $\hat{E}\subseteq S$;
we distinguish three cases for $(B,b)$:
\begin{enumerate}
\setlength{\itemsep}{0pt}
\setlength{\parsep}{0pt}
\setlength{\parskip}{0pt}
  \item if $(B,b)\in outparents_{FAF}(S)$, then taking into account that $(B,b)$ sufficiently attacks $\hat{E}$ and $\hat{E}\subseteq D_{FAF}(S,E)$, it must be the case according to the definition of $D_{FAF}(S,E)$ that there exists a fuzzy argument $(C,c)\in E$ s.t. $c*\rho_{_{CB}}=a$.
  \item if $(B,b)\in S$, then according to the definition of $L_{FAF}(S,E)$ and $R_{FAF}(S,E)$ it must be the case that $\exists (C,c)\in E\cap outparents(S)$ s.t. $(B,b)$ is weakened to $(B,b')$ by $(C,c)$ and $(B,b')\in R_{FAF}(S,E)$;
  \item if $(B,b)\in R_{FAF}(S,E),$ then we have that $(B,b)$ sufficiently attacks $(A,a)$ holds also in $FAF\downarrow_{R_{FAF}(S,E)}.$
  Consequently, the hypothesis that $\hat{E}\in \mathcal{AE}(FAF\downarrow_{R_{FAF}(S,E)})$ entails that there exists a fuzzy argument $(C,c)\in \hat{E}$ s.t. $c*\rho_{_{CB}}=a$, and, of course, that the relation also holds in FAF.
\end{enumerate}
\end{proof}

\begin{prop}\label{Preferred Proposition}
Given a fuzzy argumentation framework $FAF=\langle\mathcal{A},\rho\rangle$ and a set of fuzzy arguments $E\subseteq \mathcal{A}$, $\forall C\subseteq \mathcal{A}$, $E\in \mathcal{PE}(FAF, C)$ if and only if $\forall S\in SCCS_{FAF}$
\begin{displaymath}
(E\cap S)\in \mathcal{PE}(FAF\downarrow_{R_{FAF}(S,E)},D_{FAF}(S,E)\cap C)
\end{displaymath}
\end{prop}
\begin{proof}
As far as the first direction of the proof is concerned, let us assume that $E\in \mathcal{PE}(FAF, C)$.
By definition, $E\in \mathcal{AE}(FAF, C)$, therefore, on the basis of Proposition \ref{admissible proposition},
we have that $\forall S\in SCCS_{FAF}$,
\begin{center}
  $(E\cap S)\in \mathcal{AE}(FAF\downarrow_{R_{FAF}(S,E)},D_{FAF}(S,E)\cap C)$
\end{center}
Let us now reason by contradiction, assuming that $\exists \hat{S}\in SCCS_{FAF}$ such that $(E\cap \hat{S})$ is not maximal among the sets included in $\mathcal{AE}(FAF\downarrow_{R_{FAF}(\hat{S},E)},D_{FAF}(\hat{S},E)\cap C)$.
According to Theorem \ref{the existense of preferred extensions}, there must be a set $\hat{E}$ such that
\begin{itemize}
  \item $(E\cap \hat{S})\subsetneq \hat{E} \subseteq (D_{FAF}(\hat{S},E)\cap C)$;
  \item $\hat{E}\in \mathcal{AE}(FAF\downarrow_{R_{FAF}(\hat{S},E)},D_{FAF}(\hat{S},E)\cap C)$
\end{itemize}
Taking into account that, according to the definition of $\mathcal{AE}(FAF,C)$, $E\in \mathcal{AE}(FAF,C)$.
Lemma \ref{Preferred Lemma} entails that the set $E'= E\cup \hat{E}$ is admissible in FAF.
Moreover since both E and $\hat{E}$ are contained in C we have that $E'\subseteq C$, therefore $E'\in \mathcal{AE}(FAF,C)$.
However, it is easy to see that $E$ is strictly contained in $E'$, contradicting the maximality of E among the sets of $\mathcal{AE}(FAF,C)$.
Hence,  $(E\cap S)\in \mathcal{PE}(FAF\downarrow_{R_{FAF}(S,E)},D_{FAF}(S,E)\cap C)$.

Let us turn now to the other direction of the proof, assuming that $\forall S\in SCCS_{FAF}$,
$(E\cap S)\in \mathcal{PE}(FAF\downarrow_{R_{FAF}(\hat{S},E)},D_{FAF}(\hat{S},E)\cap C)$.
On the basis of Proposition \ref{admissible proposition}, $E\in \mathcal{AE}(FAF,C)$:
in order to prove that $E$ is also a preferred extension, we reason again by contradiction,
supposing that $\exists E'\subseteq C$, $E\subsetneq E'$: $E'\in \mathcal{PE}(FAF,C)$
(notice that the existence of $E'$ is imposed by Theorem \ref{the existense of preferred extensions}).
Since $E\subsetneq E'$, there must be at least a strongly connected component $S\in SCCS_{FAF}$ such that $E\cap S\subsetneq(E'\cap S)$:
taking into account the acyclicity of the strongly connected components, there exists in particular $\hat{S}\in SCCS_{FAF}$ such that
\begin{equation}\label{4}
  \forall S\in SCCS_{FAF}: S\in sccanc_{FAF}(\hat{S}), (E'\cap S)=(E\cap S) \tag{4}
\end{equation}
\begin{equation}\label{5}
  (E\cap \hat{S})\subsetneq (E'\cap \hat{S}) \tag{5}
\end{equation}
Note that condition (\ref{4}) is trivially verified if $\hat{S}$ is initial.

Since $E'\in \mathcal{AE}(FAF,C)$, on the basis of Proposition \ref{admissible proposition} we have that
$(E'\cap \hat{S})\in \mathcal{AE}(FAF\downarrow_{R_{FAF}(\hat{S},E')},D_{FAF}(\hat{S},E')\cap C)$.
Taking into account Equation (\ref{4}), it is easy to see that $D_{FAF}(\hat{S},E')=D_{FAF}(\hat{S},E)$ and $R_{FAF}(\hat{S},E')=R_{FAF}(\hat{S},E)$,
therefore $(E'\cap \hat{S}\in \mathcal{AE}(FAF\downarrow_{R_{FAF}(\hat{S},E)},D_{FAF}(\hat{S},E)\cap C)$.
However, on the basis of Equation (\ref{5}) we have that $(E\cap \hat{S})\subsetneq (E'\cap \hat{S})$,
and this contradicts the hypothesis that $(E\cap S)\in \mathcal{PE}(FAF\downarrow_{R_{FAF}(S,E)},D_{FAF}(S,E)\cap C)$.
\end{proof}

\subsection{Grounded Semantics}

Finally, in this subsection, we prove that the grounded semantics also fit the SCC-recursive decomposition scheme, as shown by the following Proposition \ref{Grounded Proposition}.

\begin{prop}\label{Grounded Proposition}
Given a fuzzy argumentation framework $FAF=\langle\mathcal{A},\rho\rangle$ and a set of fuzzy arguments $E\subseteq \mathcal{A}$, $\forall C\subseteq \mathcal{A}$, $E= GE(FAF, C)$ if and only if $\forall S\in SCCS_{FAF}$
\begin{displaymath}
(E\cap S)= GE(FAF\downarrow_{R_{FAF}(S,E)},D_{FAF}(S,E)\cap C)
\end{displaymath}

\end{prop}
\begin{proof}
Let us consider the first part of the proof, by supposing that $E = GE(FAF,C)$.
On the basis of Proposition \ref{Grounded}, E is in particular a complete extension in C, i.e., $E\in \mathcal{CE}(FAF,C)$,
therefore Proposition \ref{Complete Proposition} entails that
\begin{center}
$\forall S\in SCCS_{FAF}$ $(E\cap S)\in \mathcal{CE}(FAF\downarrow_{R_{FAF}(S,E)},UAF(S,E)\cap C)$
\end{center}
Taking into account Proposition \ref{Grounded}, we have to prove that $\forall S\in SCCS_{FAF}(E\cap S)$ is
the least element (with respect to set inclusion) in $\mathcal{CE}(FAF\downarrow_{R_{FAF}(S,E)},D_{FAF}(S,E)\cap C)$.
We reason by contradiction, supposing that there is at least one strongly connected component where the thesis is not verified.
In particular, since the strongly connected components of FAF make up an acyclic graph, we can choose $\hat{S}\in SCCS_{FAF}$ such that
\begin{equation}\label{6}
\forall S\in sccanc_{FAF}(\hat{S}), (E\cap S)=GE(FAF\downarrow _{R_{FAF}(S,E)},D_{FAF}(S,E)\cap C) \tag{6}
\end{equation}
and
\begin{equation}\label{7}
\exists \hat{E}\subsetneq (E\cap \hat{S}), \hat{E}=GE(FAF\downarrow _{R_{FAF}(\hat{S},E)},D_{FAF}(\hat{S},E)\cap C) \tag{7}
\end{equation}
Note that condition (\ref{6}) is trivially verified if $\hat{S}$ is initial.

Moreover, the second condition follows from the fact that, on the basis of Lemma \ref{Grounded Lemma},
$GE(FAF\downarrow _{R_{FAF}(S,E)},D_{FAF}(S,E)\cap C)$ must exist, and according to Proposition \ref{Grounded} it is included
in all the elements of $\mathcal{CE}(FAF\downarrow _{R_{FAF}(\hat{S},E)},D_{FAF}(\hat{S},E)\cap C)$.

Now, taking again into account that the strongly connected components of FAF make up an acyclic graph,
it is easy to see that it is possible to construct a set $E'$ such that:
\begin{itemize}
\setlength{\itemsep}{0pt}
\setlength{\parsep}{0pt}
\setlength{\parskip}{0pt}
  \item $\forall S\in sccanc_{FAF}(\hat{S}), (E'\cap S) = (E\cap S)$;
  \item $(E'\cap \hat{S}) = \hat{E}$;
  \item $\forall S\in SCCS_{FAF},(E'\cap S) = GE(FAF\downarrow_{R_{FAF}(S,E')},D_{FAF}(S,E')\cap C)$.
\end{itemize}
To this purpose, it is obviously possible to construct a set $E''$ contained in the strongly connected components of $(\hat{S}\cup sccanc_{FAF}(\hat{S}))$ which satisfies the first two conditions.
Thus, it turns out that $\forall S\in(\hat{S}\cup sccanc_{FAF}(\hat{S}))$ $D_{FAF}(S,E'') = D_{FAF}(S,E)$ and $R_{FAF}(S,E'')=R_{FAF}(S,E)$.
Therefore, taking into account (\ref{6}) and (\ref{7}), $E''$ satisfies the third condition too for any such S, i.e.,
\begin{center}
$\forall S\in (\hat{S}\cup sccanc_{FAF}(\hat{S}))$ $(E''\cap S)=GE(FAF\downarrow_{R_{FAF}(S,E'')},D_{FAF}(S,E'')\cap C)$
\end{center}
Now, $E'$ can be obtained constructively from $E''$ by proceeding along the other strongly connected components:
in fact $\forall S\in SCCS_{FAF}$ $GE(FAF\downarrow_{R_{FAF}(S,E')},D_{FAF}(S,E')\cap C)$ always exists by Lemma \ref{Grounded Lemma}.
On the basis of Proposition \ref{Grounded}, we have that
$\forall S\in SCCS_{FAF}$ $(E'\cap S)\in\mathcal{CE}(FAF\downarrow_{R_{FAF}(S,E')},D_{FAF}(S,E')\cap C)$.
As a consequence, by Proposition \ref{Complete Proposition} it turns out that $E'\in \mathcal{CE}(FAF,C)$, while since
$(E'\cap \hat{S})=\hat{E}\subsetneq(E\cap \hat{S})$, it is not true that $E\subseteq E'$.
However, this contradicts the hypothesis that $E = GE(FAF,C)$, which according to Proposition \ref{Grounded} is the least element of $\mathcal{CE}(FAF,C)$, i.e., the least complete extension in C.

Let us turn now to the other direction of the proof, by supposing that $\forall S\in SCCS_{FAF}$,
$(E\cap S)\in GE(FAF\downarrow_{R_{FAF}(S,E)},D_{FAF}(S,E)\cap C)$.
On the basis of Proposition \ref{Grounded}, we have that $\forall S\in SCCS_{FAF}$,
$(E\cap S)\in \mathcal{CE}(FAF\downarrow_{R_{FAF}(S,E)},D_{FAF}(S,E)\cap C)$,
therefore Proposition \ref{Complete Proposition} entails that $E\in \mathcal{CE}(FAF,C)$.
As a consequence, taking into account Proposition \ref{Grounded} we have only to prove that E is the least element of $\mathcal{CE}(FAF,C)$.
We reason by contradiction, assuming that the grounded extension $E' = GE(FAF,C)$, which must exist by Lemma \ref{Grounded Lemma}
and is a subset of E by Proposition \ref{Grounded}, is strictly included in E.
Thus, there must be at least a strongly connected component S such that $(E'\cap S)\subsetneq (E\cap S)$:
since the strongly connected components form an acyclic graph, there is in particular a strongly connected component $\hat{S}$ such that:
\begin{equation}\label{8}
\forall S\in sccanc_{FAF}(\hat{S}), (E'\cap S)=(E\cap S) \tag{8}
\end{equation}
\begin{equation}\label{9}
(E'\cap\hat{S})\subsetneq (E\cap \hat{S}) \tag{9}
\end{equation}
Moreover, since $E' = GE(FAF,C)\in \mathcal{CE}(FAF,C)$, Proposition \ref{Complete Proposition} applied to $\hat{S}$ entails that
$(E'\cap \hat{S})\in \mathcal{CE}(FAF\downarrow_{R_{FAF}(\hat{S},E')},D_{FAF}(\hat{S},E')\cap C)$.
Taking into account (\ref{8}), it is easy to see that $D_{FAF}(\hat{S},E') = D_{FAF}(\hat{S},E)$ and $R_{FAF}(\hat{S},E') = R_{FAF}(\hat{S},E)$,
therefore $(E'\cap \hat{S})\in \mathcal{CE}(FAF\downarrow_{R_{FAF}(\hat{S},E)},D_{FAF}(\hat{S},E)\cap C)$.
However, according to (\ref{9}) we have that $(E'\cap \hat{S})$ is strictly included in $(E\cap \hat{S})$, contradicting the hypothesis (referred to $\hat{S}$) that $(E\cap \hat{S})\in GE(FAF\downarrow_{R_{FAF}(\hat{S},E)},D_{FAF}(\hat{S},E)\cap C)$ and therefore,
on the basis of Proposition \ref{Grounded}, that $(E\cap \hat{S}$) is the least element of $\mathcal{CE}(FAF\downarrow_{R_{FAF}(\hat{S},E)},D_{FAF}(\hat{S},E)\cap C)$.
\end{proof}

\subsection{The SCC-recursiveness Principle of Basic Semantics}

As discussed in the previous section, each specific SCC-recursive semantics is identified by its own base function.
On the basis of the results obtained in the previous sections, we prove that the admissible, complete, preferred, and grounded semantics fit the general SCC-recursive decomposition scheme.
This is achieved by the following theorem.

\begin{thm}
The admissible, complete, preferred and grounded semantics are SCC-recursive,
characterized by the following base functions (defined for generic fuzzy argumentation frameworks such that $|SCCS_{FAF}| = 1$):
\begin{itemize}
\setlength{\itemsep}{0pt}
\setlength{\parsep}{0pt}
\setlength{\parskip}{0pt}
  \item $\mathcal{BF}_{\mathcal{AE}} (FAF,C) \equiv \mathcal{AE}(FAF,C)$;
  \item $\mathcal{BF}_{\mathcal{CO}} (FAF,C) \equiv \mathcal{CO}(FAF,C)$;
  \item $\mathcal{BF}_{\mathcal{PE}} (FAF,C) \equiv \mathcal{PE}(FAF,C)$;
  \item $\mathcal{BF}_{\mathcal{GR}} (FAF,C) \equiv \{GR(FAF,C)\}$.
\end{itemize}

\end{thm}

\begin{proof}
Let us prove the claim with reference to complete semantics.
First, $E\in \mathcal{CO}(FAF)$ if and only if $E\in \mathcal{CO}(FAF,\mathcal{A})$,
since as noticed in Section 4.1, original fuzzy argumentation frameworks are recovered from the extended ones in case C coincides with the set of all
arguments.
Now, it is easy to see that $\mathcal{CO}(FAF,C)$ for generic FAF and C adheres to Definition \ref{The base definition of SCC-recursiveness in FAF}: if $|SCCS_{FAF}| = 1$, then $\mathcal{CO}(FAF,C)$ coincides by definition with the base function $\mathcal{BF}_{\mathcal{CO}} (FAF,C)$,
otherwise the decomposition schema along the strongly connected components follows from Proposition \ref{Complete Proposition}.
As far as admissible, preferred and grounded semantics are concerned, proofs are similar
and are based on Propositions \ref{admissible proposition}, \ref{Preferred Proposition} and \ref{Grounded Proposition}, respectively.
\end{proof}

From the above theorem and propositions, we show the soundness and completeness of the SCC-recursiveness principle in admissible, complete, preferred, and grounded semantics.
It is showed that the SCC-recursiveness principle provides an incremental algorithm for calculating the argumentation semantics of FAFs.
By exploiting the SCC-recursive decomposition scheme, each FAF is partitioned to many reduced sub-frameworks along the strongly connected components.
In the following section, we will use some examples to illustrate the efficiency of the SCC-recursiveness principle in computing the argumentation semantics of FAFs.

\section{The illustrating example of efficient algorithm for calculating the SCC-recursiveness semantics}

It has been proved that the admissible, complete, preferred, grounded semantics fit the SCC-recursiveness principle in FAFs.
Thus, we can decompose the FAF to many sub-frameworks along the strongly connected components.
Then we can compute the semantics of FAF by combining the semantics of these sub-frameworks.
As a result, we prove that the SCC-recursiveness principle provides efficient and incremental algorithms on local computation at the level of strongly connected components.
In this section, we show some examples to illustrate that the SCC-recursiveness principle can help us to efficiently compute the argumentation semantics extensions.
From the previous sections, the SCC-recursiveness principle decomposes the FAF along the strongly connected components.
Thus, by utilizing the SCC-recursiveness principle, we obtain many sub-frameworks.
We then calculate the argumentation semantics of these sub-frameworks and the combined semantics of these sub-frameworks coincide with the semantics of the FAF.
Hence, we can efficiently compute the argumentation semantics of FAF.

Before the example, it is remarked that given an FAF, if an attack relation has no influence (i.e., the attack relation is always tolerable in this FAF), then we neglect this attack relation.

\begin{exmp}
\begin{figure}[htb]
\centering
\includegraphics[height=0.6\textwidth]{{examplea}.png}
\caption{The illustrating example 1.}
\label{Example1}
\end{figure}
Given a fuzzy argumentation framework $FAF=\langle \{(A,0.8),(B,0.7),(C,0.6),$
$(D,0.8),(E,0.6),(F,0.7)\},\{((A,B),0.8),((B,C),0.9),((C,B),0.9),((C,D),0.8),((D,E),$
$0.7),((E,F),0.8),((F,D),0.9)\}\rangle.$

First of all, according to the theory of strongly connected component, all the fuzzy arguments are first partitioned into three strongly connected components:
$S_1=\{(A,0.8)\},$ $S_2=\{(B,0.7),(C,0.6)\},$
$S_3=\{(D,0.8),(E,0.6),(F,0.7)\}$.

Then we computing the complete extensions of the FAF.
As for the initial strongly connected component $S_1=\{(A,0.8)\}$,  $D_{FAF}(S_1,E')=R_{FAF}(S_1,E')=S_1$.
Thus, the first sub-framework $FAF_1=\langle \{(A,0.8))\},\{\emptyset\}\rangle$.
Since $FAF_1$ consists of a unique strongly connected component, the base function $\mathcal{BF}_{\mathcal{PR}}(FAF_1,S_1)$ is invoked.
It is evident that the complete extension of $FAF_1$ is $E_1=\{(A,0.8)\}$.
Then we consider the strongly connected component $S_2=\{(B,0.7),(C,0.6)\}$.
From that $S_1$ attacks $S_2$ and $E\cap S_1=\{(A,0.8)\}$, we have that $L_{FAF}(S_2,E)=\{(B,0.8)\}$, $R_{FAF}(S_2,E)=\{(B,0.2),(C,0.6)\}$ and $D_{FAF}(S_2,E)=\{(B,0.2),(C,0.6)\}$.
Since the attack relation between $(B,0.2)$ $(C,0.6)$ is always tolerable, the attack relation among them can be reduced from the system.
The strongly connected components of the reduced fuzzy argumentation frameworks $FAF'=\langle\{(B,0.2),(C,0.6)\},\emptyset\rangle$ is not unique.
Thus, as for the strongly connected component $S_2$, we recursively obtain two strongly connected components: $S_4=\{(B,0.2)\}$, $S_5=\{(C,0.6)\}$.
It can be obtained that the second sub-framework $FAF_2=\langle\{(B,0.2)\},\emptyset\rangle$ and the third sub-framework $FAF_3=\langle\{(C,0.6)\},\emptyset\rangle$.
And $\{(B,0.2)\}\in \mathcal{CE}(FAF_2), \{(C,0.6)\}\in \mathcal{CE}(FAF_3)$ is obvious.
As far as the strongly connected component $S_3$ is concerned, since $(C,0.6)$ attacks $S_3$, we have that $L_{FAF}(S_3,E)=\{(D,0.6)\}$, $R_{FAF}(S_3,E)=\{(D,0.4),(E,0.6),(F,0.7)\}$, $D_{FAF}(S_3,E)=\{(D,0.4),(E,0.6),(F,0.7)\}$.
Since the attack relation between $(D,0.4),(E,0.6)$ is always tolerable, the attack relation among them can be neglected.
Thus the framework among $S_3$ is reduced as $FAF'=\langle \{(D,0.4),(E,0.6),(F,0.7)\},\{((E,F),0.8),((F,D),0.9)\}\rangle$.
Again utilizing the principle, all the fuzzy arguments of $FAF'$ is partitioned into three strongly connected components:
$S_4=\{(E,0.6)\}$,$S_5=\{(F,0.7)\}$,$S_6=\{(D,0.4)\}$.
We obtain that the fourth sub-framework $FAF_4=\langle\{(E,0.6)\},\emptyset\rangle$ and
$E\cap S_4=\{(E,0.6)\}$.
We thus have that $D_{FAF}(S_5,E)=P_{FAF}(S_5,E)=\{(F,0.4)\}$.
The attack relation from F to D is evidently tolerable that should be reduced.
Therefore, it can be concluded that  the fifth sub-framework $FAF_5=\langle\{(F,0.4)\},\emptyset\rangle$ and  the sixth sub-framework $FAF_6=\langle\{(D,0.4)\},\emptyset\rangle$.
And $E\cap S_5=\{(F,0.4)\}$ and $E\cap S_6=\{(D.0.4)\}$.
As a result, the combination extension $E=\{(A,0.8),(B,0.2),(C,0.6),(D,0.4),(E,0.6),(F,0.4)\}$ is a complete extension of the FAF.

\end{exmp}

From the above example, when calculating the complete extension of the given FAF by utilizing the SCC-recursiveness principle, it is reduced to a graph that only has nodes but not arrows.
It can be concluded that the SCC-recursiveness can efficiently reduce the difficult FAF and computing the semantics.
In the next example, we provide a fuzzy argumentation framework with high complexity.
We show the efficiency of the SCC-recursiveness principle.

\begin{exmp}
\begin{figure}
\centering
\includegraphics[height=1\textwidth]{{examplec}.png}
\caption{The illustrating example 2.}
\label{Example2}
\end{figure}
Given a fuzzy argumentation framework $FAF=\langle \{(A,0.8),(B,0.8),(C,0.9),$
$(D,0.8),(E,0.8),(F,0.9),(G,0.8),(H,0.5),(I,0.7)\},\{((A,B),0.8),((B,A),0.9),((B,C),$

\noindent $0.9),((C,D),0.8),((D,E),0.9),((E,F),0.8),((F,C),0.8),((E,C),0.9),((E,G),0.8),((G,$

\noindent $H),0.9),((H,I),0.7),((G,I),0.8),((I,G),0.8)\}\rangle.$

First of all, according to the theory of strongly connected component, the fuzzy arguments first partitioned into three strongly connected components: $S_1=\{(A,0.8),(B,0.8)\},$
$S_2=\{(C,0.9),(D,0.8),$
$(E,0.8),(F,0.9)\},$
$S_3=\{(G,0.8),(H,0.5),(I,0.7)\}$.

Then we computing the preferred semantics of the FAF.
As for the initial strongly connected component $S_1=\{(A,0.8),(B,0.8)\}$, $D_{FAF}(S_1,E')=R_{FAF}(S_1,E')=S_1$.
Thus, the first sub-framework $FAF_1=FAF\downarrow_{R_{FAF}}=\langle \{(A,0.8),(B,0.8)\},\{((A,B),0.8),((B,A),$
$0.9)\}\rangle$.
Since $FAF_1$ consists of a unique strongly connected component, the base function $\mathcal{BF}_{\mathcal{PR}}(FAF_1,S_1)$ is invoked.
The element of the subset of the preferred extension is infinite, for the sake of the example, we just choose two limit conditions: $PE_1=\{(A,0.2),(B,0.8)\}$, $PE_2=\{(A,0.8),(B,0.2)\}$.
Therefore, we can obtain two decompositions of the FAFs according to these two distinct preferred extensions of $FAF_1$.
And the final preferred extensions $E'$ and $E''$ are directly obtained from these two decompositions respectively.
We first consider the first decomposition (see decomposition 1 in figure 2) of the FAF, namely when $E'\cap S_1=E_1=\{(A,0.2),(B,0.8)\}$.
As far as the subsequent strongly connected component $S_2$ is concerned, from that $E_1=\{(A,0.2),(B,0.8)\}$,
we have that $D_{FAF}(S_2,E')=R_{FAF}(S_2,E')=\{(C,0.2),(D,0.8),(E,0.8),(F,0.9)\}$.
It is evident that the attack relation from E to C is always tolerable.
Thus the attack relation $((E,C),0.9)$ is reduced from our system.
Therefore, the second sub-framework $FAF_2=\langle\{(C,0.2),(D,0.8),(E,0.8),(F,0.9)\},$
$\{((C,D),0.8),((D,E),0.9),((E,F),0.8),$
$((F,C),0.8)\}\rangle$.
Since $FAF_2$ consists of an unique strongly connected component, the base function
$\mathcal{BF}_{\mathcal{PR}}(FAF_2,D_{FAF}(S_2,E'))$ is invoked.
And $E_2=\{(C,0.2),(D,0.8),(E,0.2),$
$(F,0.8)\}$ is an unique preferred extension of $FAF_2$.
Finally, we consider strongly connected component $S_3$.
Due to $E'\cap E_2=\{(C,0.2),(D,0.8),$
$(E,0.2),(F,0.8)\}$, we have that $D_{FAF}(S_3,E')=R_{FAF}(S_3,E')=\{(G,0.8),(H,0.5),(I,0.7)\}$.
Therefore, the third sub-framework $FAF_3=\langle\{(G,0.8),(H,0.5),(I,0.7)\},\{((G,H),0.9),$
$((H,I),0.7),((G,I),0.8),$
$((I,G),0.8)\}\rangle$.
Since $FAF_3$ consists of a unique strongly connected component, the base function $\mathcal{BF}_{\mathcal{PR}}(FAF_3,D_{FAF}(S_3,E'))$ is invoked.
And $E_3=\{(G,0.8),(H,0.2),(I,0.2)\}$ is a preferred extension of $FAF_3$.
As a result, the combination extension $E'=\{(A,0.2),$
$(B,0.8),(C,0.2),(D,0.8),(E,0.2),(F,0.8),(G,0.8),(H,0.2),(I,0.2)\}$ is a preferred extension of the FAF.

Next, we consider the second decomposition (see decomposition 2 in figure 2) of the FAF, namely when $E''\cap S_1=E_1=\{(A,0.8),(B,0.2)\}$.
As far as the subsequent strongly connected component $S_2$ is concerned, from that $E_1=\{(A,0.8),(B,0.2)\}$,
we have that $D_{FAF}(S_2,E'')=R_{FAF}(S_2,E'')=\{(C,0.8),(D,0.8),(E,0.8),(F,0.9)\}$.
Thus, the second sub-framework $FAF_2=\langle\{(C,0.8),(D,0.8),(E,0.8),(F,0.9)\},\{((C,D),0.8),((D,E),0.9),$
$((E,F),0.8),((F,C),0.8),((E,C),0.9)\}\rangle$.
Since $FAF_2$ consists of a unique strongly connected component, the base function $\mathcal{BF}_{\mathcal{PR}}(FAF_2,D_{FAF}(S_2,E''))$ is invoked.
And $E_2=\{(C,0.5),(D,0.5),(E,0.5),(F,0.5)\}$ is an unique preferred extension of $FAF_2$.
Finally, we consider strongly connected component $S_3$.
Due to $E'\cap E_2=\{(C,0.5),(D,0.5),(E,0.5),$
$(F,0.5)\}$, we have that $D_{FAF}(S_3,E'')=R_{FAF}(S_3,E'')=\{(G,0.5),(H,0.5),(I,0.7)\}$.
It is evident that the attack relation from G to H is always tolerable.
Thus the attack relation $((E,C),0.9)$ is reduced from our system.
The framework among $S_3$ is reduced as $FAF'=\langle\{(H,0.5),(I,0.7),(G,0.5)\},\{((H,I),0.7),((G,I),0.8),((I,G),0.8)\}\rangle$.
The strongly connected components of $FAF'$ is not unique.
Thus we again apply the SCC-recursiveness principle.
Then we obtain two strongly connected components: $S_4=\{(H,0.5)\}$, $S_5=\{(G,0.5),(I,0.7)\}$.
Therefore, $S_4$ is an initial strongly connected component in $FAF'$.
We then obtain the third sub-framework $FAF_3=\langle\{(H,0.5)\},\emptyset\rangle$.
Since $FAF_3$ consists of a unique strongly connected component, the base function $\mathcal{BF}_{\mathcal{PR}}(FAF_3,D_{FAF}(S_4,E''))$ is invoked.
And $E_3=\{(H,0.5)\}$ is a preferred extension of $FAF_3$.
From that $E''\cap E_2=\{(H,0.5)\}$, we have $D_{FAF}(S_5,E'')=R_{FAF}(S_5,E'')=\{(G,0.5),(I,0.5)\}$.
And the attack relation among G and I is tolerable.
We further obtain two strongly connected components: $S_6=\{(G,0.5)\}$, $S_7=\{(I,0.5)\}$.
Thus we obtain the fourth sub-framework $FAF_4=\langle\{(H,0.5)\},\emptyset\rangle$ and the fifth sub-framework $FAF_5=\langle\{(I,0.5)\},\emptyset\rangle$.
$E''\cap S_6=\{(G,0.5)\}$ and $E''\cap S_7=\{I,0.5\}$ is obvious.
As a result, the combination extension $E''=\{(A,0.8),(B,0.2),(C,0.5),(D,0.5),(E,0.5),(F,0.5),(G,0.5),(H,0.5),(I,0.5)\}$ is a preferred extension of the FAF.
\end{exmp}

\section{Discussion}

In \cite{baroni2005scc}, Baroni et.al proposed the SCC-recursiveness principle which relies on the graph-theoretical notion of strongly connected components.
It is an effective tool for supporting the development of new semantics and it provides a general scheme for computing argumentation semantics.
In this paper, we formalize the SCC-recursiveness principle in FAFs.
And we provide the efficient and incremental algorithms to compute the argumentation semantics of FAFs based on this principle.

The major difference of the SCC-recursiveness principle between the AFs and FAFs is the basic principles: reinstatement principle and directionality principle.
In Dung's AFs, the reinstatement principle shows that arguments defeated by an extension E play no role in the selection of arguments to be included in E.
The directionality principle shows that the justification status of an argument only depended on the justifications of its attackers (which in turn are affected by their attackers and so on).
Since the FAFs combine the fuzzy degree with arguments and attack relation, it is infeasible to directly formalize the SCC-recursiveness principle of FAFs.
Therefore, we modify the reinstatement principle and directionality principle to fit the FAFs.
As far as the reinstatement principle is concerned, we have proposed that the limited part has no influence in the FAFs and the maximal acceptable belief degree of a generic argument cannot greater than the negation of the limited belief degree.
And the directionality principle shows that the acceptable belief degree of an argument only depends on the belief degrees of its attackers (which in turn are affected by their attackers and so on).

Additionally, due to the modification of the basic theory, the justification status of the arguments are reestablished in FAFs.
In Dung's AFs, all the arguments within the specific strongly connected component S are completely partitioned into three parts w.r.t. E: defeated part, provisionally defeated part, and undefeated part.
The defeated part consists of the nodes of S attacked by E from outside S, provisionally defeated part consists of the nodes of S that are not attacked by E from outside S and are defended by E (i.e., their defeaters from outside S are all attacked by E), and undefeated part consists of the nodes of S that are not attacked by E from outside S and are not defended by E.
In FAFs, all the arguments within the specific strongly connected component S are assigned three belief degrees w.r.t. E: limited belief degree, residual belief degree, and defended belief degree.
The arguments with limited degree represent the limited part which should be reduced,
the arguments with residual degree represent the residual part which causes influence in the reduced system,
and the arguments with defended degree represent the defended part (which belong to the Residual Part) which are partial defended w.r.t. E out S, namely the outsider sufficient attackers are weakened by E.

As a result, there is much difference between the initial SCC-recursiveness principle and the modified SCC-recursiveness principle in this paper.

\section{Conclusion}

As shown in this paper, the SCC-recursiveness principle is a property of argumentation semantics which relies on the graph-theoretical notion of strongly connected components.
It provides a general recursive schema for argumentation semantics, which is an efficient and incremental algorithm for computing the argumentation semantics in FAFs.

This paper is an exploration of the SCC-recursiveness principle in FAFs, which is a special kind of numbered AFs.
In order to establish the basic theory, we modify the reinstatement principle and the directionality principle to fit the FAFs.
And the SCC-recursiveness principle in FAFs is formalized by the modified principles.
We then show that admissible, complete, grounded, and preferred semantics fit this principle.
And the principle provides a general scheme for these SCC-recursive semantics of FAFs.
We finally provide examples to illustrate the efficiency of the SCC-recursiveness scheme in FAFs.

The main contributions are in the following aspects.:
\begin{enumerate}
\setlength{\itemsep}{0pt}
\setlength{\parsep}{0pt}
\setlength{\parskip}{0pt}
\item We modify the reinstatement principle and directionality principle to fit the FAFs.
For the reinstatement principle, we propose that the limited part has no influence in the FAFs and the maximal acceptable belief degree of a generic argument cannot greater than the negation of the limited belief degree.
The directionality principle shows that the belief degree of an argument only depended on the belief degree of its attackers (which in turn are affected by their attackers and so on).
\item We extend the SCC-recursiveness principle to FAFs.
For each strongly connected component S, we identify three parts: limited part, residual part, and defended part.
Based on the reinstatement principle, the limited part is reduced from our system.
According to the directionality principle, the belief degree of each argument within a strongly connected component depends on the belief degree of ancestor strongly connected component.
Based on these two modified principles, we provide the SCC-recursiveness principle in FAFs.
\item We show the efficiency and incremental algorithms for calculating the argumentation semantics of FAFs by utilizing the SCC-recursiveness principle.
    According to the SCC-recursiveness principle, each FAF is partitioned into many reduced sub-frameworks along the strongly connected component.
    And the combination semantics of these sub-frameworks coincide with the semantics of the original FAF.
\end{enumerate}

In the future, similar to \cite{baroni2005scc}, we want to search for some novel semantics that depend on the SCC-recursiveness principle.
Additionally, we will continue to explore the residual principles of fuzzy argumentation frameworks.
These principles can provide efficient algorithms for computing argumentation semantics and explore the new semantics.

\bibliographystyle{plain}
\bibliography{SCCReferrence}

\end{document}

config: arxiv


text:
\section{Learning T-MFE}
\label{sec:learning-TMFE-offline}
We address the problem of learning T-MFE when the model is unknown. In this section, we assume the availability of a simulator, which, given the current state $s$, current action $a$ and current mean field $z$, can generate the next state $s' \sim P(\cdot | s, a, z)$. We discuss how to learn directly from real-world samples without a simulator in the next section.  We also assume that the reward function is known, as is common in the literature.  We now introduce two reinforcement learning algorithms---a model-free algorithm and a model-based algorithm---for learning  T-MFE.

\subsection{Model-Free TMFQ-Learning Algorithm for learning T-MFE}\label{sec:QL-conv-TMFE}

We first describe the TMFQ-learning algorithm, which builds on the T-BR algorithm. Recall that the T-BR algorithm uses knowledge of the model in two locations.  The first is that at each step $k,$ for a given mean field $z_{k}$, the  optimal  TQ-value function $Q^{*}_{z_{k}}$ is computed using TQ-value iteration.

In the learning approach, we use the generalized Q-learning framework \citep{szepesvari1996generalized} as the basis for the model-free TQ-learning algorithm as follows:
\begin{align}
\label{eq:TQ-update}
\begin{split}
    & Q_{t+1, z_k}(s_{t}, a_{t}) = (1 - \alpha_{t})  Q_{t, z_k}(s_{t}, a_{t}) \\
    & \quad \quad \quad + \alpha_{t} (r(s_{t}, a_{t}, z_{k}) + \gamma G(Q_{t, z_k})(s_{t+1}))
\end{split}
\end{align}
where $\alpha_{t}$ is the appropriate learning rate. Here, the state sequence $\{s_{t}\}$ is generated using the simulator by fixing the mean field $z_{k},$ i.e.,
$s_{t+1} \sim P(\cdot | s_{t}, a_{t}, z_{k}), \forall t$. Using the properties of the generalized Q-learning formulation \citep{szepesvari1996generalized}, it can be shown that $Q_{t, z_k} \rightarrow Q^{*}_{z_{k}}$ as $t \rightarrow \infty$.

The second location where the model is needed in T-BR is for the one-step McKean-Vlasov update.  In the learning approach, given the  mean field $z_{k}$ and the strategy $\mu_{k}$, the next mean field $z_{k+1}$ can be estimated to a desired accuracy using the simulator.  The precise numerical approach is presented as the {Next-MF} scheme described in  Algorithm \ref{algo:next-MF} {(supplementary material).}  We can now combine these steps to obtain the TMFQ-learning algorithm presented in Algorithm~\ref{algo:TQL}.
\begin{algorithm}
\label{algo:TQL}
	\caption{TMFQ-Learning Algorithm for T-MFE}
	\begin{algorithmic}[1]
		\STATE Initialization:  Initial mean field ${z}_0$
		\FOR {$k=0, 1, 2, \ldots $}
		    \STATE Initialize time step $t \leftarrow 0$. Initialize $s_{0}, Q_{0,z_k}$
		    \REPEAT
		        \STATE Take action $a_{t} \sim \pi^{\epsilon}_{Q_{t,z_k}}(s_{t})$, observe  reward and  the next state $s_{t+1} \sim P(\cdot | s_{t}, a_{t}, z_{k})$
		        \STATE Update $Q_{t,z_k}$ according to TQ-learning \eqref{eq:TQ-update}
		        \STATE $t \leftarrow t+1$
		    \UNTIL{$\norm{Q_{t,z_k}-Q_{t-1,z_k}}_{\infty} < \epsilon_{1}$}
		    \STATE Let $Q_{z_{k}} = Q_{t,z_k}$ and the strategy $\mu_{k} = \pi^{\epsilon}_{Q_{z_k}}$
		    \STATE $z_{k+1} =${Next-MF}($z_k,\mu_{k}$)
		\ENDFOR
	\end{algorithmic}
\end{algorithm}

We first present an asymptotic convergence result of TMFQ-learning based on a perfect accuracy assumption on the TQ-learning and Next-MF steps, i.e., they are run to convergence. A complex, but more accurate analysis using two-timescale stochastic approximation is also possible.  Instead, we will remove this assumption, and provide a PAC-type result further below.
\begin{theorem}
\label{thm:T-MFE-convergence}
Let $\Gamma$ be a stationary mean field game with strategic complementarities. Let $\{z_{k}\}$ and $\{\mu_{k}\}$ be the sequences of the mean fields and policies generated by Algorithm \ref{algo:TQL}. Then ${\mu}_{k} \rightarrow {\mu}^*$  and $z_{k} \rightarrow z^{*}$  as $k \rightarrow \infty$ where $(\mu^*, z^{*})$ is a T-MFE of ~$\Gamma$.
\end{theorem}

In a practical implementation, we may only run the TQ-learning step and the Next-MF step for a finite number of iterations. Hence, we develop a sample complexity bound under which TQ-learning and Next-MF provide an appropriate accuracy. We desire to compare TMFQ-learning with T-BR after $k_{0}$ iterations, where $k_0$ is the number of iterations of T-BR that yields a mean field that is $\bar{\epsilon}$-close to the T-MFE $z^{*}$. We make some necessary assumptions that are required for such a characterization.

\begin{assumption}
\label{assump:Lips-R-P}
(i) There exists  $C_{1} > 0$ such that  $\norm{ r(\cdot, \cdot, z) - r(\cdot, \cdot, \tilde{z}) }_{1} \le C_{1}\norm{z - \tilde{z}}_{1}$, for all $z, \tilde{z} \in \mathcal{P}(\mathcal{S})$.\\
(ii) There exists a $C_{2} > 0$ such that  $\norm{ P(\cdot | \cdot, \cdot, z) - P(\cdot | \cdot, \cdot, \tilde{z}) }_{1} \le C_{2}\norm{z - \tilde{z}}_{1}$, for all $z, \tilde{z} \in \mathcal{P}(\mathcal{S})$. \\
(iii) Let $P_{\mu,z}(s'|s) = \sum_{a} \mu(s, a) P(s'|s,a,z)$. Let $\mu_{1}, \mu_{2}$ be the trembling-hand policies corresponding to $Q_{1}, Q_{2}$, i.e., $\mu_{1} =\pi^{\epsilon}_{Q_{1}}, \mu_{2} = \pi^{\epsilon}_{Q_{2}}$. Then there exists a $C_{3} > 0$ such that $\norm{P_{z,\mu_1}-P_{z,\mu_2}}_{1} \leq C_3 \norm{Q_1-Q_2}_{\infty}$ for all $z \in \mathcal{P}(\mathcal{S})$ and for any given $Q_{1}, Q_{2}$.
\end{assumption}
Assumption \ref{assump:Lips-R-P}.(i) and \ref{assump:Lips-R-P}.(ii) indicate that the reward function and transition kernel are Lipschitz with respect to the mean field, while Assumption \ref{assump:Lips-R-P}.(iii) indicates that the distance between the Markov chains induced by two policies on the same transition kernel are upper bounded by a constant times the distance between their respective Q-functions.  We then have the following.

\begin{theorem}
\label{thm:TQL-SC}
Let Assumption \ref{assump:Lips-R-P} hold. For any $0 \leq \bar{\epsilon}, \bar{\delta} < 1,$ let $k_{0} = k_{0}(\bar{\epsilon})$. In Algorithm \ref{algo:TQL}, for each $k \leq k_{0}$, assume that TQ-learning (according to \eqref{eq:TQ-update}) update is performed $T_{0}$ number of times where $T_{0}$ is given as
\begin{align}
\label{eq:asynch-Q-sample-1}
    T_{0} & = O \Bigg( \Bigg(\frac{B^{2} L^{1+3w} V^{2}_{\max}}{\beta^{2} \bar{\epsilon}^{2}} \ln \big( \frac{2 B k_{0}|\mathcal{S}||\mathcal{A}|V_{\max}}{\bar{\delta} \beta \bar{\epsilon}} \big)   \Bigg)^{\frac{1}{w}} \nonumber \\ & + \Bigg( \frac{L}{\beta} \ln(\frac{B V_{\max}}{\bar{\epsilon}}) \Bigg)^{\frac{1}{1-w}} \Bigg),
\end{align}
where $B = (1 + C_{2} + C_{3} D)^{k_{0}+1} (C_{3}+1)$,  $D = (C_{1} + \gamma C_{2})/(1-\gamma)$, $V_{\max} = 1/(1-\gamma), \beta = (1-\gamma)/2$,  $L$ is an upper bound on the covering time \footnote{Covering time of a state-action pair sequence is the number of steps needed to visit all state-action pairs starting from any arbitrary state-action pair \cite{even2003learning}.}, and $w \in (1/2, 1)$. Then,
\begin{align*}
    \mathbb{P}(\|z_{k_{0}} - z^{*} \| \leq 2 \bar{\epsilon}) \geq (1 - \bar{\delta}).
\end{align*}
\end{theorem}

We may also eliminate the dependence of the constant term $B$ on $k_0$ under a contraction assumption on the McKean-Vlasov dynamics $\Phi$ (for instance, following conditions similar to \cite{borkar2013asymptotics}).
\begin{assumption}
\label{assump:MV-strong}
Let $Q_{1}, Q_{2}$ be two arbitrary Q-value functions and let $\mu_{1} = \pi^{\epsilon}_{Q_{1}}, \mu_{2} = \pi^{\epsilon}_{Q_{2}}$. Let $z_{1}, z_{2}$ be two arbitrary mean fields. Then there exists positive constants $C_{4}$ and $C_{5}$ such that  $ \| \Phi(z_{1}, \mu_{1}) -  \Phi(z_{2}, \mu_{2}) \|_{1} \leq C_{4} \|z_{1} - z_{2} \|_{1} + C_{5} \|Q_{1} - Q_{2} \|_{\infty}.$ Also assume that $(C_{4} + C_{5} D) < 1,$ where $D = (C_{1} + \gamma C_{2})/(1-\gamma)$.
\end{assumption}
\begin{corollary}
\label{cor:cor-1}
Let Assumption \ref{assump:Lips-R-P} and Assumption \ref{assump:MV-strong} hold. Then, the we obtain the bound on $T_{0}$ as in \eqref{eq:asynch-Q-sample-1} with $B = (C_{5}+1)/(1 - (C_{4} + C_{5} D)),$ which does not depend on  $k_{0}$.
\end{corollary}
\subsection{Generative Model-Based Reinforcement Learning for T-MFE}
A model-based variant of the T-BR algorithm is also straightforward to construct.  We note that non-stationarity in our system (the model changes at each step) implies that there is no single model.  Hence, our approach follows the generation of a new model each time that the mean field evolves under a T-BR-like procedure.  Full details are presented in Appendix~\ref{sec:MBRL}.


text:
\begin{document}
\maketitle

\input{intro}
\input{preliminaries}
\input{mv-theory}
\input{experiments}
\input{conclusions}

\section*{Acknowledgments}
GK thanks Aleksandar Nikolov for useful discussions about the proof of Lemma~\ref{lem:cov-sens}.
\bibliographystyle{alpha}
\bibliography{biblio}

\appendix
\input{uv-theory}
\input{mv-proofs}
\input{conc-and-tails}

\end{document}


TITLE: Missing Exercises in Elementary Number Theory by Underwood Dudley.
QUESTION [0 upvotes]: I'm a beginner in math and I just started studying Elementary Number Theory by Dudley. So far I'm impressed, but I've noticed that the book does not include all the solutions to the exercises they present in the chapters, namely those that require you to prove some property.
I would really like to find the worked out solutions to all the exercises. I've looked all over for a solution to all the exercises with no luck. Perhaps I'm missing something or perhaps someone knows a source I could use?
Thank You

REPLY [3 votes]: There is a published instructors guide to go with Dudley's text, which includes some nice commentary as well as exercise solutions. Dover has it posted online: Instructors Guide to Elementary Number Theory


TITLE: Iverson Bracket / Conditional Sum of a string
QUESTION [1 upvotes]: I'm trying to turn calculations that I've been using on a data set into mathematic notation to write it down in a research paper.
One of my calculations creates a factor that determines how often a certain value (in this case the geographic location of $r$), appears in a string $s$.
As a definition I wrote:
$\Gamma$ is defined for a release $r$ as the number of its occurrences in the sequence $s$ divided by count of all its elements $n$. After readingh trhough various articles I based my notation to cases where people used Iverson brackets (Mathematical notation for a conditional sum) and came up with following:
\begin{equation}
\Gamma(r_{iso}) = \frac{\sum_{i=1}^{n} \Big[ s_{i} = r_{iso}\Big]}{n}
\end{equation}
\begin{align*}
\text{where}\\~r_{iso} &= \text{release origin of r} \\
  s_{i} &= \text{sequence of all accounted geographic locations}
\end{align*}
Reading this, would a math ninja scream out of agony or does this seem about right? Are there other / better ways of expressing this definition?
Thanks for your help!

REPLY [1 votes]: It wouldn’t bother me, though if I took this approach I’d probably write it
$$\Gamma(r_{iso})=\frac1n\sum_{i=1}^n[s_i=r_{iso}]$$
instead. Unfortunately, quite a few people are still unfamiliar with Iverson brackets, so it would probably be better to use a more familiar alternative. Perhaps the simplest is
$$\Gamma(r_{iso})=\frac1n\big|\{i:s_i=r_{iso}\}\big|$$
or
$$\Gamma(r_{iso})=\frac{\big|\{i:s_i=r_{iso}\}\big|}n\;,$$
depending on person preference.