23^{rd}
International Symposium on
Fundamentals of Computation Theory
September 1215, 2021, Athens, Greece (virtually)
13:3014:00  Welcome 
14:0016:30  Tutorial 
16:3017:00  Break 
17:0018:30  Young Researchers' Forum (informal meeting) 
18:3019:30  Social Meeting 
11:3012:00  Welcome  Opening 
12:0013:00  Plenary Talk I (chair: Aris Pagourtzis)
Nobuko Yoshida 
13:0013:15  Break 
13:1514:15  Session 1 [Logic, Languages, Complexity] (chair: Nikos Tzevelekos)
Bharat Adsul, Saptarshi Sarkar and A V Sreejith
Abstract:
We contribute to the refined understanding of the languagelogicalgebra
interplay in the context of firstorder properties of countable
words. We establish decidable algebraic characterizations of FO[1] 
one variable fragment of FO as well as boolean closure of existential
fragment of FO via a strengthening of Simon's theorem about piecewise
testable languages. We propose a new extension of FO which admits infinitary
quantifiers to reason about the inherent infinitary properties of countable
words. We provide very natural and hierarchical blockproduct based
characterization of the new extension. We also explicate its role
in view of other natural and classical logical systems such as WMSO and
FO[cut]  an extension of FO where quantification over Dedekindcuts is
allowed. We rule out the possibility of a finitebasis for
a blockproduct based characterization of these logical systems.
Finally, we report simple but novel algebraic characterizations of one
variable fragments of the hierarchies of the new proposed extension of FO.
Miroslav Chodil and Antonin Kucera
Abstract:
We give a sufficient condition under which every finitesatisfiable formula of a given PCTL fragment has a model with at most doubly exponential number of states (consequently, the finite satisfiability problem for the fragment is
in 2EXPSPACE). The condition is semantic and it is based on enforcing a form of ``progress'' in nonbottom SCCs contributing to the satisfaction of a given PCTL formula. We show that the condition is satisfied by PCTL fragments
beyond the reach of existing methods.
Hermann Gruber, Markus Holzer and Simon Wolfsteiner
Abstract:
Finite languages lie at the heart of literally every regular
expression. Therefore, we investigate the approximation complexity
of minimizing regular expressions without Kleene star, or,
equivalently, regular expressions describing finite languages.
On the side of approximation hardness, given such an expression of
size~$s$, we prove that it is impossible to approximate the minimum
size required by an equivalent regular expression within a factor of
$O\left(\frac{s}{(\log s)^{\delta}}\right)$ if the running time is
bounded by a quasipolynomial function depending on $\delta$, for
every $\delta>1$, unless the exponential time hypothesis (ETH)
fails. For approximation ratio $O(s^{1\delta})$, we prove an
exponentialtime lower bound depending on $\delta$, assuming ETH.
The lower bounds apply to alphabets of constant size.
On the algorithmic side, we show that the problem can be
approximated in polynomial time within $O(\frac{s\log\log s}{\log
s})$, with~$s$ being the size of the given regular expression.
For constant alphabet size, the bound improves to $O(\frac{s}{\log
s})$. Finally, we devise a familiy of superpolynomial
approximation algorithms with approximation ratios matching the
lower bounds, while the running times are just above the lower
bounds excluded by the exponential time hypothesis.

14:1514:30  Break 
14:3015:30  Session 2 [Automata and Complexity] (chair: Stefan Hoffmann)
Henning Fernau and Kshitij Gajjar
Abstract:
A graph is called a sum graph if its vertices can be labelled by distinct positive integers such that there is an edge between two vertices if and only if the sum of their labels is the label of another vertex of the graph. Most
papers on sum graphs consider combinatorial questions like the minimum number of isolated vertices that need to be added to a given graph to make it a sum graph. In this paper, we initiate the study of sum graphs from the viewpoint of
computational complexity. Note that every nvertex sum graph can be represented by a sorted list of n positive integers where edge queries can be answered in O(log n) time. Thus, limiting the size of the vertex labels upper bounds the
space complexity of storing the graph.
We show that every nvertex, medge, ddegenerate graph can be made a sum graph by adding at most m isolated vertices to it such that the size of each vertex label is at most O(n^2d). This enables us to store the graph using O(m log
n) bits of memory. For sparse graphs (graphs with O(n) edges), this matches the trivial lower bound of Omega(n log n). Since planar graphs and forests have constant degeneracy, our result implies an upper bound of O(n^2) on their
label size. The previously best known upper bound on the label size of general graphs with the minimum number of isolated vertices was O(4^n), due to Kratochvil, Miller & Nguyen. Furthermore, their proof was existential whereas our
labelling can be constructed in polynomial time.
Peter Leupold and Sebastian Maneth
Abstract:
It is well known that for a regular tree language, it is decidable whether or not it can be recognized by a deterministic topdown tree automaton (DTA). However, the computational complexity of this problem has not been studied. We
show that for a given deterministic bottomup tree automaton it can be decided in quadratic time whether or not its language can be recognized by a DTA. Since there are finite tree languages that cannot be recognized by DTAs, we also
consider finite unions of DTAs and show that also here, definability within deterministic bottomup tree automata is decidable in quadratic time.
Markus Lohrey
Abstract:
We study the computational complexity of the word problem in HNNextension of groups.
HNNextension are a fundamental construction in geometric and combinatorial group theory.
We show that the word problem for an ascending HNNextension of a group H is logspace
reducible to the socalled compressed word problem for H. The main result of the paper
shows that the word problem for an HNNextension of a hyperbolic group H, where the
associated subgroups are cyclic, can be solved in polynomial time. This result can be easily
extended to fundamental groups of graphs of groups, where all vertex nodes are hyperbolic
and all edge groups are cyclic.

