Paper Info
Title
On the complexity of some reachability problems
Abstract
In this paper we introduce the notion of rewriting systems for sets, and consider the complexity of the reachability problems for these systems, showing that this problem is PSPACE-complete in the general case and is P-complete for particular rewriting systems. As a consequence, we show that the emptiness and finiteness problems for E0L systems are PSPACE-complete, solving in this way an open problem. Finally, we give completeness results for some decision problems concerning binary systolic tree automata.
Year
DOI
Venue
1994
10.1007/3-540-57811-0_16
CIAC
Keywords
Field
DocType
reachability problem,decision problem
Discrete mathematics,Decision problem,Combinatorics,Open problem,Computer science,Decision tree model,Reachability,PSPACE,Rewriting,Tree automaton,Time complexity
Conference
ISBN
Citations 
PageRank 
3-540-57811-0
0
0.34
References 
Authors
10
2
Name
Order
Citations
PageRank
Angelo Monti167146.93
Alessandro Roncato232020.21