Back to Search
Start Over
State Complexity of Boolean Operations on Graph-Walking Automata.
- Source :
-
International Journal of Foundations of Computer Science . Jul2024, p1-21. 21p. - Publication Year :
- 2024
-
Abstract
- Finite automata that traverse graphs by moving along their edges are known as graph-walking automata (GWA). This paper investigates the state complexity of Boolean operations for this model. It is proved that the union of GWA with m and n states, with m ≤ n, operating on graphs with k labels of edge end-points, is representable by a GWA with 2km + n + 1 states, and at least 2(k − 3)(m − 1) + n − 1 states are necessary in the worst case. For the intersection, the upper bound is (2k + 1)m + n and the lower bound is 2(k − 3)(m − 1) + n − 1. The upper bound for the complementation is 2kn + 1, and the lower bound is 2(k − 3)(n − 1). [ABSTRACT FROM AUTHOR]
- Subjects :
- *FINITE state machines
*GRAPH labelings
Subjects
Details
- Language :
- English
- ISSN :
- 01290541
- Database :
- Academic Search Index
- Journal :
- International Journal of Foundations of Computer Science
- Publication Type :
- Academic Journal
- Accession number :
- 178429292
- Full Text :
- https://doi.org/10.1142/s0129054124420012