On Languages Describing Large Graph Classes
2026-04-21 • Formal Languages and Automata Theory
Formal Languages and Automata Theory
AI summaryⓘ
The authors introduce a new way to describe groups of graphs using patterns from formal languages. Unlike earlier studies that represented graphs as single words, they use sets of binary words to define connections between nodes. They specifically explore well-known language types like palindromes and Dyck words to see how these can represent all graphs or specific types of graphs. Their work links graph theory and language theory in a novel way.
graph classesformal languagesbinary languagespalindromesLyndon wordsDyck wordscopy-wordsgraph representationgraph theoryformal language theory
Authors
Henning Fernau, Pamela Fleischmann, Kevin Mann, Silas Cato Sacher
Abstract
In this work, we introduce a new notion for representing graph classes with formal languages. In contrast to the seminal work by Kitaev and Pyatkin to represent graphs by words, we use formal binary languages in order to have a set of patterns (given by the languages' words) defining the edges in the graph. In particular, we investigate famous languages like the palindromes, copy-words, Lyndon words, and Dyck words to represent all graphs or specific graph classes by restricting these languages.