Finite graph automata for linear and boundary graph languages

DOI10.1016/j.tcs.2004.09.040zbMath1070.68064OpenAlexW2082153115MaRDI QIDQ1770387

Konstantin Skodinis, Franz-Josef Brandenburg

Publication date: 6 April 2005

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2004.09.040

zbMATH Keywords

Graph grammarsGraph searchingAlternating graph automataFinite graph automataNode labelled graphs

Mathematics Subject Classification ID

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

Related Items (3)

Reachability in Graph Transformation Systems and Slice Languages ⋮ Grammatical inference of directed acyclic graph languages with polynomial time complexity ⋮ Causality in Bounded Petri Nets is MSO Definable

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Time-space tradeoffs for undirected graph traversal by graph automata
• Boundary graph grammars with dynamic edge relabeling
• A comparison of boundary graph grammars and context-free hypergraph grammars
• Interval graphs and searching
• Restrictions on NLC graph grammars
• Traces, dependency graphs and DNLC grammars
• Graph theoretic closure properties of the family of boundary NLC graph languages
• An axiomatic definition of context-free rewriting and its application to NLC graph grammars
• Apex graph grammars and attribute grammars
• Tree-size bounded alternation
• On the structure of node-label-controlled graph languages
• Restrictions, extensions, and variations of NLC grammars
• Decision problems for node label controlled graph grammars
• Graph grammars with neighbourhood-controlled embedding
• Symmetric space-bounded computation
• Algorithms for graph problems on BNLC structured garphs
• The vertex separation number of a graph equals its path-width
• Formal languages of labelled graphs
• Monadic second-order definable graph transductions: a survey
• The vertex separation and search number of a graph
• Context-free graph languages of bounded degree are generated by apex graph grammars
• Recognition of graphs by automata
• The bounded degree problem for eNCE graph grammars
• Searching and pebbling
• Linear graph grammars: Power and complexity
• Emptiness problems of eNCE graph languages
• Handle-rewriting hypergraph grammars
• Complexity of boundary graph languages
• Boundary NLC graph grammars—Basic definitions, normal forms, and complexity
• The complexity of searching a graph
• Efficient Solution of Connectivity Problems on Hierarchically Defined Graphs
• Cellular graph automata. I. basic concepts, graph property measurement, closure properties
• Cellular graph automata. II. graph and subgraph isomorphism, graph structure recognition
• Space Lower Bounds for Maze Threadability on Restricted Machines
• Alternation
• Monotonicity in graph searching
• Handbook of Graph Grammars and Computing by Graph Transformation
• Graph automata for linear graph languages
• Recontamination does not help to search a graph

This page was built for publication: Finite graph automata for linear and boundary graph languages