11institutetext: University of Wuppertal, Germany
11email<EMAIL_ADDRESS>22institutetext: University of
Konstanz, Germany
22email<EMAIL_ADDRESS>33institutetext: University of
Passau, Germany
Institute for Artificial Intelligence Research and Development of Serbia
33email<EMAIL_ADDRESS>44institutetext: University of Kassel,
Germany
44email<EMAIL_ADDRESS>55institutetext: NII Tokyo, Japan
55email<EMAIL_ADDRESS>
# Exploiting Transformer-based Multitask Learning for the Detection of Media
Bias in News Articles

Timo Spinde 11 0000-0003-3471-4127 Jan-David Krieger 22 0000-0002-5360-2078
Terry Ruas 11 0000-0002-9440-780X Jelena Mitrović 33 0000-0003-3220-8749 Franz
Götz-Hahn 44 0000-0003-3465-5040  Akiko Aizawa 55 0000-0001-6544-5076 Bela
Gipp 11 0000-0001-6522-3019

###### Abstract

Media has a substantial impact on the public perception of events. A one-sided
or polarizing perspective on any topic is usually described as media bias. One
of the ways how bias in news articles can be introduced is by altering word
choice. Biased word choices are not always obvious, nor do they exhibit high
context-dependency. Hence, detecting bias is often difficult. We propose a
Transformer-based deep learning architecture trained via Multi-Task Learning
using six bias-related data sets to tackle the media bias detection problem.
Our best-performing implementation achieves a macro $F_{1}$ of 0.776, a
performance boost of 3% compared to our baseline, outperforming existing
methods. Our results indicate Multi-Task Learning as a promising alternative
to improve existing baseline models in identifying slanted reporting.

###### Keywords:

Media Bias Text Analysis Multi-Task Learning News Analysis

##  1 Introduction

Media bias, i.e., slanted news coverage, has the potential to drastically
change the public opinion on any topic [32]. One of the forms bias can be
expressed by is by word choice, e.g., depicting any content in a non-neutral
way [23]. Detecting and highlighting media bias might be relevant for media
analysis and mitigate the effects of biased reporting. To date, only a few
research projects focus on the detection and aggregation of bias [16, 6]. One
of the reasons that make the creation of automated methods to detect media
bias a complex task is often the subtle nature of media bias, which represents
a challenge for quantitative identification methods [10, 16, 33, 30]. While
many current research projects focus on collecting linguistic features to
describe media bias [11, 34, 29, 23], we propose a Transformer-based [39]
architecture for the classification of media bias. Similar models have
recently shown to achieve performance increases in the media bias domain,
e.g., sentence-level bias detection [6, 12, 32, 27]. However, so far, they
rely on very limited resources. Data sets with bias gold standard annotations
are, to date, only scarcely available, and exhibit various weaknesses, such as
low inter annotator agreement, small size, or no information about the
annotator background [32, 31, 36]. Additionally, state-of-the-art neural
language models usually require large amounts of training data to yield
meaningful representations [9, 24], which are incompatible with the size of
current media bias data sets [35, 10]. To mitigate the lack of suitable data
sets, our model incorporates Multi-Task Learning (MTL) [24], which allows for
increasing performance by sharing model representations between related tasks
[37, 13, 19]. The use of cross-domain data sets in our model is particularly
relevant for the media bias domain as multiple sources can provide a more
robust model. To the best of our knowledge, the MTL paradigm has not been
explored in existing work on media bias. Our research question is therefore to
assess whether MTL can improve models to classify media bias automatically.

The main contribution of this paper is to incorporate Transformer-based MTL
into a system to identify sentence-level media bias automatically. We exploit
MTL in the media bias context by computing multiple models based on different
combinations of auxiliary training data sets (section 2). All our models,
data, and code are publicly available on https://bit.ly/3cmiQgB.

##  2 Related Work

While there are multiple forms of media bias, e.g., bias by personal
perception or by the omission of information [28], our focus is on bias by
word choice, in which different words refer to the same concept [23]. We will
first summarize available media bias data sets and then present automated
methods to identify bias as well as MTL.

The concept of media bias is covered by many data sets [18, 1, 6, 10, 35].
However, they all exhibit specific deficiencies, such as (1) a low number of
topics [18, 16], (2) no annotations on the word level [18], (3) low inter-
annotator agreement [35, 17, 1, 18], (4) no background check for its
participants (except [35]), and (5) only article-level annotations [6]. Also,
some related papers focus on framing rather than on bias [1, 10], or on
Wikipedia instead of news[12], and results are only partially transferable. To
the best of our knowledge, the most extensive and precise data set was
presented recently [32]. The data set consists of 3700 sentences annotated by
expert raters on sentence-level with an inter-annotator agreement of 0.40
measured by Krippendorff’s $\alpha$ [15], which is higher than for all other
available data sets.

Several studies tackle the challenge of identifying media bias automatically
[23, 34, 12, 11, 6]. Most of them use hand-crafted features to detect bias
[11, 34]. For example, [34] identify and evaluate a wide range of linguistic,
lexical, and syntactic features serving as potential bias indicators. The
existing work on neural models is based on the data sets mentioned above,
which exhibit the described weaknesses [6, 12]. Most media bias models focus
on sentence-level bias [23, 12, 11, 6, 10]. Therefore, we follow the standard
practice and construct a sentence-level classifier.

MTL approaches have shown to be helpful when high-quality data sets in the
domain are scarce, but text corpora covering general related concepts are
available [38, 19, 40, 37, 13]. For example, [13] report that MTL applied on
BERT yields an accuracy increase of 1.03% compared to the baseline BERT in a
subjectivity detection task. MTL might be a suitable training paradigm for
media bias identification systems since sufficiently sized bias corpora with
qualitative hand-crafted annotations do not exist. Therefore, we propose the
first neural MTL media bias classifier composed of inter-domain and cross-
domain data sets.

##  3 Methodology

We explore how fine-tuning a language model via MTL can improve the
performance in detecting media bias on the sentence level. Computational costs
are an important consideration for us since we train multiple large-scale MTL
models. For this reason, we employ a distilled modification of BERT [9],
called DistilBERT [26], which achieves a 40% reduction in size while
simultaneously accelerating the training process by 60% and retaining 97% of
language understanding capabilities on NLP benchmark tasks [40]. DistilBERT
represents an appropriate architecture, keeping resource consumption and
performance balanced. The incorporation of larger models trained via MTL is
left to future research.

Our MTL technique is based on hard parameter sharing in which all hidden model
layers are shared between auxiliary training tasks [24]. Task-specific layers
are added on top of the last hidden state, accounting for the label structure
of auxiliary data sets. The MTL paradigm we propose is architecture-
independent and can be adjusted to future NLP architectures.

For our training procedure, we distinguish between models trained on in-domain
and cross-domain data sets. For in-domain data sets, the creation process
included concepts related to media bias, such as subjectivity [21].
Conversely, cross-domain data sets include data points that are not directly
annotated for or related to media bias, but are retrieved from tasks that bear
some connection to it. The auxiliary data sets we use comprise a diverse set
of NLP tasks requiring two different losses for the learning process – the
Cross-Entropy (CE) loss [8] and the Mean Squared Error (MSE) loss [25]. The
origin and number of the data used for the training of our models, as well as
their respective original tasks and used loss functions, are shown in Table 1.
We use in-domain (ID) and cross-domain (CD) data sets used in other MTL
studies within the language processing domain [37, 19, 13].

Data set | Domain | n | Task | Loss | Description
---|---|---|---|---|---
Reddit data set (Reddit) [4] | ID | 6861 | Single Sentence Regression | MSE |  Reddit comments labeled on a continuous scale ranging from 0 (supportive) to 1 (discriminatory)
Subjectivity data set (Subj) [21] | ID | 10000 | Single Sentence Classification | CE |  Movie reviews labeled as objective or opinionated
IMDb [20] | ID | 50000 | Single Sentence Classification | CE |  Movie reviews containing positive and negative sentiment labels
Wikipedia data set (Wiki)1 [22] | ID | 180000 | Single Sentence Classification | CE |  Neutral and biased sentence pairs from articles going against Wikipedia’s NPOV rule
|  |  |  |  |
Semantic Textual Similarity Benchmark (STS-B) data set [5] | CD | 10943 | Pairwise Sentence Similarity | MSE |  Multilingual and cross-lingual sentence pairs labeled in terms of similarity
Stanford Natural Language Inference (SNLI) corpus 1 [2] | CD | 570000 | Pairwise Sentence Classification | CE |  Sentence pairs labeled for linguistic relations within the labels entailment, neutral, or contradiction

  * •

1We only use 50000 text instances from these corpora in our MTL approach to
keep the size of training sets balanced.

Table 1: Auxiliary data sets incorporated in the MTL models (n = number of
instances)

fig. 1 outlines our in-domain MTL model consisting of DistilBERT’s encoder,
whose parameters are shared across tasks, and the added task-specific layers
111The cross-domain model is not shown due to lack of space but is published
at the repository mentioned in Section section 1.. The represented model is
based on the maximum number of possible data sets within the approach. In our
experiments on MTL, we try various combinations, including at least three in-
domain and five cross-domain data sets, respectively.

Figure 1: Outline of in-domain MTL model consisting of a shared encoder block
and task-specific layers. Note: We implement multiple MTL models based on
different combinations of the presented data sets.

For preprocessing and MTL training, we took the same approach as [19].
Initially, pre-trained parameters are loaded from huggingface
222https://huggingface.co/transformers/model˙doc/distilbert.html. We split up
data for a fixed-size subset of tasks into batches, and batches are merged and
shuffled to guarantee the model does not train on too many subsequent batches
of a single task. The preprocessing step is repeated every epoch. Batches are
then passed on by the data loader one by one to the model, which outputs task-
specific predictions and the respective loss. Finally, the loss is
backpropagated, and parameters are updated.

##  4 Experiments

To investigate the benefit of MTL to identify media bias on a fine-grained
linguistic level, we train ten models using MTL, which we compare to five
baseline models. As a consequence of a lack of robust guidelines for selection
criteria for auxiliary corpora, we choose a variety of auxiliary tasks to
fine-tune the DistilBERT model via MTL that have previously been used
successfully in MTL studies [37, 13, 19]. Each of our MTL models is trained
using a different combination of a sample of six popular data sets, where IMDb
[20], Subj [21], Wiki [22], and Reddit [4] are considered in-domain data sets,
and STS-B [5], and SNLI [2] comprise examples of cross-domain data sets333A
detailed description of the data sets is published at the repository mentioned
in Section section 1..

The in-domain models are based on bias-related data sets 444IMDb, Subj, Wiki,
Reddit. Combining the in-domain corpora yields five different models (table 2,
M1 - M5): four use triple combinations, and one model relies on all in-domain
data sets. The cross-domain models extend the pool of experiments by adding
the STS-B and SNLI data sets to each of the five in-domain models (table 2, M6
- M10). The approaches are oriented on the MTL fine-tuning approaches applied
in [37]. In their experiments based on BERT, the authors apply MTL on domain-
related and domain-unrelated data yielding a performance boost for sentiment
classification.

