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 Ξ be a finite set of unknowns. We consider the satisfiability problem for multilinear equations over S, i.e. equations w_L ≡ w_R with w_L,w_R ∈ (X ∪ X^{−1} ∪ Ξ ∪ Ξ^{−1})^+ such that each x ∈ Ξ labels at most one edge in the Schutzenberger automaton of either w_L or w_R relative to the presentation <X ∪Ξ|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 ∪ X^{−1})^+ relative to the presentation <X|R> is context-free.

Multilinear equations in amalgams of finite inverse semigroups

CHERUBINI, ALESSANDRA;NUCCIO, CLAUDIA;RODARO, EMANUELE
2011

Abstract

Let S = S_1 ∗_U S_2 = Inv be the free amalgamated product of the finite inverse semigroups S_1 , S_2 and let Ξ be a finite set of unknowns. We consider the satisfiability problem for multilinear equations over S, i.e. equations w_L ≡ w_R with w_L,w_R ∈ (X ∪ X^{−1} ∪ Ξ ∪ Ξ^{−1})^+ such that each x ∈ Ξ labels at most one edge in the Schutzenberger automaton of either w_L or w_R relative to the presentation . 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 ∪ X^{−1})^+ relative to the presentation is context-free.
File in questo prodotto:
File Dimensione Formato  
Multilinear.pdf

Accesso riservato

Descrizione: Articolo principale
: Publisher’s version
Dimensione 418.81 kB
Formato Adobe PDF
418.81 kB Adobe PDF   Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11311/573813
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 7
  • ???jsp.display-item.citation.isi??? 6
social impact