<figure><img src="image_1.png" /></figure>

HAL
open science

Topics in Theoretical Computer Science

Luis Barbosa, Mohammad Ali Abam

► To cite this version:

Luis Barbosa, Mohammad Ali Abam. Topics in Theoretical Computer Science: Third IFIP WG 1.8 International Conference, TTCS 2020, Tehran, Iran, July 1–2, 2020, Proceedings. Springer International Publishing, LNCS-12281, 2020, Lecture Notes in Computer Science, 978-3-030-57851-0. 10.1007/978-3-030-57852-7 . hal-03165376

HAL Id: hal-03165376

https://inria.hal.science/hal-03165376

Submitted on 10 Mar 2021

**HAL** is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Founding Editors

Gerhard Goos

Karlsruhe Institute of Technology, Karlsruhe, Germany

Juris Hartmanis

Cornell University, Ithaca, NY, USA

Editorial Board Members

Elisa Bertino

Purdue University, West Lafayette, IN, USA

Wen Gao

Peking University, Beijing, China

Bernhard Steffen

TU Dortmund University, Dortmund, Germany

Gerhard Woeginger

RWTH Aachen, Aachen, Germany

Moti Yung

Columbia University, New York, NY, USA
More information about this series at http://www.springer.com/series/7407
Luís S. Barbosa · Mohammad Ali Abam (Eds.)

Topics in Theoretical
Computer Science

Third IFIP WG 1.8 International Conference, TTCS 2020
Tehran, Iran, July 1–2, 2020
Proceedings

<figure><img src="image_3.png" /></figure>

Springer
Editors

Luís S. Barbosa

Universidade do Minho
Braga, Portugal

Mohammad Ali Abam

Sharif University of Technology
Tehran, Iran

ISSN 0302-9743

ISSN 1611-3349 (electronic)

Lecture Notes in Computer Science

ISBN 978-3-030-57851-0

ISBN 978-3-030-57852-7 (eBook)

https://doi.org/10.1007/978-3-030-57852-7

LNCS Sublibrary: SL1 – Theoretical Computer Science and General Issues

© IFIP International Federation for Information Processing 2020

This work is subject to copyright. All rights are reserved by the Publisher, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation, broadcasting, reproduction on microfilms or in any other physical way, and transmission or information storage and retrieval, electronic adaptation, computer software, or by similar or dissimilar methodology now known or hereafter developed.

The use of general descriptive names, registered names, trademarks, service marks, etc. in this publication does not imply, even in the absence of a specific statement, that such names are exempt from the relevant protective laws and regulations and therefore free for general use.

The publisher, the authors and the editors are safe to assume that the advice and information in this book are believed to be true and accurate at the date of publication. Neither the publisher nor the authors or the editors give a warranty, expressed or implied, with respect to the material contained herein or for any errors or omissions that may have been made. The publisher remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

This Springer imprint is published by the registered company Springer Nature Switzerland AG
The registered company address is: Gewerbestrasse 11, 6330 Cham, Switzerland
# Preface

We are honored to bring you this collection of the revised selected papers from the third IFIP WG 1.8 International Conference on Topics in Theoretical Computer Science (TTCS 2020), which was held at the School of Computer Science, Institute for Research in Fundamental Sciences (IPM), Tehran, Iran, July 1–2, 2020.

TTCS is a bi-annual conference series, intending to serve as a forum for novel and high-quality research in all areas of Theoretical Computer Science. Two previous editions were held in 2015 and 2017, with proceedings also published by Springer in the *Lecture Notes in Computer Science* series, respectively as volumes 9541 and 10608. As before, the 2020 conference was held in cooperation with IFIP WG 1.8, on Foundations of Concurrency, and the European Association for Theoretical Computer Science.

TTCS 2020 received 24 submissions, which were carefully reviewed by the members of an International Program Committee comprising 45 leading scientists. At least three review reports were provided for each paper. After a participated final discussion inside the Program Committee eight papers were accepted, fixing the acceptance rate of the conference at approximately 34%.