All experiments are performed on a Google Colab NVIDIA Tesla K80
555https://colab.research.google.com/notebooks/intro.ipynb. We choose the
AdamW optimizer [14] and a batch size of 32 . All downstream task layers are
based on a hidden state dimensionality of 768. All performance metrics are
calculated based on 5-fold cross-validation [3]. Thus, we divide the final
bias data set containing 1700 instances into five different train and tests
666We use a subset of BABE [32], introduced in section 2, to evaluate the MTL
models.. The models are then iteratively trained on all five training sets and
evaluated on the respective held-out test set. Finally, the performance
metrics on the test sets are averaged, yielding the cross-validated model
performance. Each respective model is trained over four epochs with an early
stopping criterion based on validation CE loss. In many cases, the model stops
learning after two epochs. The MTL fine-tuning is based on a learning rate of
$5\cdot 10^{-5}$.

As far as we know, there are no related works applying MTL in the media bias
domain. Therefore, we compare the performances of our MTL approaches to a set
of baseline models (table 2; B1-B5). We report the performance scores achieved
from pre-trained DistilBERT provided by huggingface (B1). Furthermore, we
train four DistilBERT models on each of the in-domain data sets (B2-B5). Thus,
we can observe whether the assumed performance boost of our MTL models results
from MTL rather than domain-relatedness of the training data.

We expect that fine-tuning via MTL leads to an improvement of DistilBERT’s
bias identification power. Mainly, we want to analyze whether the MTL
technique yields a substantial performance boost compared to simple Transfer
Learning (TL) approaches training the model on only a single data set.
Therefore, we run several experiments.

##  5 Results and Discussion

We show the performance indicators of our model on our expert-labeled media
bias data set in table 2, according to $F_{1}$, precision, recall, and loss.
Since the highest macro $F_{1}$ score does not necessarily match with the
lowest loss, we elaborate on the results from the perspective of both metrics.

| Model | Data sets | macro $F_{1}$ | micro $F_{1}$ | binary $F_{1}$ | Precision | Recall | CE Loss
---|---|---|---|---|---|---|---|---
| B1 |  huggingface DistilBERT | 0.746 | 0.750 | 0.711 | 0.805 | 0.640 | 0.513
TL | B2 | ✓ |  |  |  |  |  | 0.744 | 0.744 | 0.730 | 0.744 | 0.716 | 0.545
B3 |  | ✓ |  |  |  |  | 0.761 | 0.762 | 0.746 | 0.770 | 0.725 | 0.491
B4 |  |  | ✓ |  |  |  | 0.743 | 0.746 | 0.709 | 0.790 | 0.646 | 0.497
B5 |  |  |  | ✓ |  |  | 0.782 | 0.782 | 0.7695 | 0.785 | 0.754 | 0.466
ID MTL | M1 | ✓ | ✓ | ✓ |  |  |  | 0.768 | 0.768 | 0.753 | 0.778 | 0.731 | 0.482
M2 | ✓ | ✓ |  | ✓ |  |  | 0.760 | 0.760 | 0.746 | 0.766 | 0.729 | 0.495
M3 | ✓ |  | ✓ | ✓ |  |  | 0.773 | 0.774 | 0.762 | 0.777 | 0.755 | 0.482
M4 |  | ✓ | ✓ | ✓ |  |  | 0.776 | 0.777 | 0.759 | 0.794 | 0.727 | 0.464
M5 | ✓ | ✓ | ✓ | ✓ |  |  | 0.772 | 0.771 | 0.757 | 0.778 | 0.737 | 0.473
CD MTL | M6 | ✓ | ✓ | ✓ |  | ✓ | ✓ | 0.766 | 0.766 | 0.758 | 0.756 | 0.763 | 0.492
M7 | ✓ | ✓ |  | ✓ | ✓ | ✓ | 0.765 | 0.765 | 0.751 | 0.770 | 0.735 | 0.474
M8 | ✓ |  | ✓ | ✓ | ✓ | ✓ | 0.771 | 0.771 | 0.762 | 0.765 | 0.761 | 0.491
M9 |  | ✓ | ✓ | ✓ | ✓ | ✓ | 0.749 | 0.750 | 0.759 | 0.714 | 0.812 | 0.499
M10 | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ | 0.769 | 0.770 | 0.751 | 0.789 | 0.720 | 0.480
|  | Subj | IMDb | Reddit | Wiki | STS | SNLI |  |  |  |  |  |

Table 2: Results for all baseline models, i.e., the huggingface model or
models obtained by TL, as well as the models trained using MTL considering
only in-domain data sets or also incorporating cross-domain data. For each
metric we have denoted the best performance in bold.

Among all MTL-trained models the highest $F_{1}$ score is achieved from the
in-domain M4 model with 0.776. The best cross-domain model regarding macro
$F_{1}$ is reached by M8 with 0.771. Compared to DistilBERT, M4 achieves a 3%
increase in macro $F_{1}$, while B5 achieves the highest macro $F_{1}$ for TL-
based models at 0.782, which is not surpassed by any MTL approach. Although
all MTL models outperform DistilBERT, the highest macro $F_{1}$ score of all
MTL models is 0.6% lower than that of B5. Overall, MTL improves the B1
baseline macro $F_{1}$ score in a range from 0.3% (M9) to 3% (M4). When
considering the models from a loss-based perspective, the performance ranks
change slightly: M4 remains as the best in-domain MTL model, but M7 (the
second to last in terms of macro $F_{1}$ performance) reaches the lowest loss
within the cross-domain approaches. Compared to DistilBERT, M4 shows a
decrease in loss of 4.9%. B5 prevails as the best TL model with a CE loss of
0.466. In contrast to the macro $F_{1}$-based perspective, however, M4
achieves the lowest overall loss, outperforming B5 by 0.2%.

In general, our MTL approaches surpass the baseline methods. However, the best
overall model based on macro $F_{1}$ was a TL model trained on a data set
containing revised Wikipedia excerpts (B5). Based on CE loss, only one MTL
model slightly outperform this TL model. Thus, we cannot state whether
Transformer-Based MTL improves media bias detection on the sentence level. We
assume that the strong performance of B5 results from the relatedness of the
underlying data set to our bias corpus. The Wikipedia data set contains biased
and neutral sentences extracted from revised Wikipedia passages. Hence, the
data set is similar to our bias corpus777Let us point out that none of the
instances from the Wikipedia data set are contained in our target media bias
data set.. The only difference to our fine-tuning data set is the source from
which the data is extracted. Pre-training a Transformer-based model on a
highly bias-related corpus seems to hinder MTL’s relative performance
improvement. Furthermore, we assume that our selection of auxiliary data sets
might not have been sufficiently comprehensive. In our MTL approaches,
updating DistilBERT’s parameters only required the computation and back-
propagation of binary CE loss and MSE loss. [24] argues that well-performing
MTL approaches must be trained on NLP tasks, including multiple loss
functions.

Existing MTL studies [19, 13, 37] do not report diverse TL baseline models.
The MTL approaches are primarily compared to a pre-trained baseline model
provided by model libraries. Future research should incorporate a
comprehensive set of baseline models allowing for a more robust analysis.
Comparing our best MTL model to DistilBERT, the effect of MTL is similar as in
[13].

Considering our MTL-based media bias research, future work should include more
comprehensive sets of bias-related auxiliary data sets with multiple loss
functions. Possible tasks could, for example, comprise the detection of bias-
inducing linguistic features such as negative sentiment [34]. In this way,
deep learning techniques could benefit from other types of tasks, such as
classifying linguistic features. Moreover, future MTL approaches could benefit
from larger transformer models (e.g., XLNet [41], ELECTRA [7]). Our approach
based on DistilBERT is the first step towards balancing cloud-computing costs
and performance. We note that a follow-up experiment about an improved model
and a larger exploratory data analysis are already in progress and will be
published in the future.

##  6 Final Considerations

This work proposes a Transformer-based MTL approach to identify media bias by
word choice in news articles. The motivation for selecting the training
technique results from our observation that the size of available media bias
data sets is not compatible with the requirements of state-of-the-art neural
language models. We train ten MTL models based on different combinations of
six auxiliary data sets and compare them to five baseline models. Our results
show that the best performing MTL model partly surpasses the baseline models
in terms of macro $F_{1}$ loss and CE loss. Yet, we can not ascertain a
significant superiority of the MTL approach in classifying media bias
instances. The main limitation of our work is the restricted inclusion of
auxiliary tasks. In future work, we plan to incorporate more tasks based on
bias-inducing linguistic features. We have to emphasize that any successful
MTL implementation in the context of media bias identification could decrease
financial burdens emerging from the collection of hand-crafted training data.
Yet, at the same time, cloud computing requires substantial financial
resources. Costs of using larger models should therefore be properly
evaluated. We believe the MTL approach to be promising in the area and aim to
continue the research on MTL in connection with media bias identification in
the future.

