Title :
Solving commutative relaxations of word problems
Author :
Tarraf, Danielle C. ; Parrilo, Pablo A.
Author_Institution :
Caltech, Pasadena
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.
Keywords :
formal languages; polynomials; reachability analysis; relaxation theory; algebraic characterization; commutative relaxations; commutative word problem; polynomial equality; zero-to-all reachability problem; Application software; Biochemical analysis; Computer science; Control systems; Decision feedback equalizers; Multiagent systems; Polynomials; Production systems; Sequences; USA Councils;
Conference_Titel :
Decision and Control, 2007 46th IEEE Conference on
Conference_Location :
New Orleans, LA
Print_ISBN :
978-1-4244-1497-0
Electronic_ISBN :
0191-2216
DOI :
10.1109/CDC.2007.4435013