Besides paper presentations, the program included two invited talks by the following world-renowned computer scientists:

- Filippo Bonchi, University of Pisa, Italy, on “Interacting Hopf Algebras: the theory of linear systems”

- Mohammad Taghi Hajiaghayi, University of Maryland, College Park, USA, on “Massively Parallel Algorithms and Applications for Maximal Matching and Edit Distance”

We would like to thank authors and invited speakers who contributed to the success of TTCS 2020. We are also grateful to all Program Committee members for their professional and hard work in providing expert review reports and thorough discussions leading to a very interesting and strong program. Last but not least, our gratitude extends to IPM for generously supporting the conference.

Due to the COVID-19 pandemic, TTCS 2020 was forced to run virtually, with live streaming of all talks and both synchronous and asynchronous interaction with participants. We acknowledge the excellent facilities provided by Sharif University of Technology, Iran, to hold the conference online.

July 2020

Luís S. Barbosa
Mohammad Ali Abam
# Organization

## Program Committee Chairs

Mohammad Ali Abam

Luís Soares Barbosa

Sharif University of Technology, Iran

Universidade do Minho, Portugal

## Steering Committee

Farhad Arbab (Chair)

Anuj Dawar

Abbas Edalat

Michael Fellows

Wan Fokkink

Hamid Sarbazi-azad

CWI Amsterdam and Leiden University,
The Netherlands

University of Cambridge, UK

Imperial College, UK

University of Bergen, Norway

Vrije Universiteit Amsterdam, The Netherlands

IPM and Sharif University, Iran

## Program Committee

### Track A: Algorithms and Complexity

Mohammad Ali Abam

Sepehr Assadi

Mohammad Hossein Bateni

Salman Abolfath Beigy

Hossein Esfandiari

Omid Etesami

Marc van Kreveld

Mohammad Mahdian

Mohammad MahmMoody

Vahab Mirrokni

Gunter Rote

Mohammadreza
Salavatipour

Masoud Seddighin

Saeed Seddighin

Michiel Smid

Hamid Zarrabi-Zadeh

Sharif University of Technology, Iran

Rutgers University, USA

Google Research, USA

IPM, Iran

Harvard University, USA

IPM, Iran

Utrecht University, The Netherlands

Google Research, USA

University of Virginia, USA

Google Research, USA

FU Berlin, Germany

University of Alberta, Canada

IPM, Iran

Harvard University, USA

Carleton University, Canada

Sharif University of Technology, Iran

### Track B: Logic, Semantics, and Programming Theory

Farhad Arbab

Kyungmin Bae

CWI, The Netherlands