## References

  * [1] Baumer, E., Elovic, E., Qin, Y., Polletta, F., Gay, G.: Testing and comparing computational approaches for identifying the language of framing in political news. In: Proceedings of the 2015 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies. pp. 1472–1482. Association for Computational Linguistics, Denver, Colorado (May–Jun 2015). https://doi.org/10.3115/v1/N15-1171, https://www.aclweb.org/anthology/N15-1171
  * [2] Bowman, S.R., Angeli, G., Potts, C., Manning, C.D.: A large annotated corpus for learning natural language inference. In: Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing. pp. 632–642. Association for Computational Linguistics, Lisbon, Portugal (Sep 2015). https://doi.org/10.18653/v1/D15-1075, https://www.aclweb.org/anthology/D15-1075
  * [3] Browne, M.W.: Cross-validation methods. J. Math. Psychol. 44(1), 108–132 (Mar 2000). https://doi.org/10.1006/jmps.1999.1279, https://doi.org/10.1006/jmps.1999.1279
  * [4] Cabot, P.H., Abadi, D., Fischer, A., Shutova, E.: Us vs. them: A dataset of populist attitudes, news bias and emotions. CoRR abs/2101.11956 (2021), https://arxiv.org/abs/2101.11956
  * [5] Cer, D., Diab, M., Agirre, E., Lopez-Gazpio, I., Specia, L.: Semeval-2017 task 1: Semantic textual similarity multilingual and crosslingual focused evaluation. Proceedings of the 11th International Workshop on Semantic Evaluation (SemEval-2017) (2017). https://doi.org/10.18653/v1/s17-2001, http://dx.doi.org/10.18653/v1/S17-2001
  * [6] Chen, W.F., Al Khatib, K., Wachsmuth, H., Stein, B.: Analyzing Political Bias and Unfairness in News Articles at Different Levels of Granularity. In: Proceedings of the Fourth Workshop on Natural Language Processing and Computational Social Science. pp. 149–154. Association for Computational Linguistics, Online (2020). https://doi.org/10.18653/v1/2020.nlpcss-1.16, https://www.aclweb.org/anthology/2020.nlpcss-1.16
  * [7] Clark, K., Luong, M.T., Le, Q.V., Manning, C.D.: ELECTRA: Pre-training Text Encoders as Discriminators Rather Than Generators. arXiv:2003.10555 [cs] (Mar 2020)
  * [8] De Boer, P.T., Kroese, D.P., Mannor, S., Rubinstein, R.Y.: A tutorial on the cross-entropy method. Annals of operations research 134(1), 19–67 (2005)
  * [9] Devlin, J., Chang, M.W., Lee, K., Toutanova, K.: BERT: Pre-training of deep bidirectional transformers for language understanding. In: Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers). pp. 4171–4186. Association for Computational Linguistics, Minneapolis, Minnesota (Jun 2019). https://doi.org/10.18653/v1/N19-1423, https://www.aclweb.org/anthology/N19-1423
  * [10] Fan, L., White, M., Sharma, E., Su, R., Choubey, P.K., Huang, R., Wang, L.: In plain sight: Media bias through the lens of factual reporting. In: Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP). pp. 6343–6349. Association for Computational Linguistics, Hong Kong, China (Nov 2019). https://doi.org/10.18653/v1/D19-1664, https://www.aclweb.org/anthology/D19-1664
  * [11] Hube, C., Fetahu, B.: Detecting biased statements in wikipedia. In: Companion Proceedings of the The Web Conference 2018. p. 1779–1786. WWW ’18, International World Wide Web Conferences Steering Committee, Republic and Canton of Geneva, CHE (2018). https://doi.org/10.1145/3184558.3191640, https://doi.org/10.1145/3184558.3191640
  * [12] Hube, C., Fetahu, B.: Neural based statement classification for biased language. In: Proceedings of the Twelfth ACM International Conference on Web Search and Data Mining. p. 195–203. WSDM ’19, Association for Computing Machinery, New York, NY, USA (2019). https://doi.org/10.1145/3289600.3291018, https://doi.org/10.1145/3289600.3291018
  * [13] Huo, H., Iwaihara, M.: Utilizing bert pretrained models with various fine-tune methods for subjectivity detection. In: Asia-Pacific Web (APWeb) and Web-Age Information Management (WAIM) Joint International Conference on Web and Big Data. pp. 270–284. Springer (2020)
  * [14] Kingma, D.P., Ba, J.: Adam: A method for stochastic optimization. In: Bengio, Y., LeCun, Y. (eds.) 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings (2015), http://arxiv.org/abs/1412.6980
  * [15] Krippendorff, K.: Computing krippendorff’s alpha-reliability. Departmental Papers (ASC); University of Pennsylvania (2011), https://repository.upenn.edu/cgi/viewcontent.cgi?article=1043&context=asc˙papers
  * [16] Lim, S., Jatowt, A., Färber, M., Yoshikawa, M.: Annotating and analyzing biased sentences in news articles using crowdsourcing. In: Proceedings of the 12th Language Resources and Evaluation Conference. pp. 1478–1484. European Language Resources Association, Marseille, France (May 2020), https://www.aclweb.org/anthology/2020.lrec-1.184
  * [17] Lim, S., Jatowt, A., Färber, M., Yoshikawa, M.: Annotating and analyzing biased sentences in news articles using crowdsourcing. In: Proceedings of the 12th Language Resources and Evaluation Conference. pp. 1478–1484. European Language Resources Association, Marseille, France (May 2020), https://www.aclweb.org/anthology/2020.lrec-1.184
  * [18] Lim, Sora and Jatowt, Adam and Yoshikawa, Masatoshi: Understanding Characteristics of Biased Sentences in News Articles. In: CIKM Workshops (2018), –http://ceur-ws.org/Vol-2482/paper13.pdf˝
  * [19] Liu, X., He, P., Chen, W., Gao, J.: Multi-task deep neural networks for natural language understanding. In: Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics. pp. 4487–4496. Association for Computational Linguistics, Florence, Italy (Jul 2019), https://www.aclweb.org/anthology/P19-1441
  * [20] Maas, A.L., Daly, R.E., Pham, P.T., Huang, D., Ng, A.Y., Potts, C.: Learning word vectors for sentiment analysis. In: Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies. pp. 142–150. Association for Computational Linguistics, Portland, Oregon, USA (Jun 2011), https://www.aclweb.org/anthology/P11-1015
  * [21] Pang, B., Lee, L.: A sentimental education: Sentiment analysis using subjectivity summarization based on minimum cuts. In: Proceedings of the 42nd Annual Meeting on Association for Computational Linguistics. p. 271–es. ACL ’04, Association for Computational Linguistics, USA (2004). https://doi.org/10.3115/1218955.1218990, https://doi.org/10.3115/1218955.1218990
  * [22] Pryzant, R., Diehl Martinez, R., Dass, N., Kurohashi, S., Jurafsky, D., Yang, D.: Automatically neutralizing subjective bias in text. Proceedings of the AAAI Conference on Artificial Intelligence 34(01), 480–489 (Apr 2020). https://doi.org/10.1609/aaai.v34i01.5385, https://ojs.aaai.org/index.php/AAAI/article/view/5385
  * [23] Recasens, M., Danescu-Niculescu-Mizil, C., Jurafsky, D.: Linguistic models for analyzing and detecting biased language. In: Proceedings of the 51st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). pp. 1650–1659 (2013), https://www.aclweb.org/anthology/P13-1162.pdf
  * [24] Ruder, S.: An overview of multi-task learning in deep neural networks. CoRR abs/1706.05098 (2017), http://arxiv.org/abs/1706.05098
  * [25] Sammut, C., Webb, G.I. (eds.): Mean Squared Error, pp. 653–653. Springer US, Boston, MA (2010). https://doi.org/10.1007/978-0-387-30164-8_528, “url–https://doi.org/10.1007/978-0-387-30164-8˙528˝
  * [26] Sanh, V., Debut, L., Chaumond, J., Wolf, T.: Distilbert, a distilled version of BERT: smaller, faster, cheaper and lighter. CoRR abs/1910.01108 (2019), http://arxiv.org/abs/1910.01108
  * [27] Spinde, T.: An interdisciplinary approach for the automated detection and visualization of media bias in news articles. In: 2021 IEEE International Conference on Data Mining Workshops (ICDMW) (2021), https://media-bias-research.org/wp-content/uploads/2021/09/Spinde2021g.pdf
  * [28] Spinde, T., Hamborg, F., Donnay, K., Becerra, A., Gipp, B.: Enabling news consumers to view and understand biased news coverage: A study on the perception and visualization of media bias. In: Proceedings of the ACM/IEEE Joint Conference on Digital Libraries in 2020. p. 389–392. JCDL ’20, Association for Computing Machinery, Virtual Event, China (2020). https://doi.org/10.1145/3383583.3398619, https://doi.org/10.1145/3383583.3398619
  * [29] Spinde, T., Hamborg, F., Gipp, B.: Media bias in german news articles: A combined approach. ECML PKDD 2020 Workshops: Workshops of the European Conference on Machine Learning and Knowledge Discovery in Databases (ECML PKDD 2020): INRA 2020, Ghent, Belgium, September 14–18, 2020, Proceedings 1323, 581–590 (2020). https://doi.org/10.1007/978-3-030-65965-3_41, https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7850083/
  * [30] Spinde, T., Kreuter, C., Gaissmaier, W., Hamborg, F., Gipp, B., Giese, H.: Do You Think It’s Biased? How To Ask For The Perception Of Media Bias. In: Proceedings of the ACM/IEEE Joint Conference on Digital Libraries (JCDL) (Sep 2021)
  * [31] Spinde, T., Krieger, D., Plank, M., Gipp, B.: Towards A Reliable Ground-Truth For Biased Language Detection. In: Proceedings of the ACM/IEEE Joint Conference on Digital Libraries (JCDL) (Sep 2021)
  * [32] Spinde, T., Plank, M., Krieger, J.D., Ruas, T., Gipp, B., Aizawa, A.: Neural Media Bias Detection Using Distant Supervision With BABE - Bias Annotations By Experts. In: Findings of the Association for Computational Linguistics: EMNLP 2021. Dominican Republic (Nov 2021)
  * [33] Spinde, T., Rudnitckaia, L., Hamborg, F., Gipp, B.: Identification of biased terms in news articles by comparison of outlet-specific word embeddings. In: Proceedings of the iConference 2021 (March 2021)
  * [34] Spinde, T., Rudnitckaia, L., Mitrović, J., Hamborg, F., Granitzer, M., Gipp, B., Donnay, K.: Automated identification of bias inducing words in news articles using linguistic and context-oriented features. Information Processing & Management 58(3), 102505 (2021). https://doi.org/10.1016/j.ipm.2021.102505, https://doi.org/10.1016/j.ipm.2021.102505
  * [35] Spinde, T., Rudnitckaia, L., Sinha, K., Hamborg, F., Gipp, B., Donnay, K.: MBIC – A media bias annotation dataset including annotator characteristics. In: Proceedings of the iConference 2021. iSchools (2021). https://doi.org/10.5281/zenodo.4474336
  * [36] Spinde, T., Sinha, K., Meuschke, N., Gipp, B.: TASSY - A Text Annotation Survey System. In: Proceedings of the ACM/IEEE Joint Conference on Digital Libraries (JCDL) (Sep 2021)
  * [37] Sun, C., Qiu, X., Xu, Y., Huang, X.: How to fine-tune bert for text classification? In: Sun, M., Huang, X., Ji, H., Liu, Z., Liu, Y. (eds.) Chinese Computational Linguistics. pp. 194–206. Springer International Publishing, Cham (2019)
  * [38] Sun, Y., Wang, S., Li, Y.K., Feng, S., Tian, H., Wu, H., Wang, H.: Ernie 2.0: A continual pre-training framework for language understanding. Proceedings of the AAAI Conference on Artificial Intelligence 34, 8968–8975 (04 2020). https://doi.org/10.1609/aaai.v34i05.6428
  * [39] Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A.N., Kaiser, L.u., Polosukhin, I.: Attention is all you need. In: Guyon, I., Luxburg, U.V., Bengio, S., Wallach, H., Fergus, R., Vishwanathan, S., Garnett, R. (eds.) Advances in Neural Information Processing Systems. vol. 30. Curran Associates, Inc. (2017), https://proceedings.neurips.cc/paper/2017/file/3f5ee243547dee91fbd053c1c4a845aa-Paper.pdf
  * [40] Wang, A., Singh, A., Michael, J., Hill, F., Levy, O., Bowman, S.R.: Glue: A multi-task benchmark and analysis platform for natural language understanding. arXiv preprint arXiv:1804.07461 (2018)
  * [41] Yang, Z., Dai, Z., Yang, Y., Carbonell, J., Salakhutdinov, R., Le, Q.V.: XLNet: Generalized Autoregressive Pretraining for Language Understanding. arXiv:1906.08237 [cs] (Jun 2019)


University of Gothenburg, Sweden and http://www.mathieulehaut.org/
lehaut@chalmers.sehttps://orcid.org/0000-0002-6205-0682University of
Gothenburg, Sweden and
https://www.cse.chalmers.se/~piterman/nir.piterman@chalmers.sehttps://orcid.org/0000-0002-8242-5357
Mathieu Lehaut and Nir Piterman [100]Theory of computation - Formal languages
and automata theory Supported by the ERC Consolidator grant D-SynMA (No.
772459)John Q. Open and Joan R. Access 2 42nd Conference on Very Important
Topics (CVIT 2016) CVIT 2016 CVIT 2016 December 24–27, 2016 Little Whinging,
United Kingdom 42 23

