Zobrazeno 1 - 10
of 26
pro vyhledávání: '"Jozef Jirásek"'
Publikováno v:
Developments in Language Theory
This paper examines several measures of space complexity of variants of stack automata: non-erasing stack automata and checking stack automata. These measures capture the minimum stack size required to accept every word in the language of the automat
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::35e1df19181463c44760fd2d571e9a1f
https://doi.org/10.1142/s0129054121420090
https://doi.org/10.1142/s0129054121420090
Autor:
Jozef Jirásek, Ian McQuillan
Publikováno v:
Developments in Language Theory ISBN: 9783031055775
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::e3f7b0ee1a7f87d1cab640c6bf6cde32
https://doi.org/10.1007/978-3-031-05578-2_15
https://doi.org/10.1007/978-3-031-05578-2_15
Publikováno v:
International Journal of Foundations of Computer Science. 30:1091-1115
We study Kuratowski algebras generated by prefix-, suffix-, factor-, and subword-free languages under the operations of star and complementation. We examine 12 possible algebras, and for each of them, we decide whether or not it can be generated by a
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::c0e8dafbc70ebbdeaa10d0f1703225fd
https://doi.org/10.1142/s0129054119400306
https://doi.org/10.1142/s0129054119400306
Publikováno v:
Developments in Language Theory ISBN: 9783030485153
DLT
DLT
This paper examines several measures of space complexity on variants of stack automata: non-erasing stack automata and checking stack automata. These measures capture the minimum stack size required to accept any word in a language (weak measure), th
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::c419c2cc2adf31668c2c320d75f6f605
https://doi.org/10.1007/978-3-030-48516-0_11
https://doi.org/10.1007/978-3-030-48516-0_11
Publikováno v:
International Journal of Foundations of Computer Science. 29:861-876
A nondeterministic finite automaton is unambiguous if it has at most one accepting computation on every input string. We investigate the state complexity of basic regular operations on languages represented by unambiguous finite automata. We get tigh
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::41ede4fadf5beb4b84943d02cb686756
https://doi.org/10.1142/s012905411842008x
https://doi.org/10.1142/s012905411842008x
Publikováno v:
Theoretical Computer Science. 610:78-90
We investigate the left and right quotient, and the reversal operation on the class of prefix-free regular languages. We get the tight upper bounds 2 n - 1 , n - 1 , and 2 n - 2 + 1 on the state complexity of these three operations, respectively. To
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::fa20aa6e94c00a4be43446ab33e7d4e9
https://doi.org/10.1016/j.tcs.2015.08.031
https://doi.org/10.1016/j.tcs.2015.08.031
Publikováno v:
Developments in Language Theory ISBN: 9783319986531
DLT
DLT
A self-verifying finite automaton (SVFA) is a nondeterministic automaton whose computation can accept, reject, or give no answer. Every word is guaranteed to be either accepted or rejected, and the automaton can not give contradictory answers. This p
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::a72091f6fe8036d89ab406b6081ad213
https://doi.org/10.1007/978-3-319-98654-8_33
https://doi.org/10.1007/978-3-319-98654-8_33
Autor:
Galina Jirásková, Jozef Jirásek
Publikováno v:
Implementation and Application of Automata ISBN: 9783319948119
CIAA
CIAA
We show that the state complexity of the star-complement-star operation is given by \(\frac{3}{2}f(n\,-\,1) \,+\, 2 f(n\,-\,2) \,+\, 2n \,-\,5\), where \(f(2)=2\) and \(f(n) = \sum _{i=1}^{n-2}{n\atopwithdelims ()i} f (n\,-\,i) \,+\,2\). The function
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::d74d921bff840cfa5e599107d8bf957c
https://doi.org/10.1007/978-3-319-94812-6_19
https://doi.org/10.1007/978-3-319-94812-6_19
Autor:
Jozef Jirásek, Galina Jirásková
Publikováno v:
Theoretical Computer Science. 578:42-57
We prove that the tight bound on the state complexity of the boundary of regular languages, defined as bd ( L ) = L * ? ( L ? ) * , is 3 / 8 ? 4 n + 2 n - 2 - 2 ? 3 n - 2 - n + 2 . Our witness languages are described over a five-letter alphabet. Next
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::a25a773fbd87da6e156f9d9e6f01a7ff
https://doi.org/10.1016/j.tcs.2015.01.022
https://doi.org/10.1016/j.tcs.2015.01.022