Automata-based Representations for Infinite Graphs

DOI10.1051/ITA:2001122MaRDI QIDQ4331049zbMATH OpenOpenAlexFDO

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, http://www.numdam.org/item?id=ITA_2001__35_4_311_0/, https://eudml.org/doc/221962

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)

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

Cites work

• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 1222589 (Why is no real title available?)
• scientific article; zbMATH DE number 1222592 (Why is no real title available?)
• scientific article; zbMATH DE number 1512622 (Why is no real title available?)
• scientific article; zbMATH DE number 2102748 (Why is no real title available?)
• Characterization and complexity of uniformly nonprimitive labeled 2-structures
• Complement reducible graphs
• Easy problems for tree-decomposable graphs
• Finite languages for the representation of finite graphs
• Graph expressions and graph rewritings
• Graph minors. II. Algorithmic aspects of tree-width
• Multi-tape and infinite-state automata—a survey
• The Pathwidth and Treewidth of Cographs
• The Recognition of Series Parallel Digraphs
• The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
• The monadic second-order logic of graphs, II: Infinite graphs of bounded width

Cited in

(11)

• scientific article; zbMATH DE number 2087217 (Why is no real title available?)
• Graph automata: Natural expression of self-reproduction
• Representing regular languages of infinite words using mod 2 multiplicity automata
• Unary automatic graphs: an algorithmic perspective
• An internal presentation of regular graphs by prefix-recognizable graphs
• Graph representation functions computable by finite automata
• Finite languages for the representation of finite graphs
• Automata-based presentations of infinite structures
• Unary Automatic Graphs: An Algorithmic Perspective
• scientific article; zbMATH DE number 2038741 (Why is no real title available?)
• Properties of graphs specified by a regular language

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)