# Measuring the Gain of Reconfigurable Communication

Mathieu Lehaut  Nir Piterman

###### Abstract

We study the advantages of reconfigurable communication interfaces vs fixed
communication interfaces in the context of asynchronous automata. We study the
extension of asynchronous (Zielonka) automata with reconfigurable
communication interfaces. We show that it is possible to capture languages of
automata with reconfigurable communication interfaces by automata with fixed
communication interfaces. However, this comes at a cost of disseminating
communication (and knowledge) to all agents in a system. Thus, the system is
no longer behaving as a distributed system. We then show that this is
unavoidable by describing a language in which every agent that uses a fixed
communication interface either must be aware of all communication or become
irrelevant.

###### keywords:

Zielonka Automata, Reconfigurable Communication

###### category:

##  1 Introduction

In recent years, computation has permeated every aspect of our lives.
Computation devices have become so widely available that they are now
everywhere. They are lighter, cheaper, prevalent, and, ultimately, mobile.
Sensor networks, multi-agent systems, and robot teams use mobile and ad-hoc
networks. In such networks, participants/agents/elements come and go and
change the communication configuration based on need, location, and various
restrictions. These systems force us to consider how communication changes
when participants are numerous, mobile, and required to collaborate.

Already three decades ago, the modeling of mobility prompted Milner, Parrow,
and Walker to introduce the $\pi$-calculus [9, 10]. This is a process calculus
that allows message contents to include the name of channels. By transferring
channels to interested parties, communication configuration can change through
the run of the system. The $\pi$-calculus has become a standard for modeling
mobility and reconfigurability of communication. Building on the
$\pi$-calculus, the concurrency community has considered different means of
communication and how they support mobility and recently reconfiguration
(e.g., [4, 3, 7, 11, 1]). The study of different communication mechanisms,
some of them dynamic and mobile and some of them static, led to the
development of a rich theory about comparison of such systems for their
expressiveness [5, 6] The standard way is to try to create an encoding of one
formalism into another [6]. On the one hand, the encoding should be
compositional – respect the structure of original and target programs. It
should also have some operational correspondence – computations of the
original are mapped to computations of the target programs. Using this theory
one can show both equivalence of expressive power but also distinction (c.f.,
the seminal study in [6], or, e.g., [8] or the recent surprising results about
well known formalisms in [12]).

Van Glabbeek’s result mentioned above is particularly surprising as it shows
that a static communication formalism can simulate a dynamic communication
formalism [12]. Here we are interested in measuring differences in
communication when the two formalisms actually have the same expressive power.
Particularly, we are asking ourselves what is the value of reconfiguring
communication when a formalism with static communication has the same
expressive power. At the same time, we diverge from the common view in studies
of concurrency and concentrate on language technology. Hence, we consider a
canonical formalism in language theory for considering fixed communication –
_asynchronous automata_ or _Zielonka automata_. These are a well known model
that supports distribution of language recognition under a fixed communication
topology. The model is especially interesting due to Zielonka’s seminal result
on the ability to distribute languages in this model [13]. Zielonka’s result
starts from a given regular language and a target (fixed) distribution of the
alphabet. He then shows that if the deterministic automaton for the language
satisfies a simple condition about independence of communications then the
language can be distributed and accepted by a distributed team of agents.

We compare Zielonka automata with a reconfigurable variant inspired by
channeled transition systems [2]. Agents comprising a system are extended with
the ability to connect and disconnect from channels/letters. A communication
can occur on a channel if all the agents that are connected to the channel
agree on it. Otherwise, the communication is blocked. This is the exact notion
of communication of Zielonka automata, except that agents can connect and
disconnect to channels. In order to allow more than mere synchronization on
the channel, communications are extended by a data value. To distinguish
between Zielonka automata and their extension we still call the latter
_channeled transition systems_ , though they are much simpler than those
considered originally [2].

We then show, as expected, that the two formalisms are equivalent in
expressive power. As the structure of both formalisms includes one level of
parallel composition, the encoding is almost an isomorphism. We show two
different encodings: First, we consider Zielonka automata with global
transition relations. We show how to encode them using channeled transitions
systems with data. Second, we consider Zielonka automata with local transition
relations. Their encoding into channeled transition systems is achieved by
dropping the data in the previous encoding. The encoding in the other
direction is very similar, however, with an important caveat: the encoding
does not distribute the communication. Namely, all communication is shared
between all agents of the system. Given that all agents are informed about
everything they can autonomously decide which communications to ignore and
which communications to act upon.

Although we show the encoding only in the context of language equivalence and
not structural equivalence, we find the conclusion that the two formalisms
have the same expressive power very unsatisfying. Indeed, this conclusion
completely ignores who communicates with who in the distributed system, the
information that different participants have, and the potential knowledge that
agents have on the computation. This criterion is completely dropped from the
notion of equivalence. Indeed, there is a cost in one direction of the
encoding that is not evaluated according to current practices.

Finally, we show that this extra cost is unavoidable. We suggest a language
that can be recognized distributively by channeled transition system but not
by Zielonka automata. Namely, using reconfigurable communication agents
actively connect and disconnect from channels and keep themselves informed
only about crucial information. Throughout, agents are connected to a very
small number of channels that is independent of system size. However, some
(changing) channels are used for coordination of how to connect and disconnect
from the other channels. We show that for Zielonka automata to recognize the
same language some agents must be connected to the full set of channels and be
informed of everything. What’s more, every agent that is not connected to the
full set of channels can be made trivial by accepting unconditionally all
possible communication on channels that they are connected to. Thus, the only
possible translation from reconfigurable communication to fixed communication
is by making agents constantly connected to all channels that they might need
at some point. We give two versions of this construction with slightly
different properties with the essential difference being the distance to
“trivializability” being shorter if we add one more channel for coordination.

The rest of the paper is organized as follows. In Section 2 we recall the
definition of Zielonka automata and give the definition of the simplified
channeled transition systems. In Section 3 we give the translations between
the models and show that the data of channeled transition systems correspond
to the global transitions of Zielonka automata. We then show that in every
translation that removes the reconfigurability all agents either know
everything or are trivial, in Section 4. Finally, we conclude and discuss our
results in Section 5.

##  2 Definitions

###  2.1 Fixed communication structure

####  2.1.1 Distributed Alphabets.

We fix a finite set $\mathbb{P}$ of processes. Let $\Sigma$ be a finite
alphabet, and $\mathit{dom}:\Sigma\to 2^{\mathbb{P}}$ a domain function
associating each letter with the subset of processes listening to that letter.
The pair $(\Sigma,\mathit{dom})$ is called a distributed alphabet. We let
$\mathit{dom}^{-1}(p)=\\{a\in\Sigma\mid p\in\mathit{dom}(a)\\}$. It induces an
independence binary relation $I$ in the following way: $(a,b)\in
I\Leftrightarrow\mathit{dom}(a)\cap\mathit{dom}(b)=\emptyset$. Two words
$u=u_{1}\dots u_{n}$ and $v=v_{1}\dots v_{n}$ are said to be equivalent,
denoted by $u\sim v$, if one can start from $u$, repeatedly switch two
consecutive independent letters, and end up with $v$. Let us denote by $[u]$
the equivalence class of a word $u$. Let
$\mathcal{A}=(Q,\Sigma,q_{0},\Delta,F)$ be a deterministic automaton over
$\Sigma$. We say that $\mathcal{A}$ is $I$-diamond if for all pairs of
independent letters $(a,b)\in I$ and all states $q\in Q$, we have
$\Delta(q,ab)=\Delta(q,ba)$. If $\mathcal{A}$ has this property, then a word
$u$ is accepted by $\mathcal{A}$ if and only if all words in $[u]$ are
accepted. Zielonka’s result states that an $I$-diamond automaton can be
distributed to processes who are connected to channels according to
$\mathit{dom}$ [13].

####  2.1.2 Asynchronous Automata.

An asynchronous automaton (AA) over $\Sigma$ is a tuple
$\mathcal{B}=((S_{p})_{p\in\mathbb{P}},(s^{0}_{p})_{p\in\mathbb{P}},(\delta_{a})_{a\in\Sigma},\mathrm{Acc})$
such that:

  * •

$S_{p}$ is the set of states for process $p$, and $s^{0}_{p}\in S_{p}$ is its
initial state,

  * •

$\delta_{a}:\prod_{p\in\mathit{dom}(a)}S_{p}\to\prod_{p\in\mathit{dom}(a)}S_{p}$
is a transition function for letter $a$ that only depends on the states of
processes in $\mathit{dom}(a)$ and leaves those outside unchanged,

  * •

$\mathrm{Acc}\subseteq\prod_{p\in\mathbb{P}}S_{p}$ is a set of accepting
states.

A run of $\mathcal{B}$ is a sequence
$\textbf{s}_{0}a_{0}\textbf{s}_{1}a_{1}\dots\textbf{s}_{n}$ where for all
$i\leq n$, $\textbf{s}_{i}\in\prod_{p\in\mathbb{P}}S_{p}$, $a_{i}\in\Sigma$,
satisfying the following relation:

$\textbf{s}_{i+1}\downarrow_{\mathit{dom}(a)}=\delta_{a_{i}}(\textbf{s}_{i}\downarrow_{\mathit{dom}(a)})\text{
and
}\textbf{s}_{i+1}\downarrow_{\mathbb{P}\setminus\mathit{dom}(a)}=\textbf{s}_{i}\downarrow_{\mathbb{P}\setminus\mathit{dom}(a)}$

A run is accepting if $\textbf{s}_{n}$ belongs to $\mathrm{Acc}$. The word
$a_{0}a_{1}\dots$ is accepted by $\mathcal{B}$ if such an accepting run
exists. The language of $\mathcal{B}$, denoted by $\mathcal{L}(B)$, is the set
of words accepted by $\mathcal{B}$. For the rest of this paper, we will drop
the $\mathrm{Acc}$ component as we focus more on the runs themselves over
whether they can reach a certain target. That is, we assume that
$\mathrm{Acc}=\prod_{p\in\mathbb{P}}S_{p}$.

We also define a weaker version of asynchronous automata, called _local_
asynchronous automata (short: LAA or local AA), in which the transition
function is local to each process, and therefore independent with respect to
the states of all other processes. To avoid confusion, we sometimes refer to
normal asynchronous automata as defined earlier as _global_ asynchronous
automata (or global AA), though if not specified then AA refers to global AA.

####  2.1.3 Local Asynchronous Automata.

A local asynchronous automaton over $\Sigma$ is a tuple
$\mathcal{B}=((S_{p})_{p\in\mathbb{P}},(s^{0}_{p})_{p\in\mathbb{P}},(\delta_{p})_{p\in\mathbb{P}})$
where $S_{p}$ and $s^{0}_{p}$ are defined as before, and
$\delta_{p}:S_{p}\times\mathit{dom}^{-1}(p)\to S_{p}$ is the transition
function of process $p$. A run of $\mathcal{B}$ is a sequence
$\textbf{s}_{0}a_{0}\textbf{s}_{1}a_{1}\dots\textbf{s}_{n}$ where for all
$i\leq n$,
$\textbf{s}_{i}=(s_{i}^{p})_{p\in\mathbb{P}}\in\prod_{p\in\mathbb{P}}S_{p}$,
$a_{i}\in\Sigma$, satisfying the following relation:

