Loading…
Complexity of shift spaces on semigroups
Let G = S | R A be a semigroup with generating set S and equivalences R A among S determined by a matrix A . This paper investigates the complexity of G -shift spaces by yielding the Petersen–Salama entropies [defined in Petersen and Salama (Theoret Comput Sci 743:64–71, 2018)]. After revealing the...
Saved in:
| Published in: | Journal of algebraic combinatorics 2021-03, Vol.53 (2), p.413-434 |
|---|---|
| Main Authors: | , , |
| Format: | Article |
| Language: | English |
| Subjects: | |
| Citations: | Items that this one cites Items that cite this one |
| Online Access: | Get full text |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| cited_by | cdi_FETCH-LOGICAL-c363t-478a58ccd37e75736a0b0df081563fe9afe925e94a02426f3fddb1443686a7f63 |
|---|---|
| cites | cdi_FETCH-LOGICAL-c363t-478a58ccd37e75736a0b0df081563fe9afe925e94a02426f3fddb1443686a7f63 |
| container_end_page | 434 |
| container_issue | 2 |
| container_start_page | 413 |
| container_title | Journal of algebraic combinatorics |
| container_volume | 53 |
| creator | Ban, Jung-Chao Chang, Chih-Hung Huang, Yu-Hsiung |
| description | Let
G
=
S
|
R
A
be a semigroup with generating set
S
and equivalences
R
A
among
S
determined by a matrix
A
. This paper investigates the complexity of
G
-shift spaces by yielding the Petersen–Salama entropies [defined in Petersen and Salama (Theoret Comput Sci 743:64–71, 2018)]. After revealing the existence of Petersen–Salama entropy of
G
-shift of finite type (
G
-SFT), the calculation of Petersen–Salama entropy of
G
-SFT is equivalent to solving a system of nonlinear recurrence equations. The complete characterization of Petersen–Salama entropies of
G
-SFTs on two symbols is addressed, which extends (Ban and Chang in On the topological entropy of subshifts of finite type on free semigroups, 2018.
arXiv:1702.04394
) in which
G
is a free semigroup. |
| doi_str_mv | 10.1007/s10801-019-00935-1 |
| format | article |
| fullrecord | <record><control><sourceid>proquest_cross</sourceid><recordid>TN_cdi_proquest_journals_2507709112</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><sourcerecordid>2507709112</sourcerecordid><originalsourceid>FETCH-LOGICAL-c363t-478a58ccd37e75736a0b0df081563fe9afe925e94a02426f3fddb1443686a7f63</originalsourceid><addsrcrecordid>eNp9kE1LxDAURYMoOI7-AVcFN26i7yVN0ixl8AsG3Og6ZNpk7DBtatKC8--NVnDn4vE2594Lh5BLhBsEULcJoQKkgJoCaC4oHpEFCsWoRs2OyQI0E1RXWp-Ss5R2kKkKxYJcr0I37N1nOx6K4Iv03vqxSIOtXSpCXyTXtdsYpiGdkxNv98ld_P4leXu4f1090fXL4_Pqbk1rLvlIS1VZUdV1w5VTQnFpYQONhzwmuXfa5mPC6dICK5n03DfNBsuSy0pa5SVfkqu5d4jhY3JpNLswxT5PGiZAKdCILFNspuoYUorOmyG2nY0Hg2C-jZjZiMlGzI8RgznE51DKcL918a_6n9QXR4JiEw</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>2507709112</pqid></control><display><type>article</type><title>Complexity of shift spaces on semigroups</title><source>Springer Nature</source><creator>Ban, Jung-Chao ; Chang, Chih-Hung ; Huang, Yu-Hsiung</creator><creatorcontrib>Ban, Jung-Chao ; Chang, Chih-Hung ; Huang, Yu-Hsiung</creatorcontrib><description>Let
G
=
S
|
R
A
be a semigroup with generating set
S
and equivalences
R
A
among
S
determined by a matrix
A
. This paper investigates the complexity of
G
-shift spaces by yielding the Petersen–Salama entropies [defined in Petersen and Salama (Theoret Comput Sci 743:64–71, 2018)]. After revealing the existence of Petersen–Salama entropy of
G
-shift of finite type (
G
-SFT), the calculation of Petersen–Salama entropy of
G
-SFT is equivalent to solving a system of nonlinear recurrence equations. The complete characterization of Petersen–Salama entropies of
G
-SFTs on two symbols is addressed, which extends (Ban and Chang in On the topological entropy of subshifts of finite type on free semigroups, 2018.
arXiv:1702.04394
) in which
G
is a free semigroup.</description><identifier>ISSN: 0925-9899</identifier><identifier>EISSN: 1572-9192</identifier><identifier>DOI: 10.1007/s10801-019-00935-1</identifier><language>eng</language><publisher>New York: Springer US</publisher><subject>Combinatorics ; Complexity ; Computer Science ; Convex and Discrete Geometry ; Entropy ; Equivalence ; Group Theory and Generalizations ; Lattices ; Mathematics ; Mathematics and Statistics ; Order ; Ordered Algebraic Structures</subject><ispartof>Journal of algebraic combinatorics, 2021-03, Vol.53 (2), p.413-434</ispartof><rights>Springer Science+Business Media, LLC, part of Springer Nature 2020</rights><rights>Springer Science+Business Media, LLC, part of Springer Nature 2020.</rights><lds50>peer_reviewed</lds50><oa>free_for_read</oa><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c363t-478a58ccd37e75736a0b0df081563fe9afe925e94a02426f3fddb1443686a7f63</citedby><cites>FETCH-LOGICAL-c363t-478a58ccd37e75736a0b0df081563fe9afe925e94a02426f3fddb1443686a7f63</cites></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><link.rule.ids>314,776,780,27901,27902</link.rule.ids></links><search><creatorcontrib>Ban, Jung-Chao</creatorcontrib><creatorcontrib>Chang, Chih-Hung</creatorcontrib><creatorcontrib>Huang, Yu-Hsiung</creatorcontrib><title>Complexity of shift spaces on semigroups</title><title>Journal of algebraic combinatorics</title><addtitle>J Algebr Comb</addtitle><description>Let
G
=
S
|
R
A
be a semigroup with generating set
S
and equivalences
R
A
among
S
determined by a matrix
A
. This paper investigates the complexity of
G
-shift spaces by yielding the Petersen–Salama entropies [defined in Petersen and Salama (Theoret Comput Sci 743:64–71, 2018)]. After revealing the existence of Petersen–Salama entropy of
G
-shift of finite type (
G
-SFT), the calculation of Petersen–Salama entropy of
G
-SFT is equivalent to solving a system of nonlinear recurrence equations. The complete characterization of Petersen–Salama entropies of
G
-SFTs on two symbols is addressed, which extends (Ban and Chang in On the topological entropy of subshifts of finite type on free semigroups, 2018.
arXiv:1702.04394
) in which
G
is a free semigroup.</description><subject>Combinatorics</subject><subject>Complexity</subject><subject>Computer Science</subject><subject>Convex and Discrete Geometry</subject><subject>Entropy</subject><subject>Equivalence</subject><subject>Group Theory and Generalizations</subject><subject>Lattices</subject><subject>Mathematics</subject><subject>Mathematics and Statistics</subject><subject>Order</subject><subject>Ordered Algebraic Structures</subject><issn>0925-9899</issn><issn>1572-9192</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2021</creationdate><recordtype>article</recordtype><recordid>eNp9kE1LxDAURYMoOI7-AVcFN26i7yVN0ixl8AsG3Og6ZNpk7DBtatKC8--NVnDn4vE2594Lh5BLhBsEULcJoQKkgJoCaC4oHpEFCsWoRs2OyQI0E1RXWp-Ss5R2kKkKxYJcr0I37N1nOx6K4Iv03vqxSIOtXSpCXyTXtdsYpiGdkxNv98ld_P4leXu4f1090fXL4_Pqbk1rLvlIS1VZUdV1w5VTQnFpYQONhzwmuXfa5mPC6dICK5n03DfNBsuSy0pa5SVfkqu5d4jhY3JpNLswxT5PGiZAKdCILFNspuoYUorOmyG2nY0Hg2C-jZjZiMlGzI8RgznE51DKcL918a_6n9QXR4JiEw</recordid><startdate>20210301</startdate><enddate>20210301</enddate><creator>Ban, Jung-Chao</creator><creator>Chang, Chih-Hung</creator><creator>Huang, Yu-Hsiung</creator><general>Springer US</general><general>Springer Nature B.V</general><scope>AAYXX</scope><scope>CITATION</scope></search><sort><creationdate>20210301</creationdate><title>Complexity of shift spaces on semigroups</title><author>Ban, Jung-Chao ; Chang, Chih-Hung ; Huang, Yu-Hsiung</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c363t-478a58ccd37e75736a0b0df081563fe9afe925e94a02426f3fddb1443686a7f63</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2021</creationdate><topic>Combinatorics</topic><topic>Complexity</topic><topic>Computer Science</topic><topic>Convex and Discrete Geometry</topic><topic>Entropy</topic><topic>Equivalence</topic><topic>Group Theory and Generalizations</topic><topic>Lattices</topic><topic>Mathematics</topic><topic>Mathematics and Statistics</topic><topic>Order</topic><topic>Ordered Algebraic Structures</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Ban, Jung-Chao</creatorcontrib><creatorcontrib>Chang, Chih-Hung</creatorcontrib><creatorcontrib>Huang, Yu-Hsiung</creatorcontrib><collection>CrossRef</collection><jtitle>Journal of algebraic combinatorics</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Ban, Jung-Chao</au><au>Chang, Chih-Hung</au><au>Huang, Yu-Hsiung</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>Complexity of shift spaces on semigroups</atitle><jtitle>Journal of algebraic combinatorics</jtitle><stitle>J Algebr Comb</stitle><date>2021-03-01</date><risdate>2021</risdate><volume>53</volume><issue>2</issue><spage>413</spage><epage>434</epage><pages>413-434</pages><issn>0925-9899</issn><eissn>1572-9192</eissn><abstract>Let
G
=
S
|
R
A
be a semigroup with generating set
S
and equivalences
R
A
among
S
determined by a matrix
A
. This paper investigates the complexity of
G
-shift spaces by yielding the Petersen–Salama entropies [defined in Petersen and Salama (Theoret Comput Sci 743:64–71, 2018)]. After revealing the existence of Petersen–Salama entropy of
G
-shift of finite type (
G
-SFT), the calculation of Petersen–Salama entropy of
G
-SFT is equivalent to solving a system of nonlinear recurrence equations. The complete characterization of Petersen–Salama entropies of
G
-SFTs on two symbols is addressed, which extends (Ban and Chang in On the topological entropy of subshifts of finite type on free semigroups, 2018.
arXiv:1702.04394
) in which
G
is a free semigroup.</abstract><cop>New York</cop><pub>Springer US</pub><doi>10.1007/s10801-019-00935-1</doi><tpages>22</tpages><oa>free_for_read</oa></addata></record> |
| fulltext | fulltext |
| identifier | ISSN: 0925-9899 |
| ispartof | Journal of algebraic combinatorics, 2021-03, Vol.53 (2), p.413-434 |
| issn | 0925-9899 1572-9192 |
| language | eng |
| recordid | cdi_proquest_journals_2507709112 |
| source | Springer Nature |
| subjects | Combinatorics Complexity Computer Science Convex and Discrete Geometry Entropy Equivalence Group Theory and Generalizations Lattices Mathematics Mathematics and Statistics Order Ordered Algebraic Structures |
| title | Complexity of shift spaces on semigroups |
| url | http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-02-13T21%3A14%3A49IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-proquest_cross&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=Complexity%20of%20shift%20spaces%20on%20semigroups&rft.jtitle=Journal%20of%20algebraic%20combinatorics&rft.au=Ban,%20Jung-Chao&rft.date=2021-03-01&rft.volume=53&rft.issue=2&rft.spage=413&rft.epage=434&rft.pages=413-434&rft.issn=0925-9899&rft.eissn=1572-9192&rft_id=info:doi/10.1007/s10801-019-00935-1&rft_dat=%3Cproquest_cross%3E2507709112%3C/proquest_cross%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c363t-478a58ccd37e75736a0b0df081563fe9afe925e94a02426f3fddb1443686a7f63%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=2507709112&rft_id=info:pmid/&rfr_iscdi=true |