Automata-based Representations for Infinite Graphs

DOI10.1051/ita:2001122zbMath0997.05067OpenAlexW2067945234MaRDI QIDQ4331049

Salvatore La Torre, Margherita Napoli

Publication date: 17 November 2002

Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL: http://www.numdam.org/item?id=ITA_2001__35_4_311_0

zbMATH Keywords

finite automataformal languagesgraph classesequational graphsrepresentation of infinite graphs

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Graph theory (including graph drawing) in computer science (68R10) Automata and formal grammars in connection with logical questions (03D05) Graph representations (geometric and intersection representations, etc.) (05C62)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Characterization and complexity of uniformly nonprimitive labeled 2-structures
• Complement reducible graphs
• Finite languages for the representation of finite graphs
• Easy problems for tree-decomposable graphs
• The monadic second-order logic of graphs, II: Infinite graphs of bounded width
• Graph minors. II. Algorithmic aspects of tree-width
• Graph expressions and graph rewritings
• The Recognition of Series Parallel Digraphs
• The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
• The Pathwidth and Treewidth of Cographs
• Multi-tape and infinite-state automata—a survey

This page was built for publication: Automata-based Representations for Infinite Graphs