Name
Abstract | ||
|---|---|---|
Let S = S-1 *(U) S-2 = Inv < X; R > be the free amalgamated product of the finite inverse semigroups S-1, S-2 and let Xi be a finite set of unknowns. We consider the satisfiability problem for multilinear equations over S, i.e. equations w(L) equivalent to w(R) with w(L), w(R) is an element of (X boolean OR X-1 boolean OR Xi boolean OR Xi(-1))(+) such that each x is an element of Xi labels at most one edge in the Schutzenberger automaton of either wL or wR relative to the presentation < X boolean OR Xi vertical bar R >. We prove that the satisfiability problem for such equations is decidable using a normal form of the words w(L), w(R) and the fact that the language recognized by the Schutzenberger automaton of any word in (X boolean OR X-1)(+) relative to the presentation < X vertical bar R > is context-free. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1142/S0218196711006078 | INTERNATIONAL JOURNAL OF ALGEBRA AND COMPUTATION |
Keywords | Field | DocType |
Inverse semigroups, inverse automata, equations in inverse semigroups | Discrete mathematics,Inverse,Finite set,Algebra,Boolean satisfiability problem,Automaton,Decidability,Multilinear map,Mathematics | Journal |
Volume | Issue | ISSN |
21 | 1-2 | 0218-1967 |
Citations | PageRank | References |
0 | 0.34 | 2 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Alessandra Cherubini | 1 | 171 | 22.16 |
| C. Nuccio | 2 | 0 | 0.34 |
| Emanuele Rodaro | 3 | 55 | 15.63 |