Go to content
UR Home

Equations Over Free Inverse Monoids with Idempotent Variables

Diekert, Volker, Martin, Florent, Sénizergues, Géraud and Silva, Pedro V. (2017) Equations Over Free Inverse Monoids with Idempotent Variables. Theory of Computing Systems 61 (2), pp. 494-520.

Full text not available from this repository.

at publisher (via DOI)

Other URL: http://doi.org/10.1007/s00224-016-9693-1


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 ...

plus


Export bibliographical data



Item type:Article
Date:2017
Institutions:Mathematics
Identification Number:
ValueType
10.1007/s00224-016-9693-1DOI
Keywords:SEMIGROUPS; Free inverse monoid; Equation; Language equation; Idempotent variable; One-variable equation
Dewey Decimal Classification:500 Science > 510 Mathematics
Status:Published
Refereed:Yes, this version has been refereed
Created at the University of Regensburg:Yes
Item ID:39332
Owner only: item control page
  1. Homepage UR

University Library

Publication Server

Contact:

Publishing: oa@ur.de

Dissertations: dissertationen@ur.de

Research data: daten@ur.de

Contact persons