<!DOCTYPE html>
<html>
<head>
<title>Set Theory and Analysis</title>
</head>
<body>
<p>
Tuesday, 5 May 2026 - 10:00 to 11:30 <br />
Place: IM, konÃrna
</p>
<p>
Speaker: Yvo Ad Meeres, University of Bremen<br />
Title: Hidden Graphs: Low-Complexity Properties of Graph Sets
</p>
<p class="ql-ed">
Abstract <br />
<p>The class of regular languages resides at the lowest level of the Chomsky hierarchy of string languages. This robust class exhibits favorable properties like low complexity for standard decision problems such as membership. In contrast, regular languages of directed acyclic graphs (DAGs), as defined in the literature, are strictly more expressive, which leads to significantly higher complexity for these problems. In particular, the membership problem turns out to be NP-complete. An alternative definition of regularity enables the transfer of techniques from string languages to DAG languages.</p><p>However, the two presented equivalent computational models for DAGs, the automaton model and the grammar model, are not only useful for graph processing. Surprisingly, computational models for DAGs provide an elegant mechanism for lifting strings from one to two dimensions. Picture languages are sets of finite two-dimensional strings. A wide variety of computational models for pictures exist in the literature of automata and formal language theory. By encoding pictures, thus two-dimensional strings, as vertex-labeled directed acyclic graphs (DAGs) and processing them with DAG automata and, equivalently, DAG grammars, a single computational model suffices to simulate several established picture language formalisms. Under this approach of showing its hidden graph structure, each computational model corresponds merely to a specific encoding of a picture into a DAG. DAG automata can simulate several well-known picture language models: returning finite automata (RFA), boustrophedon finite automata (BFA), two-dimensional right-linear grammars (2RLG), tiling systems (TS), tiling automata (TA), and two-dimensional on-line tessellation automata (2OTA), which are restricted versions of cellular automata.</p>
</p>
<p>
For more information see the seminar web page at <br />
https://www.math.cas.cz/index.php/events/seminar/6
</p>
<p>
Set Theory and Analysis mailing list <br />
settfa@math.cas.cz <br />
https://list.math.cas.cz/listinfo/settfa@math.cas.cz
</p>
</body>
</html>