$\displaystyle s_{i+1}^{p}=\begin{cases}\delta_{p}(s_{i}^{p},a_{i})&\text{ if
$p\in\mathit{dom}(a_{i})$,}\\\ s_{i}^{p}&\text{ otherwise.}\end{cases}$

Observe that a global AA can easily simulate a local AA, whereas the reverse
direction does not hold.

###  2.2 Reconfigurable communication

Let us consider here a model where the communication structure is not fixed,
and can be modified dynamically during a run. As before, fix a finite set
$\mathbb{P}$ of processes, with $|\mathbb{P}|=n$. Let us as well fix a finite
set $C$ of channels, with a role similar to the alphabet $\Sigma$ of the
previous section except without an added $\mathit{dom}$ function. Finally, let
$T$ be a (possibly infinite) set of message contents.

####  2.2.1 Channeled Transition Systems.

A Channeled Transition System (CTS) over $C$ is a tuple
$\mathcal{A}=(S,s^{0},\Delta,L)$ where:

  * •

$S$ is a set of states, $s^{0}\in S$ being the initial state,

  * •

$\Delta\subseteq S\times(T\times C)\times S$ is the transition relation, where
$(s,(t,c),s^{\prime})$ means going from state $s$ to $s^{\prime}$ after having
a message on channel $c$ with content $t$,

  * •

$L:S\to 2^{C}$ is a listening function such that $c\in L(s)$ if there is a
transition of the form $(s,(t,c),s^{\prime})\in\Delta$, i.e. state $s$ must be
listening to channel $c$ if there is some transition from $s$ involving a
message on $c$.

A run of $\mathcal{A}$ is a sequence $s_{0}m_{0}s_{1}m_{1}\dots$ starting from
the initial state $s^{0}$ and where for all $i\in\mathbb{N},m_{i}\in T\times
C$ and $(s_{i},m_{i},s_{i+1})\in\Delta$. The language of $\mathcal{A}$,
denoted by $\mathcal{L}(\mathcal{A})$, is the set of words over $C$ of the
form $c_{0}c_{1}\dots$ such that there exists a run of the form
$s_{0}(t_{0},c_{0})s_{1}(t_{1},c_{1})\dots$, i.e. we focus only on the
sequence of channels where messages are sent, and drop the states and message
contents.

Given a sequence of CTS $\mathcal{A}_{1},\dots,\mathcal{A}_{n}$ (one for each
$p\in\mathbb{P}$) with $\mathcal{A}_{p}=(S_{p},s^{0}_{p},\Delta_{p},L_{p})$,
one can define their parallel composition
$\mathcal{A}_{\parallel\mathbb{P}}=(S,s^{0},\Delta,L)$:

  * •

$S=\prod_{p\in\mathbb{P}}S_{p}$ and $s_{0}=(s^{0}_{1},\dots,s^{0}_{n})$,

  * •

$L(s_{1},\dots,s_{n})=\bigcup_{p\leq n}L_{p}(s_{p})$,

  * •

$((s_{1},\dots,s_{n}),(t,c),(s^{\prime}_{1},\dots,s^{\prime}_{n}))\in\Delta$
if the following conditions are met:

    1. 1.

$\exists p$ s.t. $c\in L_{p}(s_{p})$,

    2. 2.

$\forall p$ s.t. $c\in
L_{p}(s_{p}),(s_{p},(t,c),s^{\prime}_{p})\in\Delta_{p}$, and

    3. 3.

$\forall p$ s.t. $c\notin L_{p}(s_{p}),s^{\prime}_{p}=s_{p}$.

In plain words, there is a transition if all processes listening to the
corresponding channel have a transition, with at least one process listening
to the channel, whereas those that do not listen are left unchanged. Note that
if some process listens to that channel but does not implement the transition,
then that transition is blocked.

##  3 From AA to CTS and Back

We now focus on comparing the expressive power of those two formalisms. For
the rest of this section, we fix a finite set $\mathbb{P}$ of processes.

###  3.1 AA to CTS

Let $(\Sigma,\mathit{dom})$ be a distributed alphabet, and let $\mathcal{B}$
be an AA over it. One can construct a CTS $\mathcal{A}_{\parallel\mathbb{P}}$
with $\Sigma$ as set of channels that recognizes the same language as
$\mathcal{B}$.

####  3.1.1 Intuition.

The listening function of each agent is the same for all states: each process
always listens to the channels that have this process in their domain, i.e.
$L_{p}(s)=\mathit{dom}^{-1}(p)$ for all $s\in S_{p}$. The only part that is
not straightforward to emulate is that a transition of an AA depends on the
states of all processes in the domain of the corresponding letter. Therefore
each process in the CTS needs to share their states via message contents to
all others when emulating a transition.

######  Lemma 3.1.

Every language recognized by an AA over $(\Sigma,\mathit{dom})$ can be
recognized by a CTS with set of channels $\Sigma$.

######  Proof 3.2.

Let
$\mathcal{B}=((S_{p})_{p\in\mathbb{P}},(s^{0}_{p})_{p\in\mathbb{P}},(\delta_{a})_{a\in\Sigma})$
be an AA as described earlier. Let $A_{p}=(S_{p},s^{0}_{p},\Delta_{p},L_{p})$
be a CTS for process $p$ where:

  * •

$L_{p}(s)=\\{a\in\Sigma\mid p\in\mathit{dom}(a)\\}$ for all $s\in S_{p}$,

  * •

$\Delta_{p}=$

$\\{(s_{p},((s_{p^{\prime}})_{p^{\prime}\in\mathit{dom}(a)},a),s^{\prime}_{p})\mid
s_{p}=(s_{p^{\prime}})_{p^{\prime}\in\mathit{dom}(a)}\downarrow_{p}\text{ and
}s^{\prime}_{p}=\delta_{a}((s_{p^{\prime}})_{p^{\prime}\in\mathit{dom}(a)})\downarrow_{p}\\}$

i.e. an $a$-transition is possible if and only if all processes in
$\mathit{dom}(a)$ correctly share their own state in the message, and all
processes then update their state according to $\delta_{a}$.

By construction, one can verify that for each run of $\mathcal{B}$, there is a
corresponding run of $\mathcal{A}_{\parallel\mathbb{P}}$ where at each point,
the state of each process $p$ is the same in both runs. It follows that every
word in $\mathcal{L}(\mathcal{B})$ also belongs to
$\mathcal{L}(\mathcal{A}_{\parallel\mathbb{P}})$ and conversely
$\mathcal{A}_{\parallel\mathbb{P}}$ can only emulate runs of $\mathcal{B}$,
showing the reverse inclusion.

Note that the size of the constructed CTS lies almost entirely in the size of
$T$, the message contents set, which is $\prod_{p\in\mathbb{P}}S_{p}$. One
could reduce the size of $T$ by allowing processes to share their states one
communication at a time, though the state space would grow as each process
needs to store the states of others, and the language recognized would become
the $n$-stuttering of the original language.

For local AA the translation is even more straightforward, as no message
content is required (i.e. $T$ can be reduced to a singleton).

######  Corollary 3.3.

Every language recognized by an LAA over $(\Sigma,dom)$ can be recognized by a
CTS with set of channels $\Sigma$ and where $|T|=1$.

######  Proof 3.4.

In the case of LAA, the transition $\delta_{p}$ does not depend on the states
of other processes. Let $T=\\{t\\}$. We replace the transition $\Delta_{p}$ in
the proof of Lemma 3.1 by
$\Delta_{p}=\\{s_{p},(t,a),s^{\prime}_{p}\leavevmode\nobreak\
|\leavevmode\nobreak\ \delta_{p}(s_{p},a)=s^{\prime}_{p}\\}$.

###  3.2 CTS to AA

Let us now focus on the reverse direction. Let
$(\mathcal{A}_{p})_{p\in\mathbb{P}}$ be a sequence of CTS over $\mathbb{P}$
with set of channels $C$, and let $\mathcal{A}$ be their parallel composition.
Our goal is to create an AA with alphabet $C$ that recognizes the same
language. The question that arises is: what should $\mathit{dom}$ be defined
as for the distributed alphabet $(C,\mathit{dom})$?

If we allow $\mathit{dom}$ to be unrestricted, one could define it as the
complete domain function: $\mathit{dom}(a)=\mathbb{P}$ for all channels. In
that case, it is trivial to build an AA over $(C,\mathit{dom})$ that emulates
$\mathcal{A}$, as each process can simply stutter when they are not supposed
to listen to a channel.

######  Lemma 3.5.

Every language recognized by a CTS over set of channels $C$ can be recognized
by an AA over $C$ and the complete domain function.

######  Proof 3.6.

Consider $(\mathcal{A}_{p})_{p\in\mathbb{P}}$, where
$A_{p}=(S_{p},s_{0}^{P},A_{p},L_{p})$, with $\mathcal{A}=(S,s^{0},\Delta,L)$
being their parallel composition. We build
$\mathcal{B}=((Q_{p})_{p\in\mathbb{P}},(q^{0}_{p})_{p\in\mathbb{P}},(\delta_{c})_{c\in
C})$ as follows:

  * •

for all $p\in\mathbb{P}$, $Q_{p}=S_{p}$, and $q^{0}_{p}=s^{0}_{p}$

  * •

For channel $c\in C$ we have $\delta_{c}$ defined as follows.

$\delta_{c}=\left\\{((q_{p})_{p\in\mathbb{P}},(q^{\prime}_{p})_{p\in\mathbb{P}})\left|\begin{array}[]{l}\exists
t\in T,p\in\mathbb{P}.c\in L_{p}(q_{p})\mbox{ and }\forall
p^{\prime}\in\mathbb{P}.\\\ \mbox{If }c\in
L_{p}(q_{p}),(q_{p^{\prime}},(t,c),q^{\prime}_{p^{\prime}})\in\Delta_{p^{\prime}}\text{
and}\\\ \mbox{If }c\notin
L_{p}(q_{p}),q_{p}=q^{\prime}_{p}\end{array}\right.\right\\}$

Note that having global transitions is necessary to ensure all processes share
the same message content $t$. However if we assume that $T$ is a singleton,
then local transitions suffice.

######  Corollary 3.7.

Every language recognized by a CTS over set of channels $C$, where $|T|=1$ can
be recognized by an LAA over $C$.

Actually, it is not even necessary that all processes listens to all channels.
It suffices that at least one process $p\in\mathbb{P}$ does (i.e.
$\mathit{dom}^{-1}(p)=C$), and implements the transitions as described above.
Any other process can listen to any subset of channels and simply allow any
transition to happen on those channels. In other words, one process serves as
a centralized executor of the simulation, while others simply need to be non-
blocking.

In the next section we show that the complete domain is required.

##  4 Trivializable and Fully Listening

