A proof of Zhil'tsov's theorem on decidability of equational theory of epigroups

Epigroups are semigroups equipped with an additional unary operation called pseudoinversion. Each finite semigroup can be considered as an epigroup. We prove the following theorem announced by Zhil'tsov in 2000: the equational theory of the class of all epigroups coincides with the equational t...

Full description

Saved in:
Bibliographic Details
Published in:Discrete mathematics and theoretical computer science 2016-06, Vol.17 no. 3 (Combinatorics), p.179-202
Main Author: Mikhaylova, Inna
Format: Article
Language:English
Subjects:
[info.info-dm] computer science [cs]/discrete mathematics [cs.dm]
Combinatorics
Computer Science
decidability of equational theory
Discrete Mathematics
epigroup
finite basis proble
finite semigroup
Theorems
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
cited_by
cites
container_end_page 202
container_issue Combinatorics
container_start_page 179
container_title Discrete mathematics and theoretical computer science
container_volume 17 no. 3
creator Mikhaylova, Inna
description Epigroups are semigroups equipped with an additional unary operation called pseudoinversion. Each finite semigroup can be considered as an epigroup. We prove the following theorem announced by Zhil'tsov in 2000: the equational theory of the class of all epigroups coincides with the equational theory of the class of all finite epigroups and is decidable. We show that the theory is not finitely based but provide a transparent infinite basis for it.
doi_str_mv 10.46298/dmtcs.2155
format article
fullrecord <record><control><sourceid>proquest_doaj_</sourceid><recordid>TN_cdi_doaj_primary_oai_doaj_org_article_35f66c21cfcb487783e24f889bd0d696</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><doaj_id>oai_doaj_org_article_35f66c21cfcb487783e24f889bd0d696</doaj_id><sourcerecordid>4178420911</sourcerecordid><originalsourceid>FETCH-LOGICAL-c356t-22382a9d08be789b3b051c7769c0719427d03c2e96ecc1adb177a5f769d96dbb3</originalsourceid><addsrcrecordid>eNpVkUtLAzEYRQdRsFZX_oEBF0Vkah6T17IUtUJBF7pxEzJJpk2ZNtMkLfTfO-2IKAQSbg7ng-9m2S0E45IiwR_NOuk4RpCQs2wAMSUFBwSc_3lfZlcxrgCASJRskL1P8jZ4X-fd-Vq6ZpSi349inpbWB7vO_SY3VjujKte4dDhidrtTyfmNanqqD1u3CH7XxuvsolZNtDc_9zD7fH76mM6K-dvL63QyLzQmNBUIYY6UMIBXlnFR4QoQqBmjQgMGRYmYAVgjK6jVGipTQcYUqbt_I6ipKjzMXnuv8Wol2-DWKhykV06eAh8WUoXkdGMlJjWlGkFd66rkjHFsUVnzbqoBhgraue5711I1_1SzyVweMwAxQbwUe9ixdz3brW27szHJld-FbhlRQg45Rphx0lEPPaWDjzHY-lcLgTxVJU9VyWNV-Bte3oW1</addsrcrecordid><sourcetype>Open Website</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>1818323785</pqid></control><display><type>article</type><title>A proof of Zhil'tsov's theorem on decidability of equational theory of epigroups</title><source>Publicly Available Content (ProQuest)</source><creator>Mikhaylova, Inna</creator><creatorcontrib>Mikhaylova, Inna</creatorcontrib><description>Epigroups are semigroups equipped with an additional unary operation called pseudoinversion. Each finite semigroup can be considered as an epigroup. We prove the following theorem announced by Zhil'tsov in 2000: the equational theory of the class of all epigroups coincides with the equational theory of the class of all finite epigroups and is decidable. We show that the theory is not finitely based but provide a transparent infinite basis for it.</description><identifier>ISSN: 1365-8050</identifier><identifier>ISSN: 1462-7264</identifier><identifier>EISSN: 1365-8050</identifier><identifier>DOI: 10.46298/dmtcs.2155</identifier><language>eng</language><publisher>Nancy: DMTCS</publisher><subject>[info.info-dm] computer science [cs]/discrete mathematics [cs.dm] ; Combinatorics ; Computer Science ; decidability of equational theory ; Discrete Mathematics ; epigroup ; finite basis proble ; finite semigroup ; Theorems</subject><ispartof>Discrete mathematics and theoretical computer science, 2016-06, Vol.17 no. 3 (Combinatorics), p.179-202</ispartof><rights>Copyright DMTCS 2016</rights><rights>Distributed under a Creative Commons Attribution 4.0 International License</rights><lds50>peer_reviewed</lds50><oa>free_for_read</oa><woscitedreferencessubscribed>false</woscitedreferencessubscribed></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><linktohtml>$$Uhttps://www.proquest.com/docview/1818323785?pq-origsite=primo$$EHTML$$P50$$Gproquest$$Hfree_for_read</linktohtml><link.rule.ids>230,314,780,784,885,25753,27924,27925,37012,44590</link.rule.ids><backlink>$$Uhttps://inria.hal.science/hal-01352849$$DView record in HAL$$Hfree_for_read</backlink></links><search><creatorcontrib>Mikhaylova, Inna</creatorcontrib><title>A proof of Zhil'tsov's theorem on decidability of equational theory of epigroups</title><title>Discrete mathematics and theoretical computer science</title><description>Epigroups are semigroups equipped with an additional unary operation called pseudoinversion. Each finite semigroup can be considered as an epigroup. We prove the following theorem announced by Zhil'tsov in 2000: the equational theory of the class of all epigroups coincides with the equational theory of the class of all finite epigroups and is decidable. We show that the theory is not finitely based but provide a transparent infinite basis for it.</description><subject>[info.info-dm] computer science [cs]/discrete mathematics [cs.dm]</subject><subject>Combinatorics</subject><subject>Computer Science</subject><subject>decidability of equational theory</subject><subject>Discrete Mathematics</subject><subject>epigroup</subject><subject>finite basis proble</subject><subject>finite semigroup</subject><subject>Theorems</subject><issn>1365-8050</issn><issn>1462-7264</issn><issn>1365-8050</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2016</creationdate><recordtype>article</recordtype><sourceid>PIMPY</sourceid><sourceid>DOA</sourceid><recordid>eNpVkUtLAzEYRQdRsFZX_oEBF0Vkah6T17IUtUJBF7pxEzJJpk2ZNtMkLfTfO-2IKAQSbg7ng-9m2S0E45IiwR_NOuk4RpCQs2wAMSUFBwSc_3lfZlcxrgCASJRskL1P8jZ4X-fd-Vq6ZpSi349inpbWB7vO_SY3VjujKte4dDhidrtTyfmNanqqD1u3CH7XxuvsolZNtDc_9zD7fH76mM6K-dvL63QyLzQmNBUIYY6UMIBXlnFR4QoQqBmjQgMGRYmYAVgjK6jVGipTQcYUqbt_I6ipKjzMXnuv8Wol2-DWKhykV06eAh8WUoXkdGMlJjWlGkFd66rkjHFsUVnzbqoBhgraue5711I1_1SzyVweMwAxQbwUe9ixdz3brW27szHJld-FbhlRQg45Rphx0lEPPaWDjzHY-lcLgTxVJU9VyWNV-Bte3oW1</recordid><startdate>20160607</startdate><enddate>20160607</enddate><creator>Mikhaylova, Inna</creator><general>DMTCS</general><general>Discrete Mathematics &amp; Theoretical Computer Science</general><scope>AAYXX</scope><scope>CITATION</scope><scope>8FE</scope><scope>8FG</scope><scope>ABJCF</scope><scope>ABUWG</scope><scope>AFKRA</scope><scope>AZQEC</scope><scope>BENPR</scope><scope>BFMQW</scope><scope>BGLVJ</scope><scope>CCPQU</scope><scope>DWQXO</scope><scope>HCIFZ</scope><scope>L6V</scope><scope>M7S</scope><scope>PIMPY</scope><scope>PQEST</scope><scope>PQQKQ</scope><scope>PQUKI</scope><scope>PRINS</scope><scope>PTHSS</scope><scope>1XC</scope><scope>VOOES</scope><scope>DOA</scope></search><sort><creationdate>20160607</creationdate><title>A proof of Zhil'tsov's theorem on decidability of equational theory of epigroups</title><author>Mikhaylova, Inna</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c356t-22382a9d08be789b3b051c7769c0719427d03c2e96ecc1adb177a5f769d96dbb3</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2016</creationdate><topic>[info.info-dm] computer science [cs]/discrete mathematics [cs.dm]</topic><topic>Combinatorics</topic><topic>Computer Science</topic><topic>decidability of equational theory</topic><topic>Discrete Mathematics</topic><topic>epigroup</topic><topic>finite basis proble</topic><topic>finite semigroup</topic><topic>Theorems</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Mikhaylova, Inna</creatorcontrib><collection>CrossRef</collection><collection>ProQuest SciTech Collection</collection><collection>ProQuest Technology Collection</collection><collection>Materials Science &amp; Engineering Collection</collection><collection>ProQuest Central (Alumni)</collection><collection>ProQuest Central</collection><collection>ProQuest Central Essentials</collection><collection>ProQuest Central</collection><collection>ProQuest Continental Europe Database</collection><collection>Technology Collection</collection><collection>ProQuest One Community College</collection><collection>ProQuest Central</collection><collection>SciTech Premium Collection</collection><collection>ProQuest Engineering Collection</collection><collection>Engineering Database</collection><collection>Publicly Available Content (ProQuest)</collection><collection>ProQuest One Academic Eastern Edition (DO NOT USE)</collection><collection>ProQuest One Academic</collection><collection>ProQuest One Academic UKI Edition</collection><collection>ProQuest Central China</collection><collection>Engineering Collection</collection><collection>Hyper Article en Ligne (HAL)</collection><collection>Hyper Article en Ligne (HAL) (Open Access)</collection><collection>DOAJ Directory of Open Access Journals</collection><jtitle>Discrete mathematics and theoretical computer science</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Mikhaylova, Inna</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>A proof of Zhil'tsov's theorem on decidability of equational theory of epigroups</atitle><jtitle>Discrete mathematics and theoretical computer science</jtitle><date>2016-06-07</date><risdate>2016</risdate><volume>17 no. 3</volume><issue>Combinatorics</issue><spage>179</spage><epage>202</epage><pages>179-202</pages><issn>1365-8050</issn><issn>1462-7264</issn><eissn>1365-8050</eissn><abstract>Epigroups are semigroups equipped with an additional unary operation called pseudoinversion. Each finite semigroup can be considered as an epigroup. We prove the following theorem announced by Zhil'tsov in 2000: the equational theory of the class of all epigroups coincides with the equational theory of the class of all finite epigroups and is decidable. We show that the theory is not finitely based but provide a transparent infinite basis for it.</abstract><cop>Nancy</cop><pub>DMTCS</pub><doi>10.46298/dmtcs.2155</doi><tpages>24</tpages><oa>free_for_read</oa></addata></record>
fulltext fulltext
identifier ISSN: 1365-8050
ispartof Discrete mathematics and theoretical computer science, 2016-06, Vol.17 no. 3 (Combinatorics), p.179-202
issn 1365-8050
1462-7264
1365-8050
language eng
recordid cdi_doaj_primary_oai_doaj_org_article_35f66c21cfcb487783e24f889bd0d696
source Publicly Available Content (ProQuest)
subjects [info.info-dm] computer science [cs]/discrete mathematics [cs.dm]
Combinatorics
Computer Science
decidability of equational theory
Discrete Mathematics
epigroup
finite basis proble
finite semigroup
Theorems
title A proof of Zhil'tsov's theorem on decidability of equational theory of epigroups
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-08T00%3A26%3A49IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-proquest_doaj_&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=A%20proof%20of%20Zhil'tsov's%20theorem%20on%20decidability%20of%20equational%20theory%20of%20epigroups&rft.jtitle=Discrete%20mathematics%20and%20theoretical%20computer%20science&rft.au=Mikhaylova,%20Inna&rft.date=2016-06-07&rft.volume=17%20no.%203&rft.issue=Combinatorics&rft.spage=179&rft.epage=202&rft.pages=179-202&rft.issn=1365-8050&rft.eissn=1365-8050&rft_id=info:doi/10.46298/dmtcs.2155&rft_dat=%3Cproquest_doaj_%3E4178420911%3C/proquest_doaj_%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c356t-22382a9d08be789b3b051c7769c0719427d03c2e96ecc1adb177a5f769d96dbb3%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=1818323785&rft_id=info:pmid/&rfr_iscdi=true