DocumentCode :
2831731
Title :
Solving commutative relaxations of word problems
Author :
Tarraf, Danielle C. ; Parrilo, Pablo A.
Author_Institution :
Caltech, Pasadena
fYear :
2007
fDate :
12-14 Dec. 2007
Firstpage :
5575
Lastpage :
5580
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;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Decision and Control, 2007 46th IEEE Conference on
Conference_Location :
New Orleans, LA
ISSN :
0191-2216
Print_ISBN :
978-1-4244-1497-0
Electronic_ISBN :
0191-2216
Type :
conf
DOI :
10.1109/CDC.2007.4435013
Filename :
4435013
Link To Document :
بازگشت