From author's presentation: In the first section are given the basic notation, the formal definition of graph automata (GA) and examples showing how different types of automata can be expressed in terms of GA. In sections 2-4 the closure properties of GA and the proofs of these properties under intersection are presented. Finally, in section 5, is proved that the emptiness problem for GA is decidable.
Recommendations
- scientific article; zbMATH DE number 3858446
- Finite automata with undirected state graphs
- Finite automata with undirected state graphs
- On congruences of automata defined by directed graphs
- scientific article; zbMATH DE number 7604432
- Automata on Directed Graphs: Edge Versus Vertex Marking
- Graph automata
- scientific article; zbMATH DE number 3882460
- Finite graph automata for linear and boundary graph languages
- Cyclic automata networks on finite graphs
Cites work
- An Algorithm for the General Petri Net Reachability Problem
- Decidability of Second-Order Theories and Automata on Infinite Trees
- Generalized finite automata theory with an application to a decision problem of second-order logic
- scientific article; zbMATH DE number 3492660 (Why is no real title available?)
- scientific article; zbMATH DE number 3254905 (Why is no real title available?)
- scientific article; zbMATH DE number 3301432 (Why is no real title available?)
- scientific article; zbMATH DE number 3339435 (Why is no real title available?)
- scientific article; zbMATH DE number 3341983 (Why is no real title available?)
- Parallel program schemata
- Testing and generating infinite sequences by a finite automaton
- Tree acceptors and some of their applications
Cited in
(22)- Construction of push-down automaton graph
- Nondeterminism versus determinism of finite automata over directed acyclic graphs
- A branching time logic with past operators
- Finite graph automata for linear and boundary graph languages
- Graph automata
- scientific article; zbMATH DE number 3858446 (Why is no real title available?)
- scientific article; zbMATH DE number 4155919 (Why is no real title available?)
- Automata on Directed Graphs: Edge Versus Vertex Marking
- scientific article; zbMATH DE number 4074547 (Why is no real title available?)
- scientific article; zbMATH DE number 3499653 (Why is no real title available?)
- A Correction and Some Comments Concerning Graph Isomorphism by Finite Automata
- Deterministic generalized automata
- Distributed graph automata
- scientific article; zbMATH DE number 2111186 (Why is no real title available?)
- scientific article; zbMATH DE number 7604432 (Why is no real title available?)
- Mathematical Foundations of Computer Science 2004
- The loops of the basis finite automaton and the connected questions
- scientific article; zbMATH DE number 4185044 (Why is no real title available?)
- Finite automata with undirected state graphs
- Finite automata with undirected state graphs
- Finite automata for efficient graph recognition
- Some machines defined by directed graphs
This page was built for publication: Finite automata on directed graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1191024)
