DC Field
Value
Language
dc.contributor.author
Droste, Manfred
-
dc.contributor.author
Kuich, Werner
-
dc.date.accessioned
2025-01-24T14:47:18Z
-
dc.date.available
2025-01-24T14:47:18Z
-
dc.date.issued
2024-06-29
-
dc.identifier.citation
<div class="csl-bib-body"> <div class="csl-entry">Droste, M., &#38; Kuich, W. (2024). Undecidability of the universal support problem for weighted automata over zero-sum-free commutative semirings. <i>Theoretical Computer Science</i>, <i>1002</i>, Article 114599. https://doi.org/10.1016/j.tcs.2024.114599</div> </div>
-
dc.identifier.issn
0304-3975
-
dc.identifier.uri
http://hdl.handle.net/20.500.12708/209620
-
dc.description.abstract
We show that there is an effectively given zero-sum-free commutative semiring S, contained as the subsemiring of nonnegative elements in an effectively given commutative ordered ring, for which there are no procedures deciding, given a weighted finite automaton over S, whether its support is the language of all words or whether its support is infinite. In particular, by a result of D. Kirsten (2011), since S is zero-sum-free and commutative, the support is recognizable by a classical finite automaton, but such an automaton or even just a pushdown automaton for its support cannot be constructed effectively.
en
dc.language.iso
en
-
dc.publisher
ELSEVIER
-
dc.relation.ispartof
Theoretical Computer Science
-
dc.rights.uri
https://creativecommons.org/licenses/by-nc-nd/4.0/
-
dc.subject
Finite automata
en
dc.subject
Semirings
en
dc.subject
Support problem
en
dc.subject
Undecidability problem
en
dc.subject
Weighted automata
en
dc.subject
Zero-sum-free semirings
en
dc.title
Undecidability of the universal support problem for weighted automata over zero-sum-free commutative semirings
en
dc.type
Article
en
dc.type
Artikel
de
dc.rights.license
Creative Commons Namensnennung - Nicht kommerziell - Keine Bearbeitungen 4.0 International
de
dc.rights.license
Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International
en
dc.identifier.scopus
2-s2.0-85191323293
-
dc.identifier.url
https://api.elsevier.com/content/abstract/scopus_id/85191323293
-
dc.contributor.affiliation
Leipzig University, Germany
-
dc.rights.holder
© 2024 The Authors.
-
dc.type.category
Original Research Article
-
tuw.container.volume
1002
-
tuw.journal.peerreviewed
true
-
tuw.peerreviewed
true
-
wb.publication.intCoWork
International Co-publication
-
tuw.researchTopic.id
A3
-
tuw.researchTopic.name
Fundamental Mathematics Research
-
tuw.researchTopic.value
100
-
dcterms.isPartOf.title
Theoretical Computer Science
-
tuw.publication.orgunit
E104-02 - Forschungsbereich Computational Logic
-
tuw.publisher.doi
10.1016/j.tcs.2024.114599
-
dc.date.onlinefirst
2024-04-25
-
dc.identifier.articleid
114599
-
dc.identifier.eissn
1879-2294
-
dc.identifier.libraryid
AC17418540
-
dc.description.numberOfPages
4
-
tuw.author.orcid
0000-0001-9128-8844
-
dc.rights.identifier
CC BY-NC-ND 4.0
de
dc.rights.identifier
CC BY-NC-ND 4.0
en
wb.sci
true
-
wb.sciencebranch
Informatik
-
wb.sciencebranch
Mathematik
-
wb.sciencebranch.oefos
1020
-
wb.sciencebranch.oefos
1010
-
wb.sciencebranch.value
5
-
wb.sciencebranch.value
95
-
item.languageiso639-1
en
-
item.openairetype
research article
-
item.grantfulltext
open
-
item.fulltext
with Fulltext
-
item.cerifentitytype
Publications
-
item.mimetype
application/pdf
-
item.openairecristype
http://purl.org/coar/resource_type/c_2df8fbb1
-
item.openaccessfulltext
Open Access
-
crisitem.author.dept
Leipzig University
-
crisitem.author.dept
E104 - Institut für Diskrete Mathematik und Geometrie
-
crisitem.author.orcid
0000-0001-9128-8844
-
crisitem.author.parentorg
E100 - Fakultät für Mathematik und Geoinformation
-
Appears in Collections:
Article
Thumbnail
Fulltext (Version of Record (published version))
Adobe PDF
(398.29 kB)
Publikation
Open Access CC BY-NC-ND 4.0
Show simple item record

Page view(s)

53
checked on Jan 25, 2025

Download(s)

29
checked on Jan 25, 2025

Google ScholarTM

Check