15:3016:30  Long Break 
16:3017:50  Session 3 [Automata, Complexity, Formal Methods] (chair: David Richerby)
JinYi Cai, Austen Fan and Yin Liu
Abstract:
We prove a complexity dichotomy for a class of counting problems expressible as bipartite 3regular Holant problems. For every problem of the form Holant(f  =_3), where f is any integervalued ternary symmetric constraint function on
Boolean variables, we prove that it is either Ptime computable or #Phard, depending on an explicit criterion of f. The constraint function can take both positive and negative values, allowing for cancellations. In addition, we
discover a new phenomenon: there is a set F with the property that for every f in F the problem Holant(f =_3) is planar Ptime computable but #Phard in general, yet its planar tractability is by a combination of a holographic
transformation by [1 1 \\ 1 1] to FKT together with an independent global argument.
Vrunda Dave, Taylor Dohmen, Shankara Narayanan Krishna, Ashutosh Trivedi
Abstract:
Regular model checking is an exploration technique for infinite
state systems where state spaces are represented as regular languages and
transition relations are expressed using rational relations over infinite (or finite) strings. We extend the regular model checking paradigm to permit the use of more powerful transition relations: the class of regular relations, of
which the rational relations are a strict subset. We use the language of monadic secondorder logic (\mso{}) on infinite strings to specify such relations and adopt streaming string transducers (\sst{}s) as a suitable computational
model. We introduce nondeterministic \sst{}s over infinite strings (\wnsst{}s) and show that they precisely capture the relations definable in \mso{}. We further explore theoretical properties of \wnsst{}s required to effectively
carry out regular model checking. In particular, we establish that the regular type checking problem for \wnsst{}s is decidable in \pspace{}. Since the postimage of a regular language under a regular relation may not be regular (or
even contextfree), approaches that iteratively compute the image can not be effectively carried out in this setting. Instead, we utilize the fact that regular relations are closed under composition, which, together with our
decidability result, provides a foundation for regular model checking with regular relations.
S. Raja and G. V. Sumukha Bharadwaj
Abstract:
In this paper, we study the computational complexity of the commutative determinant polynomial computed by a class of setmultilinear circuits which we call regular setmultilinear circuits. Regular setmultilinear circuits are
commutative circuits with a restriction on the order in which they can compute polynomials. A regular setmultilinear circuit can be seen as the commutative analogue of the ordered circuit defined by Hrubes, Wigderson and Yehudayoff
[HWY10]. We show that if the commutative determinant polynomial has a small representation in the sum of constantly many regular setmultilinear circuits, then the commutative permanent polynomial also has a small arithmetic circuit.
Stefan Hoffmann
Abstract:
The constrained synchronization problem asks for a synchronizing word of a given input automaton contained in a a regular set of constraints. It could be viewed as a special case of synchronization of a discrete event system under
supervisory control. Here, we study the computational complexity of the constrained synchronization problem for the class of sparse regular constraint languages. We give a new characterization of sparse regular sets, which equal the
bounded regular sets and give a full classification of the computational complexity of the constrained synchronization problem for strictly bounded regular languages. In addition, we derive a polynomial time decision procedure for the
complexity of the constrained synchronization problem, given a constraint automaton recognizing a strictly bounded regular language as input. Then, we introduce strongly selfsynchronizing codes and investigate the constrained
synchronization problem for bounded languages induced by these codes. With our previous result, we deduce a full classification for these languages as well. In both cases, depending on the constraint language, our problem becomes
$NP$complete or polynomial time solvable.

17:5018:00  Break 
18:0019:00  Plenary Talk II (chair: Stathis Zachos)
Constantinos Daskalakis 
19:1520:15 
Social Programme
The Athenian Acropolis through the Ages (19:3020:15)
Abstract:
The Acropolis is one of the most famous Greek landmarks and one of the most historic locations of Athens.
It is the place where the first traces of human habitation in Athens (6 millenia ago) have been found. By Mycaenean times (13th century BCE) the small Neolithic settlement of the 3rd millenium BCE had evolved into a strong citadel. A few centuries later, in the Geometric Era, the Acropolis became a sanctuary and its transformation into a religious centre began. The first monumental temples were built in the 6th century; after the Persian Wars, the Acropolis began to gradually take the form we know today. Its masterpieces (like the Parthenon and the Propylaea) are considered the best examples of Greek architecture. The Acropolis changed through the ages, mirroring the history of Athens. During the Middle Ages, its temples were turned into churches, whereas the hill became a castle. Due to its strategic position, its monuments suffered the impact of various conflicts, until the Greek War of Independence; their marks are visible to this day. The Acropolis of Athens is the city’s symbol. It is also a place enriched by the happy convergence of art, history and mythology. Bio:
Aristotle Koskinas studied classical archaeology at the University of Ioannina, Greece. He specialized in the study of architectural terracottas (rooftiles). For several years he participated in various excavations conducted by
the Greek Ministry of Culture. He took part in the surface survey project conducted in Western Achaia by the Center for Greek and Roman Studies of the National Research Foundation, as well as in the Sicyon surface survey conducted
by the University of Thessaly. He published material from both projects.
In 2003 he graduated from the Greek School of Tourist Guides and has since been working as a guide. He specialises in organising thematic and/or educational tours for interested parties, such as universities, historic societies
etc. He has been working closely with several universities, such as the universities of Princeton, Missouri, Longwood, et.al.
He is also an accomplished narrator, and is a regular participant (by invitation of the National Archaeological Museum and the Greek Narration Festival) to participate in their yearly narration events. He lectures on Greek history and archaeology, while continuing to study and publish material from excavations of the Ministry of Culture. His other interests lay in the field of military history and conflict archaeology and he has been involved in historical reenactment events. Professional blog 