Pohang University Science and Technology,
South Korea
<table><tr><td>Christel Baier</td><td>Technische Universität Dresden, Germany</td></tr><tr><td>Luis Soares Barbosa</td><td>University of Minho, Portugal</td></tr><tr><td>Mário Benevides</td><td>Universidade Federal do Rio de Janeiro, Brazil</td></tr><tr><td>Simon Bliudze</td><td>Inria Lille, France</td></tr><tr><td>Filippo Bonchi</td><td>University of Pisa, Italy</td></tr><tr><td>Marcello Bonsangue</td><td>Leiden University, The Netherlands</td></tr><tr><td>Flavio Corradini</td><td>University of Camerino, Italy</td></tr><tr><td>Fredrik Dahlqvist</td><td>University College London, UK</td></tr><tr><td>Sergey Goncharov</td><td>FAU Erlangen-Nürnberg, Germany</td></tr><tr><td>Hossein Hojjat</td><td>Rochester Institute of Technology, USA</td></tr><tr><td>Mohammad Izadi</td><td>Sharif University of Technology, Iran</td></tr><tr><td>Sung-Shik Jongmans</td><td>Open University, The Netherlands</td></tr><tr><td>Alexander Knapp</td><td>University of Augsburg, Germany</td></tr><tr><td>Jan Kretinsky</td><td>Munich University of Technology, Germany</td></tr><tr><td>Alexandre Madeira</td><td>University of Aveiro, Portugal</td></tr><tr><td>Stefan Mitsch</td><td>Carnegie Mellon University, USA</td></tr><tr><td>Mohammad Reza Mousavi</td><td>University of Leicester, UK</td></tr><tr><td>Renato Neves</td><td>INESC TEC, Portugal</td></tr><tr><td>Peter Ölveczky</td><td>University of Oslo, Norway</td></tr><tr><td>Prakash Panangaden</td><td>McGill University, Canada</td></tr><tr><td>Elaine Pimentel</td><td>Universidade Federal do Rio Grande do Norte, Brazil</td></tr><tr><td>Subodh Sharma</td><td>IIT Delhi, India</td></tr><tr><td>Pawel Sobocinski</td><td>Taltech, Estonia</td></tr><tr><td>Ana Sokolova</td><td>University of Salzburg, Austria</td></tr><tr><td>Carolyn Talcott</td><td>Stanford University, USA</td></tr><tr><td>Benoit Valiron</td><td>LRI, France</td></tr><tr><td>Naijun Zhan</td><td>Chinese Academy of Science, China</td></tr></table>

## Additional Reviewers

<table><tr><td>Mohammad Reza Bahrami</td><td>Shahin Kamali</td></tr><tr><td>Mohammad Sadegh Borouny</td><td>Eduard Kamburjan</td></tr><tr><td>Guillermina Cledou</td><td>Mehran Khodabandeh</td></tr><tr><td>Daniel Figueiredo</td><td>Mohamad Latifian</td></tr><tr><td>Ehsan Emamjomeh-Zadeh</td><td>Dave Parker</td></tr><tr><td>Claudio Gallicchio</td><td>Alireza Rezaei</td></tr><tr><td>Arnd Hartmanns</td><td>Mingji Xia</td></tr></table>
# Contents

<table><tr><td>Dirac-Based Reduction Techniques for Quantitative Analysis of Discrete-Time Markov Models</td><td>1</td></tr><tr><td>Mohammadsadegh Mohagheghi and Behrang Chaboki</td><td></td></tr><tr><td>Combining Machine and Automata Learning for Network Traffic Classification</td><td>17</td></tr><tr><td>Zeynab Sabahi-Kaviani, Fatemeh Ghassemi, and Zahra Alimadadi</td><td></td></tr><tr><td>On the Complexity of the Upper r-Tolerant Edge Cover Problem</td><td>32</td></tr><tr><td>Ararat Harutyunyan, Mehdi Khosravian Ghadikolaei, Nikolaos Melissinos, Jérôme Monnot, and Aris Pagourtzis</td><td></td></tr><tr><td>Margin-Based Semi-supervised Learning Using Apollonius Circle</td><td>48</td></tr><tr><td>Mona Emadi and Jafar Tanha</td><td></td></tr><tr><td>Computing Boundary Cycle of a Pseudo-Triangle Polygon from Its Visibility Graph</td><td>61</td></tr><tr><td>Hossein Boomari and Soheila Farokhi</td><td></td></tr><tr><td>Improved Algorithms for Distributed Balanced Clustering</td><td>72</td></tr><tr><td>Kian Mirjalali and Hamid Zarrabi-Zadeh</td><td></td></tr><tr><td>Finite Interval-Time Transition System for Real-Time Actors</td><td>85</td></tr><tr><td>Shaghayegh Tavassoli, Ramtin Khosravi, and Ehsan Khamespanah</td><td></td></tr><tr><td>Path Planning with Objectives Minimum Length and Maximum Clearance</td><td>101</td></tr><tr><td>Mansoor Davoodi, Arman Rouhani, and Maryam Sanisales</td><td></td></tr><tr><td>Author Index</td><td>117</td></tr></table>