Diekert, Volker and Martin, Florent and Senizergues, Geraud and Silva, Pedro V. (2017) Equations Over Free Inverse Monoids with Idempotent Variables. THEORY OF COMPUTING SYSTEMS, 61 (2). pp. 494-520. ISSN 1432-4350, 1433-0490
Full text not available from this repository. (Request a copy)Abstract
We introduce the notion of idempotent variables for studying equations in inverse monoids. It is proved that it is decidable in singly exponential time (DEX-PTIME) whether a system of equations in idempotent variables over a free inverse monoid has a solution. Moreover the problem becomes hard for DEXPTIME, as soon as the quotient group of the free inverse monoid has rank at least two. The upper bound is proved by a direct reduction to solve language equations with one-sided concatenation and a known complexity result by Baader and Narendran (J. Symb. Comput. 31, 277-305 2001). For the lower bound we show hardness for a restricted class of language equations. Decidability for systems of typed equations over a free inverse monoid with one irreducible variable and at least one unbalanced equation is proved with the same complexity upper-bound. Our results improve known complexity bounds by Deis et al. (IJAC 17, 761-795 2007). Our results also apply to larger families of equations where no decidability has been previously known. The lower bound confirms a conjecture made in the conference version of this paper.
| Item Type: | Article |
|---|---|
| Uncontrolled Keywords: | SEMIGROUPS; Free inverse monoid; Equation; Language equation; Idempotent variable; One-variable equation |
| Subjects: | 500 Science > 510 Mathematics |
| Divisions: | Mathematics |
| Depositing User: | Dr. Gernot Deinzer |
| Date Deposited: | 14 Dec 2018 13:16 |
| Last Modified: | 19 Feb 2019 07:10 |
| URI: | https://pred.uni-regensburg.de/id/eprint/1502 |
Actions (login required)
 |
View Item |
