Graph automata for linear graph languages

DOI10.1007/3-540-61228-9_97MaRDI QIDQ4645286zbMATH OpenOpenAlexFDO

Authors Konstantin Skodinis, Franz J. Brandenburg

Publication date 10 January 2019

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-61228-9_97

zbMATH Keywords

finite state automatongraph grammarinput graphnode labelterminal node

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42) Formal languages and automata (68Q45)

Recommendations

• Finite graph automata for linear and boundary graph languages
• Graph automata
• scientific article; zbMATH DE number 7604432
• scientific article; zbMATH DE number 2031101
• Linear graph grammars: Power and complexity
• scientific article; zbMATH DE number 2016084
• scientific article; zbMATH DE number 3858446
• Graph adjacency matrix automata
• scientific article; zbMATH DE number 1759440
• scientific article; zbMATH DE number 139799

Cites work

• Boundary NLC graph grammars—Basic definitions, normal forms, and complexity
• Cellular graph automata. I. basic concepts, graph property measurement, closure properties
• Cellular graph automata. II. graph and subgraph isomorphism, graph structure recognition
• Graph grammars and their application to computer science. 4th international workshop, Bremen, Germany, March 5-9, 1990. Proceedings
• scientific article; zbMATH DE number 3854429 (Why is no real title available?)
• scientific article; zbMATH DE number 3819112 (Why is no real title available?)
• scientific article; zbMATH DE number 4049101 (Why is no real title available?)
• scientific article; zbMATH DE number 17539 (Why is no real title available?)
• scientific article; zbMATH DE number 1142315 (Why is no real title available?)
• scientific article; zbMATH DE number 3410623 (Why is no real title available?)
• Linear graph grammars: Power and complexity
• Monotonicity in graph searching
• Recognition of graphs by automata
• Recontamination does not help to search a graph
• The bounded degree problem for NLC grammars is decidable
• The complexity of searching a graph

Cited in

(7)

• Finite graph automata for linear and boundary graph languages
• Linear graph grammars: Power and complexity
• A simple extension to finite tree automata for defining sets of labeled, connected graphs
• Graph Automata: The Algebraic Properties of Abelian Relational Graphoids
• scientific article; zbMATH DE number 3858446 (Why is no real title available?)
• scientific article; zbMATH DE number 1839464 (Why is no real title available?)
• scientific article; zbMATH DE number 7604432 (Why is no real title available?)

This page was built for publication: Graph automata for linear graph languages

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