Automata-based Representations for Infinite Graphs

DOI10.1051/ITA:2001122zbMATH Open0997.05067OpenAlexW2067945234MaRDI QIDQ4331049FDOQ4331049

Authors: 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

Recommendations

• scientific article; zbMATH DE number 1222592
• Automata-based presentations of infinite structures
• On infinite transition graphs having a decidable monadic theory
• scientific article; zbMATH DE number 2087217
• Graph representation functions computable by finite automata

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

• Title not available (Why is that?)
• Complement reducible graphs
• Easy problems for tree-decomposable graphs
• Graph minors. II. Algorithmic aspects of tree-width
• 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
• The monadic second-order logic of graphs, II: Infinite graphs of bounded width
• Graph expressions and graph rewritings
• Characterization and complexity of uniformly nonprimitive labeled 2-structures
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Finite languages for the representation of finite graphs
• Multi-tape and infinite-state automata—a survey
• Title not available (Why is that?)

Cited In (9)

• Title not available (Why is that?)
• Representing regular languages of infinite words using mod 2 multiplicity automata
• Graph automata: Natural expression of self-reproduction
• Unary automatic graphs: an algorithmic perspective
• An internal presentation of regular graphs by prefix-recognizable graphs
• Graph representation functions computable by finite automata
• Automata-based presentations of infinite structures
• Unary Automatic Graphs: An Algorithmic Perspective
• Title not available (Why is that?)

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

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