We now give an example of a CTS such that the method described above is the
only way of accepting the same language. The idea is to allow every possible
subset of channels to be either fully independent, that is every one of those
channels can be used in parallel, or make them sequentially dependent, that is
they can only be used in a certain order. This status can be switched by a
communication on a separate channel (that all processes listen to), called the
switching channel. Moreover, after enough switches, a different channel will
serve as the switching channel. That way, all channels have the opportunity to
serve as the switching channel, given enough switches. Notice that our
construction does not use messages. Thus, already the weakest form of CTS
shows this property. We start with a simpler construction with a single
switching channel that can cycle through all possible subsets according to
some order. Then we give a more refined construction with two switching
channels that allows for a finer control on the dependent subset.

###  4.1 Single Switching Channel

Let $\mathbb{P}=\\{p_{1},\dots,p_{n}\\}$. We fix
$C=\\{c_{1},\dots,c_{n},c_{n+1}\\}$, that is, we have one channel per process
and one additional channel to be used as switching channel (dynamically).

For all $\mathrm{sc}\in C$ ($\mathrm{sc}$ stands for _switching channel_), fix
$<_{\mathrm{sc}}$ an arbitrary total order over
$2^{C\setminus\\{\mathrm{sc}\\}}$, with the only requirement that $\emptyset$
be the minimal element. Intuitively, a set in
$2^{C\setminus\\{\mathrm{sc}\\}}$ will represent the set of dependent
channels, and a switch will go to the next one with respect to
$<_{\mathrm{sc}}$. Let us denote by
$\mathit{inc}_{<_{\mathrm{sc}}}:2^{C\setminus\\{\mathrm{sc}\\}}\to
2^{C\setminus\\{\mathrm{sc}\\}}\cup\\{\bot\\}$ the function that returns the
next set according to $<_{\mathrm{sc}}$ or $\bot$ for the maximal element.

Additionally, for every subset $D\subseteq C$, we fix
${\mbox{{${}$}{{\vbox{\offinterlineskip\hbox{\hskip
3.87495pt\scriptsize{${D}$}}\vskip-2.58334pt\hbox{\normalsize{${+}$}}}}}{${1}$}}}:C\to
C$ a function that cycles through all elements of $D$ and is the identity on
$C\setminus D$. For convenience we write ${d}$ ${D}$ ${+}$ ${1}$ for
${\mbox{{${}$}{{\vbox{\offinterlineskip\hbox{\hskip
3.87495pt\scriptsize{${D}$}}\vskip-2.58334pt\hbox{\normalsize{${+}$}}}}}{${1}$}}}(d)$.
We also define ${\mbox{{${}$}{{\vbox{\offinterlineskip\hbox{\hskip
3.87495pt\scriptsize{${D}$}}\vskip-2.58334pt\hbox{\normalsize{${-}$}}}}}{${1}$}}}:D\to
D$ the inverse function and use the same notation. Namely, for every $d\in D$
we have ${\mbox{{${({\mbox{{${d}$}{{\vbox{\offinterlineskip\hbox{\hskip
3.87495pt\scriptsize{${D}$}}\vskip-2.58334pt\hbox{\normalsize{${-}$}}}}}{${1}$}}})}$}{{\vbox{\offinterlineskip\hbox{\hskip
3.87495pt\scriptsize{${D}$}}\vskip-2.58334pt\hbox{\normalsize{${+}$}}}}}{${1}$}}}=d$
and ${\mbox{{${({{\mbox{{${d}$}{{\vbox{\offinterlineskip\hbox{\hskip
3.87495pt\scriptsize{${D}$}}\vskip-2.58334pt\hbox{\normalsize{${+}$}}}}}{${1}$}}}})}$}{{\vbox{\offinterlineskip\hbox{\hskip
3.87495pt\scriptsize{${D}$}}\vskip-2.58334pt\hbox{\normalsize{${-}$}}}}}{${1}$}}}=d$.
We denote by $c_{D}\in D$ an arbitrary element of $D$.

Finally, we set $T=\\{t\\}$, and omit the message content component in
transitions.

We build $\mathcal{A}_{p}=(S_{p},s^{0}_{p},\Delta_{p},L_{p})$ for $p=p_{k}$ as
follows:

  * •

$S_{p}=\\{(c,\mathrm{sc},D,d)\mid c,\mathrm{sc}\in C,D\subseteq
C\setminus\\{\mathrm{sc}\\},d\in D\cup\\{c\\}\\}$, and
$s_{p}^{0}=(c_{k},c_{n+1},\emptyset,c_{k})$.

The first component is the channel assigned to this process, initially $c_{k}$
for process $k$, but may change if $c_{k}$ becomes the switching channel. The
second component is the current switching channel, initialized to $c_{n+1}$
for all processes. Component $D$ represents the set of channels that are
currently dependent, and $d$ is the next channel that $\mathcal{A}_{k}$ is
listening to on which it is expecting communication.

  * •

All processes listen to the switching channel and their assigned channel, plus
all of $D$ if it contains the assigned channel:

