Zobrazeno 1 - 10
of 66
pro vyhledávání: '"Vesa Halava"'
Publikováno v:
Electronic Proceedings in Theoretical Computer Science, Vol 63, Iss Proc. WORDS 2011, Pp 147-151 (2011)
We give a new proof for the decidability of the D0L ultimate periodicity problem based on the decidability of p-periodicity of morphic words adapted to the approach of Harju and Linna.
Externí odkaz:
https://doaj.org/article/46f6024985b34c4ba1911ae6cdca254d
Publikováno v:
Discrete Mathematics & Theoretical Computer Science, Vol Vol. 10 no. 1, Iss Automata, Logic and Semantics (2008)
Automata, Logic and Semantics
Externí odkaz:
https://doaj.org/article/b1c57559a2144686aa83501dfd2d7336
Publikováno v:
Discrete Mathematics & Theoretical Computer Science, Vol 10, Iss 1 (2008)
We consider relational periods where the relation is a compatibility relation on words induced by a relation on letters. We introduce three types of periods, namely global, external and local relational periods, and we compare their properties by pro
Externí odkaz:
https://doaj.org/article/fe59bfd3bc11432a8d36a0820d96328b
Publikováno v:
Developments in Language Theory ISBN: 9783030815073
DLT
DLT
In this paper we combine two classical generalisations of finite automata (weighted automata and automata on infinite words) into a model of integer weighted automata on infinite words and study the universality and the emptiness problems under zero
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::bfbe4cb54b928b29ce0c4f8e3ab6d5bd
https://doi.org/10.1142/s0129054122440014
https://doi.org/10.1142/s0129054122440014
Publikováno v:
Filomat. 36:2775-2793
In this paper we study particular linear and weakly linear systems of matrix equations over semirings, with the aim of describing and computing functions as solutions to those systems. Our special attention is devoted to solutions whose ranks are as
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::3f17577f387fd76872fde628283726a4
https://doi.org/10.2298/fil2208775s
https://doi.org/10.2298/fil2208775s
Publikováno v:
Fundamenta Informaticae. 175:201-206
Denote by ш the operation of interleaving, or shuffling, of words. We prove that, given a regular language R and a letter-to-letter morphism φ, it is undecidable whether or not there exists a word ω such that ω ш φ(ω) ∩ R ≠ ø.
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::c30f7cab92a1c1af8b9ba42125cb1d13
https://doi.org/10.3233/fi-2020-1954
https://doi.org/10.3233/fi-2020-1954
Autor:
Tero Harju, Vesa Halava
Publikováno v:
Acta Cybernetica. 24:613-623
In 1946, Emil Leon Post (Bulletin of Amer. Math. Soc. 52 (1946), 264-268) introduced his famouscorrespondence decision problem, nowadays known as the Post Correspondence Problem (PCP).Post proved the undecidability of the PCP by areduction from his n
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::b98f00f01ed0733ad3161e853e6a2c3a
https://doi.org/10.14232/actacyb.284625
https://doi.org/10.14232/actacyb.284625
Publikováno v:
SSRN Electronic Journal.
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::9d19f467377d47ccdfd20dc61c29d8d0
https://doi.org/10.2139/ssrn.4021954
https://doi.org/10.2139/ssrn.4021954
Publikováno v:
Theoretical Computer Science. 732:85-88
We show that it is undecidable whether or not an injective rational function (realized by a finite transducer) f : A ⁎ → A ⁎ has a fixed point. The proof applies undecidability of the Post's Correspondence Problem for injective morphisms. As a
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::c30f44bde7ee85578758a38e8402b2fe
https://doi.org/10.1016/j.tcs.2018.04.030
https://doi.org/10.1016/j.tcs.2018.04.030
Autor:
Tero Harju, Vesa Halava
Publikováno v:
Theoretical Computer Science. 701:120-124
In 1966 J.R. Isbell proved his algebraic Zig-Zag Theorem using a simple property of paths in a tiling of a plane rectangle. We prove here Isbell's lemma for more general tilings of plane rectangles.
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::ffe9596f04d60d13c3afb3983ad4ce68
https://doi.org/10.1016/j.tcs.2017.02.034
https://doi.org/10.1016/j.tcs.2017.02.034