Properties of graphs specified by a regular language

DOI10.1007/S00236-022-00427-ZMaRDI QIDQ5918788zbMATH OpenOpenAlexWikidataFDO

Authors Volker Diekert, Henning Fernau, Petra Wolf

Publication date 30 August 2022

Published in Acta Informatica (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/s00236-022-00427-z

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Properties of graphs specified by a regular language
• Two Algorithms For Languages Recognized By Graph Algebras
• Finite languages for the representation of finite graphs
• scientific article; zbMATH DE number 3858446
• Automata-based Representations for Infinite Graphs

Cites work

• Automata equipped with auxiliary data structures and regular realizability problems
• Deciding regular intersection emptiness of complete problems for PSPACE and the polynomial hierarchy
• Detecting palindromes, patterns and borders in regular languages
• Graph minors. III. Planar tree-width
• Graph structure and monadic second-order logic. A language-theoretic approach
• Graph theory
• Groups, the theory of ends, and context-free languages
• scientific article; zbMATH DE number 3497806 (Why is no real title available?)
• scientific article; zbMATH DE number 2104820 (Why is no real title available?)
• scientific article; zbMATH DE number 3368555 (Why is no real title available?)
• scientific article; zbMATH DE number 3057871 (Why is no real title available?)
• Nonserial dynamic programming
• On Context-Free Languages
• On finite monoids having only trivial subgroups
• On regular realizability problems for context-free languages
• On the decidability of finding a positive ILP-instance in a regular set of ILP-instances
• Properties of graphs specified by a regular language
• S-functions for graphs
• Second-Order Finite Automata
• Second-order finite automata: expressive power and simple proofs using automatic structures
• Semigroups, Presburger formulas, and languages
• Structural properties of word representable graphs
• The structure of the models of decidable monadic theories of graphs
• The word problem for the Burnside varieties
• Word problem of the Perkins semigroup via directed acyclic graphs.

Cited in

(3)

• scientific article; zbMATH DE number 5999572 (Why is no real title available?)
• Properties of graphs specified by a regular language
• On universality of regular realizability problems

Describes a project that uses

Uses Software

• TreeRePair

This page was built for publication: Properties of graphs specified by a regular language

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