Zobrazeno 1 - 10
of 11
pro vyhledávání: '"Branislav Rovan"'
Publikováno v:
Language and Automata Theory and Applications ISBN: 9783030681944
LATA
LATA
In this paper we continue the research on usefulness of information examining the effect of supplementary information on the complexity of solving a problem (see Rovan and Sadovský [7] for an overview). We use deterministic finite automata for a for
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::03625cf97e7a9a4aa6bada6bf3240d90
https://doi.org/10.1007/978-3-030-68195-1_11
https://doi.org/10.1007/978-3-030-68195-1_11
Autor:
Branislav Rovan, Peter Kostolányi
Publikováno v:
International Journal of Foundations of Computer Science. 27:787-807
We introduce a new generalization of weighted automata – automata with auxiliary weights. They allow to compute several quantities not directly computable over semirings by generalizing both semiring addition and semiring multiplication. Moreover,
Publikováno v:
Theoretical Computer Science. 132:319-336
The study of synchronized alternating machines has enabled to characterize several natural complexity classes. It is known that synchronized alternating space SASPACE(S(n))= ∪c>0NSPACE(ncS(n)) for any (space-constructible) function S(n) [Hromkovic
Autor:
Pavel Labath, Branislav Rovan
Publikováno v:
Language and Automata Theory and Applications ISBN: 9783642212536
LATA
LATA
We study the effect of using supplementary information on the complexity of deterministic pushdown automata. This continues the study of assisted problem solving initiated in [Gaži, Rovan 2008]. We study deterministic PDA that can assume its input t
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::8a323df6ed2d38353e142c68b1d3716d
https://doi.org/10.1007/978-3-642-21254-3_27
https://doi.org/10.1007/978-3-642-21254-3_27
Autor:
Katsushi Inoue, Branislav Rovan, Anna Slobodová, Klaus W. Wagner, Itsuo Takanami, Juraj Hromkovic
Publikováno v:
International Journal of Foundations of Computer Science. :65-79
This paper continues the investigation of the concept of synchronized alternation. The open problems from Ref. 4 are solved by showing that one-way synchronized alternating (multihead) automata are as powerful as two-way ones. More precisely it is sh
Publikováno v:
Discrete Applied Mathematics. 32:155-182
This paper continues investigations of synchronized alternating machines which provide a natural model of communication of parallel processes. It is proved that synchronized alternating space SASPACE(S(n)) = ⋃c>0 NSPACE(n·cS(n)). Using this charac
Autor:
Branislav Rovan, Peter Gaži
Publikováno v:
SOFSEM 2008: Theory and Practice of Computer Science ISBN: 9783540775652
SOFSEM
SOFSEM
A study of assisted problem solving formalized via decompositions of deterministic finite automata is initiated. The landscape of new types of decompositions of finite automata this study uncovered is presented. Languages with various degrees of deco
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::d09d0f7e74a990f54a48762b08a0322a
https://doi.org/10.1007/978-3-540-77566-9_25
https://doi.org/10.1007/978-3-540-77566-9_25
Autor:
Branislav Rovan, L'ubos Steskal
Publikováno v:
Lecture Notes in Computer Science ISBN: 9783540730002
We present a hierarchy of families between the Σ 2 and Δ 3 levels of the arithmetic hierarchy. The structure of the top five levels of this hierarchy is in some sense similar to the structure of the Chomsky hierarchy, while the bottom levels are re
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::30072f1c867a092d34a1e3bc3a496074
https://doi.org/10.1007/978-3-540-73001-9_68
https://doi.org/10.1007/978-3-540-73001-9_68
Autor:
Seymour Ginsburg, Branislav Rovan
Publikováno v:
Information and Control. 26:34-44
The following result is established: Let L be a DOL language and x1, x2,…, a sequence of all words in L ordered by increasing length. Suppose that for some integer ko there exist arbitrarily long intervals xi,…, xi+l such that | xj+1 | − | xj |
Autor:
Branislav Rovan
Publikováno v:
Journal of Computer and System Sciences. 11(1):1-55
A study is made of necessary conditions in order for a bounded language V to be in the smallest [full] (semi-)AFL generated by a bounded language U. Two major classes of bounded languages are introduced. Specific necessary conditions are then derived