$L_{p}(c,\mathrm{sc},D,d)=\left\\{\begin{array}[]{l
l}\\{\mathrm{sc},c,{\mbox{{${c}$}{{\vbox{\offinterlineskip\hbox{\hskip
3.87495pt\scriptsize{${D}$}}\vskip-2.58334pt\hbox{\normalsize{${-}$}}}}}{${1}$}}}\\}&\mbox{if
}c\in D\\\ \\{\mathrm{sc},c\\}&\mbox{if }c\notin D\end{array}\right.$

  * •

The transition $\Delta_{p}$ is the union of the sets in Figure 1.

The first two kinds of transitions handle the independence of all channels in
$C\setminus D$ and the cycling through the channels of $D$. If $c\notin D$
then $c={\mbox{{${c}$}{{\vbox{\offinterlineskip\hbox{\hskip
3.87495pt\scriptsize{${D}$}}\vskip-2.58334pt\hbox{\normalsize{${-}$}}}}}{${1}$}}}$.
In this case, the first two sets simply say that a transition on $c$ is always
possible possible. If $c\in D$, then the process awaits until it gets a
message on ${c}$ ${D}$ ${-}$ ${1}$ and then is ready to interact on $c$. After
interaction on $c$ it awaits another interaction on ${c}$ ${D}$ ${-}$ ${1}$.
It follows that all the processes owning the channels in $D$ enforce together
the cyclic order on the messages in $D$. This part is further illustrated in
Figure 2. The rest or the transitions describe what happens when a switch
occurs. Sets three and four describe what happens when the next set according
to $<_{\mathrm{sc}}$ is defined. In this case, the next set becomes the new
set of dependent channels $D$. Set three handles the case of the process that
is in charge of the channel becoming the first channel to communicate on the
new set $\mathit{inc}_{<_{\mathrm{sc}}}(D)$. This process is ready for
communication on this first channel. The fourth set handles the case of all
other processes. All other processes are either in charge of channels in
$D^{\prime}$, in which case they set themselves to await a communication on
the previous in $D^{\prime}$ or they are in charge of channels not in
$D^{\prime}$ in which case, $c$ and
${\mbox{{${c}$}{{\vbox{\offinterlineskip\hbox{\hskip
3.87495pt\scriptsize{${D^{\prime}}$}}\vskip-2.58334pt\hbox{\normalsize{${-}$}}}}}{${1}$}}}=c$,
and the process is ready to communicate on $c$. Finally, sets five and six
describe what happens when the next set according to $<_{\mathrm{sc}}$ is
undefined. In this case, the next dependent set becomes $\emptyset$. Most
processes just set the dependent set to $\emptyset$ and allow communication on
“their” channel (set 5). The process that was in charge of the new switcghing
channel ${\mathrm{sc}}$ ${C}$ ${+}$ ${1}$ takes over the old switching channel
$\mathrm{sc}$ and is ready to communicate on it (set 6). Notice that
communications on the switching channel affect all processes. The change in
$D$ and the change of the switching channel is further illustrated in Figure
3.

$\begin{array}[]{l l
l}\Delta_{p}=&\\{((c,\mathrm{sc},D,c),c,(c,\mathrm{sc},D,{\mbox{{${c}$}{{\vbox{\offinterlineskip\hbox{\hskip
3.87495pt\scriptsize{${D}$}}\vskip-2.58334pt\hbox{\normalsize{${-}$}}}}}{${1}$}}}))\\}&\cup\\\
&\\{((c,\mathrm{sc},D,{\mbox{{${c}$}{{\vbox{\offinterlineskip\hbox{\hskip
3.87495pt\scriptsize{${D}$}}\vskip-2.58334pt\hbox{\normalsize{${-}$}}}}}{${1}$}}}),{\mbox{{${c}$}{{\vbox{\offinterlineskip\hbox{\hskip
3.87495pt\scriptsize{${D}$}}\vskip-2.58334pt\hbox{\normalsize{${-}$}}}}}{${1}$}}},(c,\mathrm{sc},D,c)\\}&\cup\\\
&\left\\{((c,\mathrm{sc},D,d),\mathrm{sc},(c,\mathrm{sc},D^{\prime},c))\left|\leavevmode\nobreak\
\begin{array}[]{l}D^{\prime}=\mathit{inc}_{<_{\mathrm{sc}}}(D)\neq\bot\\\
\mbox{and }c=c_{D^{\prime}}\end{array}\right.\right\\}&\cup\\\
&\left\\{((c,\mathrm{sc},D,d),\mathrm{sc},(c,\mathrm{sc},D^{\prime},{\mbox{{${c}$}{{\vbox{\offinterlineskip\hbox{\hskip
3.87495pt\scriptsize{${D^{\prime}}$}}\vskip-2.58334pt\hbox{\normalsize{${-}$}}}}}{${1}$}}}))\left|\leavevmode\nobreak\
\begin{array}[]{l}D^{\prime}=\mathit{inc}_{<_{\mathrm{sc}}}(D)\neq\bot\\\
\mbox{and }c\neq c_{D^{\prime}}\end{array}\right.\right\\}&\cup\\\
&\left\\{((c,\mathrm{sc},D,d),\mathrm{sc},(c,{\mbox{{${\mathrm{sc}}$}{{\vbox{\offinterlineskip\hbox{\hskip
3.87495pt\scriptsize{${C}$}}\vskip-2.58334pt\hbox{\normalsize{${+}$}}}}}{${1}$}}},\emptyset,c))\left|\begin{array}[]{l}\mathit{inc}_{<_{\mathrm{sc}}}(D)=\bot\mbox{
and}\\\ c\neq{\mbox{{${\mathrm{sc}}$}{{\vbox{\offinterlineskip\hbox{\hskip
3.87495pt\scriptsize{${C}$}}\vskip-2.58334pt\hbox{\normalsize{${+}$}}}}}{${1}$}}}\end{array}\right.\right\\}&\cup\\\
&\left\\{((c,\mathrm{sc},D,d),\mathrm{sc},(\mathrm{sc},{\mbox{{${\mathrm{sc}}$}{{\vbox{\offinterlineskip\hbox{\hskip
3.87495pt\scriptsize{${C}$}}\vskip-2.58334pt\hbox{\normalsize{${+}$}}}}}{${1}$}}},\emptyset,\mathrm{sc}))\left|\begin{array}[]{l}\mathit{inc}_{<_{\mathrm{sc}}}(D)=\bot\mbox{
and}\\\ c={\mbox{{${\mathrm{sc}}$}{{\vbox{\offinterlineskip\hbox{\hskip
3.87495pt\scriptsize{${C}$}}\vskip-2.58334pt\hbox{\normalsize{${+}$}}}}}{${1}$}}}\end{array}\right.\right\\}\end{array}$
Figure 1: The transitions comprising $\Delta_{p}$ of the single switching
channel case. Figure 2: Illustration of how the order on the channels in $D$
is maintained. We consider the case where $D=\\{1,\ldots,n\\}$ and $p_{i}$ is
in charge of channel $i$. The order between the channels is the natural order
on $\\{1,\ldots,n\\}$. The black token indicates the current state for each
process. Transitions that are on the same channel are connected with a dashed
line. The system is set up for next communication on channel $1$ and all other
channels are blocked. Indeed, both agents listening to channel $1$ are ready
to interact on $1$ ($p_{1}$ in state $(1,n+1,D,1)$ and $p_{2}$ in state
$(2,n+1,D,1)$) and for every other channel $i>1$ agent $i$ is awaiting
communication on $i-1$ ($p_{i}$ in state $(i,n+1,D,i-1)$) so channel $i$ is
not enabled.  Figure 3:  Illustration of how the set $D$ and the switching
channel $\mathrm{sc}$ change whenever there is a communication on
$\mathrm{sc}$. We consider the case where there are three processes and four
channels. Each column corresponds to the status after one more communication
on $\mathrm{sc}$. Each channel is in turn the switching channel starting with
$4$. The channels in $D$ at a certain time/column are marked with a black box.
We cycle through the states in $\\{1,\ldots,4\\}\setminus\\{\mathrm{sc}\\}$
according to set size first and then lexigographically on the sorted set.

Let $\mathcal{A}$ be the parallel composition of $(\mathcal{A}_{p})$. The size
of the state space of $\mathcal{A}$ is in $O((n^{3}.2^{n})^{n})$.

###  4.2 Asynchronous Automata Construction

We show that an AA that recognizes the same language as $\mathcal{A}$ has the
following property: for each process $p$, either $p$ listens to every channel
($\mathit{dom}^{-1}(p)=C$), or from every reachable state there is a path to a
bottom strongly connected component that is complete w.r.t.
$\mathit{dom}^{-1}(p)$. In the former case, we call $p$ _fully-listening_. In
the latter case, we say that $p$ is _trivializable_ , as once it is in this
bottom SCC it can never block communications ever again, thus $p$ becomes
irrelevant to the rest of the computation.

######  Lemma 4.1.

Let $\mathcal{B}$ be an AA such that
$\mathcal{L}(\mathcal{B})=\mathcal{L}(\mathcal{A})$. Each process in
$\mathcal{B}$ is either fully-listening or trivializable.

######  Proof 4.2.

Let
$\mathcal{B}=((S_{p})_{p\in\mathbb{P}},(s^{0}_{p})_{p\in\mathbb{P}},(\delta_{a})_{a\in\Sigma})$,
and let $p\in\mathbb{P}$. Assume that $p$ is not fully-listening, so let
$C_{p}=\mathit{dom}^{-1}(p)\subsetneq C$. In particular, let $c\in C\setminus
C_{p}$ be a channel that $p$ does not listen to.

Let $s_{p}$ be a reachable state for $p$ in $\mathcal{B}$. Then there is $w$ a
computation in $\mathcal{L}(\mathcal{B})$ such that $p$ reaches state $s_{p}$
after $w$. Consider the same computation in $\mathcal{A}$, and let
$\mathrm{sc}$ be the current switching channel in $\mathcal{A}$ at the end of
$w$. Let $\mathrm{sc}\cdot c_{1}\cdot...\cdot c_{n-1}\cdot c$ be the sequence
of channels from $\mathrm{sc}$ to $c$ according to the order from  ${C}$ ${+}$
${1}$. Then there is a continuation $w^{\prime}$ of $w$ of the form
$\mathrm{sc}^{k_{0}}\cdot c_{1}^{k_{1}}\cdot...\cdot c_{n-1}^{k_{n-1}}$ with
$k_{0},\dots,k_{n-1}\in\mathbb{N}$ such that:

  * •

$ww^{\prime}\in\mathcal{L}(\mathcal{A})$,

  * •

$c$ is the current switching channel and the dependent set $D$ is $\emptyset$.

From this, every continuation $w^{\prime\prime}\in(C\setminus\\{c\\})^{\ast}$
is still in $\mathcal{L}(\mathcal{A})$ and does not change the switching
channel or the dependent set. In particular, every
$w^{\prime\prime}\in(\mathit{dom}^{-1}(p))^{*}$ maintains that $w\cdot
w^{\prime}\cdot w^{\prime\prime}$ is also in
$\mathcal{L}(\mathcal{A})=\mathcal{L}(\mathcal{B})$. Therefore, from the state
reached in $\mathcal{B}$ after $ww^{\prime}$, there is a path to a strongly
connected component that will implement all transitions in
$\mathit{dom}^{-1}(p)$, i.e. a complete one.

###  4.3 Two Switching Channels

We outline a second construction that allows for a finer control on the set of
dependent channels using an additional switching channel. Aside from the two
switching channels, there is always one _highlighted_ non-switching channel.
The first switching channel, $\mathrm{tg}$ (for _toggling channel_), is used
to add the highlighted channel to the dependent set. The second switching
channel, $\mathrm{hl}$ (for _highlighting channel_), changes the highlighted
channel to the next non-switching channel. With that setup, it is always
possible to go from an empty dependent set to any set $D$ in a linear number
of steps by iterating on $D$: switch the highlighted channel to the next one
in $D$, then toggle it, repeat. This takes at most $n$ uses of $\mathrm{hl}$
to cycle through all channels and $n$ uses of $\mathrm{tg}$ to add them. In
the previous construction, it could take up to $2^{n}$ steps to reach a target
set. Finally, after enough uses of $\mathrm{hl}$, the two switching channels
change so that every channel can eventually be one of the switching channels,
and the dependent set is also reset to the empty set.

Formally, let us first introduce some useful notations. We let
$\mathbb{P}=\\{p_{1},\dots,p_{n}\\}$ and $C=\\{c_{1},\dots,c_{n+2}\\}$. As in
the previous construction, for every subset $D\subseteq C$ we fix
${\mbox{{${}$}{{\vbox{\offinterlineskip\hbox{\hskip
3.87495pt\scriptsize{${D}$}}\vskip-2.58334pt\hbox{\normalsize{${+}$}}}}}{${1}$}}}:C\to
C$ a function that cycles through all elements of $D$ and is the identity on
$C\setminus D$. For convenience we write ${d}$ ${D}$ ${+}$ ${1}$ for
${\mbox{{${}$}{{\vbox{\offinterlineskip\hbox{\hskip
3.87495pt\scriptsize{${D}$}}\vskip-2.58334pt\hbox{\normalsize{${+}$}}}}}{${1}$}}}(d)$.
As before we also use ${\mbox{{${}$}{{\vbox{\offinterlineskip\hbox{\hskip
3.87495pt\scriptsize{${D}$}}\vskip-2.58334pt\hbox{\normalsize{${-}$}}}}}{${1}$}}}:D\to
D$ the inverse function and use the same notation. When the two switching
channels $\mathrm{tg}$ and $\mathrm{hl}$ are known, we denote by
$C^{\ast}=C\setminus\\{\mathrm{tg},\mathrm{hl}\\}$ the set of non-switching
channels. Finally, let $c^{1^{\star}}$ and $c^{0^{\star}}$ be two channels in
$C^{\ast}$ such that
$c^{1^{\star}}={\mbox{{${c^{0^{\star}}}$}{{\vbox{\offinterlineskip\hbox{\hskip
3.87495pt\scriptsize{${C^{*}}$}}\vskip-2.58334pt\hbox{\normalsize{${+}$}}}}}{${1}$}}}$.
Those two are used to check when we have cycled through every non-switching
channels.

Now for $p\in\mathbb{P}$ we build
$\mathcal{A}_{p}=(S_{p},s^{0}_{p},\Delta_{p},L_{p})$ with its components
described as follows:

  * •

A state is of the form $s=(c,\mathrm{tg},\mathrm{hl},h,D,d)\in C^{4}\times
2^{C}\times C$. As in the first construction, $c$ is the channel currently
assigned to $p$, which may change when the switching channels are replaced.
The channels $\mathrm{tg}$ and $\mathrm{hl}$ are those two switching channels.
Channel $h$ is the highlighted non-switching channel. Finally, $D$ is the
current dependent set and $d$ the next channel available for a communication
for $p$.

  * •

The initial state is
$s^{0}_{p}=(c_{k},c_{n+1},c_{n+2},c^{1^{\star}},\emptyset,c_{k})$, where $k$
is the index such that $p=p_{k}$.

  * •

All processes listen to both switching channels and their assigned channel,
plus, potentially, the previous channel in $D$ if $D$ contains the assigned
channel:

$L_{p}(c,\mathrm{tg},\mathrm{hl},h,D,d)=\left\\{\begin{array}[]{l
l}\\{\mathrm{tg},\mathrm{hl},c,{\mbox{{${c}$}{{\vbox{\offinterlineskip\hbox{\hskip
3.87495pt\scriptsize{${D}$}}\vskip-2.58334pt\hbox{\normalsize{${-}$}}}}}{${1}$}}}\\}&\mbox{if
}c\in D\\\ \\{\mathrm{tg},\mathrm{hl},c\\}&\mbox{if }c\notin
D\end{array}\right.$

  * •

The transition $\Delta_{p}$ is the union of the sets in Figure 4. The first
two kinds of transition are similar to the previous construction. The third
and fourth kind are the toggling mechanism, which adds the currently
highlighted channel $h$ to the dependent set. If the followed channel is not
$h$ then update the previous channel according to the set $D\cup\\{h\\}$. If
the followed channel is $h$ then expect the next communication on $h$. The
remaining are the highlighting mechanism. When a communication on
$\mathrm{hl}$ occurs, the highlighted channel changes to the next one. If the
highlighted channel is not maximal then go to the next highlighted channel
(5). If we have already cycled through all non-switching channels once (the
current highlighted channel is maximal), we may have to update the first
component if the channel assigned to this process becomes a switching channel,
and the highlighted channel and dependent set are both reset, then new
channels assume the roles of toggling and highlighting. That is, either “our
channel” is untouched by the change (6), or “our channel” is assigned to
$\mathrm{tg}$ (7) or to $\mathrm{hl}$ (8).

$\begin{array}[]{l
l}\\{(c,\mathrm{tg},\mathrm{hl},h,D,c),c,(c,\mathrm{tg},\mathrm{hl},h,D,{\mbox{{${c}$}{{\vbox{\offinterlineskip\hbox{\hskip
3.87495pt\scriptsize{${D}$}}\vskip-2.58334pt\hbox{\normalsize{${-}$}}}}}{${1}$}}})\\}&\cup\\\
\\{(c,\mathrm{tg},\mathrm{hl},h,D,{\mbox{{${c}$}{{\vbox{\offinterlineskip\hbox{\hskip
3.87495pt\scriptsize{${D}$}}\vskip-2.58334pt\hbox{\normalsize{${-}$}}}}}{${1}$}}}),{\mbox{{${c}$}{{\vbox{\offinterlineskip\hbox{\hskip
3.87495pt\scriptsize{${D}$}}\vskip-2.58334pt\hbox{\normalsize{${-}$}}}}}{${1}$}}},(c,\mathrm{tg},\mathrm{hl},h,D,c)\\}&\cup\\\
\\{(c,\mathrm{tg},\mathrm{hl},h,D,d),\mathrm{tg},(c,\mathrm{tg},\mathrm{hl},h,E,{\mbox{{${c}$}{{\vbox{\offinterlineskip\hbox{\hskip
3.87495pt\scriptsize{${E}$}}\vskip-2.58334pt\hbox{\normalsize{${-}$}}}}}{${1}$}}})\leavevmode\nobreak\
|\leavevmode\nobreak\ c\neq h\wedge E=D\cup\\{h\\}\\}\\}&\cup\\\
\\{(c,\mathrm{tg},\mathrm{hl},h,D,d),\mathrm{tg},(h,\mathrm{tg},\mathrm{hl},h,D\cup\\{h\\},h)\leavevmode\nobreak\
|\leavevmode\nobreak\ c=h\\}&\cup\\\
\\{(c,\mathrm{tg},\mathrm{hl},h,D,d),\mathrm{hl},(c,\mathrm{tg},\mathrm{hl},{\mbox{{${h}$}{{\vbox{\offinterlineskip\hbox{\hskip
3.87495pt\scriptsize{${C^{*}}$}}\vskip-2.58334pt\hbox{\normalsize{${+}$}}}}}{${1}$}}},D,d)\leavevmode\nobreak\
|\leavevmode\nobreak\ h\neq c^{0^{\star}}\\}&\cup\\\
\left\\{(c,\mathrm{tg},\mathrm{hl},c^{0^{\star}},D,d),\mathrm{hl},(c,{\mbox{{${\mathrm{tg}}$}{{\vbox{\offinterlineskip\hbox{\hskip
3.87495pt\scriptsize{${C}$}}\vskip-2.58334pt\hbox{\normalsize{${+}$}}}}}{${1}$}}},{\mbox{{${\mathrm{hl}}$}{{\vbox{\offinterlineskip\hbox{\hskip
3.87495pt\scriptsize{${C}$}}\vskip-2.58334pt\hbox{\normalsize{${+}$}}}}}{${1}$}}},c^{1^{\star}},\emptyset,c)\left|\leavevmode\nobreak\
c\notin\left\\{\begin{array}[]{c}{\mbox{{${\mathrm{tg}}$}{{\vbox{\offinterlineskip\hbox{\hskip
3.87495pt\scriptsize{${C}$}}\vskip-2.58334pt\hbox{\normalsize{${+}$}}}}}{${1}$}}},\\\
{\mbox{{${\mathrm{hl}}$}{{\vbox{\offinterlineskip\hbox{\hskip
3.87495pt\scriptsize{${C}$}}\vskip-2.58334pt\hbox{\normalsize{${+}$}}}}}{${1}$}}}\end{array}\right\\}\right.\right\\}&\cup\\\
\\{(c,\mathrm{tg},\mathrm{hl},c^{0^{\star}},D,d),\mathrm{hl},(\mathrm{tg},{\mbox{{${\mathrm{tg}}$}{{\vbox{\offinterlineskip\hbox{\hskip
3.87495pt\scriptsize{${C}$}}\vskip-2.58334pt\hbox{\normalsize{${+}$}}}}}{${1}$}}},{\mbox{{${\mathrm{hl}}$}{{\vbox{\offinterlineskip\hbox{\hskip
3.87495pt\scriptsize{${C}$}}\vskip-2.58334pt\hbox{\normalsize{${+}$}}}}}{${1}$}}},c^{1^{\star}},\emptyset,\mathrm{tg})\leavevmode\nobreak\
|\leavevmode\nobreak\
c={\mbox{{${\mathrm{tg}}$}{{\vbox{\offinterlineskip\hbox{\hskip
3.87495pt\scriptsize{${C}$}}\vskip-2.58334pt\hbox{\normalsize{${+}$}}}}}{${1}$}}}\\}&\cup\\\
\\{(c,\mathrm{tg},\mathrm{hl},c^{0^{\star}},D,d),\mathrm{hl},(\mathrm{hl},{\mbox{{${\mathrm{tg}}$}{{\vbox{\offinterlineskip\hbox{\hskip
3.87495pt\scriptsize{${C}$}}\vskip-2.58334pt\hbox{\normalsize{${+}$}}}}}{${1}$}}},{\mbox{{${\mathrm{hl}}$}{{\vbox{\offinterlineskip\hbox{\hskip
3.87495pt\scriptsize{${C}$}}\vskip-2.58334pt\hbox{\normalsize{${+}$}}}}}{${1}$}}},c^{1^{\star}},\emptyset,\mathrm{hl})\leavevmode\nobreak\
|\leavevmode\nobreak\
c={\mbox{{${\mathrm{hl}}$}{{\vbox{\offinterlineskip\hbox{\hskip
3.87495pt\scriptsize{${C}$}}\vskip-2.58334pt\hbox{\normalsize{${+}$}}}}}{${1}$}}}\\}\end{array}$
Figure 4: The transitions comprising $\Delta_{p}$ of the two switching
channels case.

Without going into details, one can modify the proof of Lemma 4.1 to be
adapted to this construction: use enough $\mathrm{hl}$ communications until
$\mathrm{hl}$ is a channel that process $p$ does not listen to, which means
that $p$ is not able to distinguish between all possible dependent sets from
this point onwards and therefore $p$ cannot block communications on a non-
switching channel.

We note that it is possible to modify the last construction so that only the
$\mathrm{hl}$ channel is dynamic and the $\mathrm{tg}$ channel is fixed. This,
however, complicates the notations further.

##  5 Conclusion

We study the addition of reconfiguration of communication to Zielonka
automata. We show that in terms of expressiveness, the addition does not
change the power of the model: every language recognized distributively by
automata with reconfigurable communication can be recognized essentially by
the same automata with fixed communication. The same is (obviously) true in
the other direction. However, the cost of conversion is in disseminating
widely all the information and leaving it up to the agents whether to use it
or not. We also show that this total dissemination cannot be avoided. Agents
who do not get access to the full information about the computation become
irrelevant and in fact do not participate in the distributed computation.

The issues of mobile and reconfigurable communication raise a question
regarding “how much” communication is performed in a computation. Given a
language recognized by a a Zielonka automaton (distributively), the
independence relation between letters is fixed by the language. It follows
that two distributed systems in the form of Zielonka automata accepting
(distributively) the same language must have the same independence relation
between letters. However, this does not mean that they agree on the
distribution of the alphabet. In case of two different distributed alphabets,
what makes one better than the other? This question becomes even more
important with systems with reconfigurable communication interfaces.
Particularly, in channeled transition systems, the connectivity changes from
state to state, which makes comparison even harder. How does one measure (and
later reduce or minimize) the amount of communication in a system while
maintaining the same behavior? We note that for the system in Section 4, the
maximal number of connections per agent is four regardless of how many
channels are in the system. Dually, the Zielonka automaton for the same
language requires every agent that participates meaningfully in the
interaction to have number of connections equivalent to the parameter $n$. Is
less connectivity better than more connectivity?

The issues of who is connected and to with whom information is shared also
have implications for security and privacy. Reconfiguration allowed us to
share communication only with those who “need to know”. Fixed topology forced
us to disseminate information widely. If we intend to use language models and
models of concurrency in applications that involve security and privacy we
need a way to reason about dissemination of information and comparing
formalisms also based on knowledge and information.

Acknowledgments

We are grateful to Y. Abd Alrahman and L. Di Stefano for fruitful discussions
and suggestions.

## References

  * [1] Yehia Abd Alrahman, Rocco De Nicola, and Michele Loreti.  A calculus for collective-adaptive systems and its behavioural theory.  Inf. Comput., 268, 2019.  doi:10.1016/j.ic.2019.104457.
  * [2] Yehia Abd Alrahman and Nir Piterman.  Modelling and verification of reconfigurable multi-agent systems.  Auton. Agents Multi Agent Syst., 35(2):47, 2021.  doi:10.1007/s10458-021-09521-x.
  * [3] Marco Carbone and Sergio Maffeis.  On the expressive power of polyadic synchronisation in pi-calculus.  Nord. J. Comput., 10(2):70–98, 2003.
  * [4] Luca Cardelli and Andrew D. Gordon.  Mobile ambients.  Theor. Comput. Sci., 240(1):177–213, 2000.  doi:10.1016/S0304-3975(99)00231-5.
  * [5] Frank S. de Boer and Catuscia Palamidessi.  Embedding as a tool for language comparison.  Inf. Comput., 108(1):128–157, 1994.  doi:10.1006/inco.1994.1004.
  * [6] Daniele Gorla.  Towards a unified approach to encodability and separation results for process calculi.  Inf. Comput., 208(9):1031–1053, 2010.  doi:10.1016/j.ic.2010.05.002.
  * [7] Mathias John, Cédric Lhoussaine, Joachim Niehren, and Adelinde M. Uhrmacher.  The attributed pi calculus.  In 6th International Conference on Computational Methods in Systems Biology, volume 5307 of Lecture Notes in Computer Science, pages 83–102. Springer, 2008.  doi:10.1007/978-3-540-88562-7\\_10.
  * [8] Radu Mateescu and Gwen Salaün.  Translating pi-calculus into LOTOS NT.  In 8th International Conference on Integrated Formal Methods, volume 6396 of Lecture Notes in Computer Science, pages 229–244. Springer, 2010.  doi:10.1007/978-3-642-16265-7\\_17.
  * [9] Robin Milner, Joachim Parrow, and David Walker.  A calculus of mobile processes, I.  Inf. Comput., 100(1):1–40, 1992.  doi:10.1016/0890-5401(92)90008-4.
  * [10] Robin Milner, Joachim Parrow, and David Walker.  A calculus of mobile processes, II.  Inf. Comput., 100(1):41–77, 1992.  doi:10.1016/0890-5401(92)90009-5.
  * [11] Rocco De Nicola, Michele Loreti, Rosario Pugliese, and Francesco Tiezzi.  A formal approach to autonomic systems programming: The SCEL language.  ACM Trans. Auton. Adapt. Syst., 9(2):7:1–7:29, 2014.  doi:10.1145/2619998.
  * [12] Rob van Glabbeek.  Comparing the expressiveness of the $\pi$-calculus and CCS.  In Ilya Sergey, editor, Programming Languages and Systems - 31st European Symposium on Programming, ESOP 2022, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2022, Munich, Germany, April 2-7, 2022, Proceedings, volume 13240 of Lecture Notes in Computer Science, pages 548–574. Springer, 2022.  doi:10.1007/978-3-030-99336-8\\_20.
  * [13] Wieslaw Zielonka.  Notes on finite asynchronous automata.  RAIRO Theor. Informatics Appl., 21(2):99–135, 1987.  doi:10.1051/ita/1987210200991.