Abstract | ||
---|---|---|
We present an algebraic characterization of the standard commutative relaxation of the word problem in terms of a polynomial equality. We then consider a variant of the commutative word problem, referred to as the "Zero-to-All reachability" problem. We show that this problem is equivalent to a finite number of commutative word problems, and we use this insight to derive necessary conditions for Zero-to-All reachability. We conclude with a set of illustrative examples. |
Year | DOI | Venue |
---|---|---|
2007 | 10.1109/CDC.2007.4435013 | PROCEEDINGS OF THE 46TH IEEE CONFERENCE ON DECISION AND CONTROL, VOLS 1-14 |
Keywords | Field | DocType |
polynomials,word problem,formal languages | Discrete mathematics,Algebraic number,Formal language,Finite set,Polynomial,Algebra,Commutative property,Relaxation theory,Word problem (mathematics education),Reachability,Mathematics | Conference |
ISSN | Citations | PageRank |
0743-1546 | 0 | 0.34 |
References | Authors | |
2 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Danielle C. Tarraf | 1 | 177 | 19.65 |
Pablo A. Parrilo | 2 | 3455 | 229.27 |