The genus of regular languages and directed graph emulators

DOI10.1016/J.TCS.2024.114579MaRDI QIDQ6495791zbMATH OpenFDO

Authors Guillaume Bonfante, Florian Deloup

Publication date 2 May 2024

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.TCS.2024.114579

zbMATH Keywords

automatadirected graph coversdirected graph emulatorsregular languagessurface genus

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• Bisimulation from open maps
• Categorical semantics of linear logic
• Decidability of regular language genus computation
• Elements of automata theory. Translated from the French by Reuben Thomas
• Finite planar emulators for \(K_{4,5} - 4K_{2}\) and \(K_{1,2,2,2}\) and Fellows' conjecture
• Forbidden directed minors and Kelly-width
• Graph minors. XX: Wagner's conjecture
• How not to characterize planar-emulable graphs
• scientific article; zbMATH DE number 46168 (Why is no real title available?)
• scientific article; zbMATH DE number 3497806 (Why is no real title available?)
• scientific article; zbMATH DE number 7199591 (Why is no real title available?)
• Inherently nonplanar automata
• K4,4 ?e has no finite planar cover
• Linear logic
• Logical structures and genus of proofs
• Nonconstructive tools for proving polynomial-time decidability
• The genus of regular languages

This page was built for publication: The genus of regular languages and directed graph emulators

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6495791)