Automaty a formálne jazyky I, 1. stupeň štúdia, prednáška Automaty a formálne jazyky II, 1. stupeň štúdia, prednáška Výpočtová zložitosť, 2. stupeň štúdia, prednáška Seminár z teoretickej informatiky, 2. stupeň štúdia, seminár Výpočtová zložitosť a modely, 3. stupeň štúdia, prednáška Formálne jazyky a konečnostavové automaty, 3. stupeň štúdia, prednáška

3

21

5

VEGA 1/0479/12 „Kombinatorické štruktúry a zložitosť algoritmov“, 2012-2014, vedúci projektu, APVV-0035-10 „Algoritmy, automaty a diskrétne dátové štruktúry“, 2011-2014, vedúci projektu

49

228

8

8

2

ADC – V.Geffert: Normal forms for phrase-structure grammars, RAIRO - Informatique Theorique et Applications, 1991, Vol.25, No.5, pp.473-496

ADC – V.Geffert: Nondeterministic computations in sublogarithmic space and space constructibility, SIAM J. of Computing, 1991, Vol.20, No.3, pp.484-498

ADC – V.Geffert: Tally versions of the Savitch and Immerman-Szelepcsenyi theorems for sublogarithmic space, SIAM J. of Computing, 1993, Vol.22, No.1, pp.102-113

ADC – V.Geffert, J.Katajainen, T.Pasanen: Asymptotically efficient in-place merging, Theoretical Computer Science, Elsevier, 2000, Vol.237, pp.159-181

ADC – G.Franceschini, V.Geffert: An in-place sorting with O(n.log n) comparisons and O(n) moves, J. of the ACM, ACM Press, 2005, Vol.52, No.4, pp.515-537

ADC – V.Geffert: Normal forms for phrase-structure grammars, RAIRO - Informatique Theorique et Applications, 1991, Vol.25, No.5, pp.473-496: 19 ohlasov WoK 1. J.Gruska: Foundations of Computing, Internat. Thomson Computer Press (ITP), USA, 1997 2. A.Matescu, A.Salomaa: Aspects of classical language theory. In G.Rozenberg, A.Salomaa (eds.), Handbook of formal languages, Vol.I: Word, language, grammar. Springer-Verlag, 1997 3. M.Jantzen, H.Petersen: Cancellation in context-free languages: Enrichment by reduction, Theoretical Computer Science, Elsevier, 1994, Vol.127, No.1, pp.149-170 4. J.Dassow, V.Mitrana, and A.Salomaa: Context-free evolutionary grammars and the structural language of nucleic-acids, Biosystems, Elsevier, 1997, Vol.43, No.3, pp.169-177 5. G.Paun: DNA computing based on splicing: Universality results, Theoretical Computer Science, Elsevier, 2000, Vol.231, No.2, pp.275-296 6. E.Csuhaj-Varju, V.Mitrana: Evolutionary systems: A language generating device inspired by evolving communities of cells, Acta Informatica, Springer-Verlag, 2000, Vol.36, No.11, pp.913-926 7. E.Csuhaj-Varjú, C.Martín-Vide, V.Mitrana: Hybrid networks of evolutionary processors are computationally complete, Acta Informatica, Springer-Verlag, 2005, Vol.41, No.4-5, pp.257-272 8. F.Okubo: A note on the descriptional complexity of semi-conditional grammars, Information Processing Letters, 2009, Vol.110, No.1, pp.36-40 9. R.Freund, M.Oswald: CD grammar systems with regular start conditions, Internat. J. of Foundations of Computer Science, 2008, Vol.19, No.4, pp.767-779 10. K.Fujioka, H.Katsuno: On the generative power of cancel minimal linear grammars with single nonterminal symbol except the start symbol, IEICE Transactions on Information and Systems, 2011, Vol.E94D, No.10, pp.1945-1954

ADC – V.Geffert: Nondeterministic computations in sublogarithmic space and space constructibility, SIAM J. of Computing, 1991, Vol.20, No.3, pp.484-498: 32 ohlasov WoK 1. A.Szepietowski: Turing machines with sublogarithmic space, Lecture Notes in Computer Science 843, Springer-Verlag, 1994, 115pp. 2. M.Liskiewicz, R.Reischuk: Computing with sublogarithmic space. In L.A.Hemaspaandra, A.L.Selman (eds.), Complexity theory retrospective II, Springer-Verlag, 1997 3. K.Inoue, A.Ito, I.Takanami: A relationship between nondeterministic Turing machines and 1-inkdot Turing machines with small space, Information Processing Letters, North-Holland, 1992, Vol.43, No.4, pp.225-227 4. K.Inoue, A.Ito, I.Takanami: A note on 1-inkdot alternating Turing machines with small space, Theoretical Computer Science, Elsevier, 1994, Vol.127, No.1, pp.171-179 5. M.Liskiewicz, R.Reischuk: The sublogarithmic alternating space world, SIAM J. of Computing, 1996, Vol.25, No.4, pp.828-861 6. A.Ito, K.Inoue, I.Takanami, Y.Wang: The Effect of Inkdots for 2-Dimensional Automata, International J. of Pattern Recognition and Artificial Intelligence, World Scientific, 1995, Vol.9, No.5, pp.777-796 7. K.Inoue, A.Ito, I.Takanami, T.Yoshinaga: A Note on Multi-Inkdot Nondeterministic Turing-Machines with Small Space, Information Processing Letters, Elsevier, 1993, Vol.48, No.6, pp.285-288 8. C.Mereghetti and G.Pighizzini: Optimal simulations between unary automata, SIAM J. of Computing, 2001, Vol.30, No.6, pp.1976-1992 9. J.L.Xu, Y.X.Liu, T.Yoshinaga: A note on non-closure property of sublogarithmic space-bounded 1-inkdot alternating pushdown automata with only existential (universal) states, J. Comput. Sci. Technol. (J. of Computer Science and Technology), 2006, Vol.21, No.6, pp.979-983 10. T.Makino, H.Okabe, S.Taniguchi, M.Sakamoto, K.Inoue: Three-dimensional multiinkdot automata, Artificial Life and Robotics, 2005, Vol.9, No.2, pp.99-101

ADC – V.Geffert: Tally versions of the Savitch and Immerman-Szelepcsenyi theorems for sublogarithmic space, SIAM J. of Computing, 1993, Vol.22, No.1, pp.102-113: 19 ohlasov WoK 1. M.Liskiewicz, R.Reischuk: Computing with sublogarithmic space. In L.A.Hemaspaandra, A.L.Selman (eds.), Complexity theory retrospective II, Springer-Verlag, 1997 2. A.Matescu, A.Salomaa: Aspects of classical language theory. In G.Rozenberg, A.Salomaa (eds.), Handbook of formal languages, Vol.I: Word, language, grammar. Springer-Verlag, 1997 3. C.Damm, M.Holzer: Inductive counting for width-restricted branching programs, Information and Computation, Academic Press, 1996, Vol.130, No.1, pp.91-99 4. M.Liskiewicz, R.Reischuk: The sublogarithmic alternating space world, SIAM J. of Computing, 1996, Vol.25, No.4, pp.828-861 5. C.Mereghetti and G.Pighizzini: A remark on middle space bounded alternating Turing machines, Information Processing Letters, Elsevier, 1995, Vol.56, No.4, pp.229-232 6. A.Szepietowski: Weak and strong one-way space complexity classes, Information Processing Letters, Elsevier, 1998, Vol.68, No.6, pp.299-302 7. C.Mereghetti and G.Pighizzini: Optimal simulations between unary automata, SIAM J. of Computing, 2001, Vol.30, No.6, pp.1976-1992 8. G.Pighizzini, J.Shallit, M.-W.Wang: Unary context-free grammars and pushdown automata, descriptional complexity and auxiliary space lower bounds, J. Computer and System Sciences, 2003, Vol.65, No.2, pp.393-414 9. G.Pighizzini: Unary language concatenation and its space complexity, Proc.of CIAA 2000 (Confer. on Implementation and Application of Automata), Lecture Notes in Computer Science, Springer-Verlag, 2001, Vol.2088, pp.252-262 10. C.Mereghetti: Testing the descriptional power of small Turing machines on nonregular language acceptance, Internat. J. of Foundations of Computer Science, 2008, Vol.19, No.4, pp.827-843

ADC – V.Geffert, J.Katajainen, T.Pasanen: Asymptotically efficient in-place merging, Theoretical Computer Science, Elsevier, 2000, Vol.237, pp.159-181: 25 ohlasov WoK 1. J.Ellis, M.Markov: In situ, stable merging by way of the perfect shuffle, Computer J., Oxford Univ. Press, 2000, Vol.43, No.1, pp.40-53 2. Jingchao Chen: Optimizing a stable in-place merging, Theoretical Computer Science, Elsevier, 2003, Vol.302, pp.191-210 3. J.-C.Chen: A simple algorithm for in-place merging, Information Processing Letters, 2006, Vol.98, No.1, pp.34-40 4. L.A.Hemaspaandra, P.Mukherji, T.Tantau: Context-free languages can be accepted with absolutely no space overhead, Information and Computation, 2005, Vol.203, No.2, pp.163-180 5. J.Vahrenhold: Line-segment intersection made in-place, Computational Geometry-Theory and Applications, Elsevier, 2007, Vol.38, No.3, pp.213-230 6. P.Bose, A.Maheshwari, P.Morin, J.Morrison, M.Smid, J.Vahrenhold: Space-efficient geometric divide-and-conquer algorithms, Computational Geometry-Theory and Applications, Elsevier, 2007, Vol.37, No.3, pp.209-227 7. J.Vahrenhold: An in-place algorithm for Klee's measure problem in two dimensions, Information Processing Letters, 2007, Vol.102, No.4, pp.169-174 8. P.S.Kim, A.Kutzner: Stable minimum storage merging by symmetric comparisons, Proc.of ESA 2004 (Eur. Symp. Algorithms), Lecture Notes in Computer Science, Springer-Verlag, 2004, Vol.3221, pp.714-723 9. H.Blunck, J.Vahrenhold: In-place algorithms for computing (Layers of) maxima, Algorithmica (New York), 2010, Vol.57, No.1, pp.1-21 10. M.E.Dalkilic, E.Acar, G.Tokatli: A simple shuffle-based stable in-place merge algorithm, Proc. of WCIT-2010 (World Conference on Inrofmation Technology 2010), Procedia Computer Science, 2011, Vol.3, pp.1049-1054

ADC – V.Geffert, A.Badr, I.Shipman: Hyper-minimizing minimized deterministic finite state automata, RAIRO - Theoretical Informatics and Applications, EDP Sciences, 2009, Vol.43, pp.69-94 (DOI: 10.1051/ita:2007061) : 13 ohlasov WoK 1. M.Holzer, A.Maletti: An O(n log n) algorithm for hyper-minimizing states in a (minimized) deterministic automaton, Proc. of CIAA 2009 (Confer. on Implementation and Application of Automata), Lecture Notes in Computer Science 5642, Springer-Verlag, 2009, pp.4-13 2. M.Holzer, A.Maletti: An n.log n algorithm for hyper-minimizing a (minimized) deterministic automaton, Theoretical Computer Science, Elsevier, 2010, Vol.411, No.38-39, pp.3404-3413 3. M.Holzer, S.Jacobi: From equivelence to almost-equivalence and beyond -- minimizing automata with errors, Proc. of DLT 2012 (Developments in Language Theory), Lecture Notes in Computer Science 7410, Springer-Verlag, 2012, pp.190-201 4. A.Jez, A.Maletti: Hyper-minimization for deterministic tree automata, Proc. of CIAA 2012 (Conference on Implementation and Application of Automata), Lecture Notes in Computer Science, 7381, Springer-Verlag, 2012, pp.217-228 5. H.Björklund, W.Martens: The tractability frontier for NFA minimization, J. Computer and System Sciences, 2012, Vol.78, No.1, pp.198-210 6. A.Szepietowski: Closure properties of hyper-minimized automata, RAIRO - Theoretical Informatics and Applications, 2011, Vol.45, No.4, pp.459-466 7. A.Maletti, D.Quernheim: Optimal hyper-minimization, Internat. J. Foundations of Computer Science, 2011, Vol.22, No.8, pp.1877-1891 8. P.Gawrychowski, A.Jez, A.Maletti: On minimising automata with errors, Proc. of MFCS 2011 (Mathematical Foundations of Computer Science), Lecture Notes in Computer Science, 6907, Springer-Verlag, 2011, pp.327-338 9. A.Jez, A.Maletti: Computing all ℓ-cover automata fast, Proc. of CIAA 2011 (Conference on Implementation and Application of Automata), Lecture Notes in Computer Science, 6807, Springer-Verlag, 2011, pp.203-214 10. A.Maletti: Better hyper-minimization not as fast, but fewer errors, Proc. of CIAA 2010 (Conference on Implementation and Application of Automata), Lecture Notes in Computer Science, 6482, Springer-Verlag, 2011, pp.201-210

IFIP (International Federation for Information Processing) -- Working Group 1.2 on Descriptional Complexity, člen Slovenská informatická spoločnosť, člen Člen redakčnej rady časopisu Tatra Mountains Mathematical Publications

Garant 1.stupňa študijného programu 9.2.1 Informatika Garant 2.stupňa študijného programu 9.2.1 Informatika Garant 3.stupňa študijného programu 9.2.1 Informatika Garant pre uskutočňovanie habilitačných konaní a konaní na vymenúvanie profesorov v odbore 9.2.1 Informatika Spolugarant 1.stupňa študijného programu 9.2.9 Aplikovaná informatika Účasť v skúšobných komisiách uvedených študijných programov. Ovplyvňovanie obsahu a charakteru študijných programov prostredníctvom členstva vo Vedeckej rade PF UPJŠ a Akademickom senáte PF UPJŠ. Predseda odborovej komisie doktorandského štúdia Informatika na PF UPJŠ Člen odborovej komisie doktorandského štúdia Informatika na FMFI UK Bratislava

<FONT FACE="ARIAL" SIZE="2"> Doc. RNDr. DrSc.

<FONT FACE="ARIAL" SIZE=2> - Teória automatov a formálnych jazykov.<BR> - Výpočtová zložitosť.<BR> - Výpočtové modely.<BR>

<FONT FACE="ARIAL" SIZE=2> Výpočtová zložitosť, triedenie, formálne jazyky, pamäťová zložitosť.<BR>

<FONT FACE="ARIAL" SIZE="2"> Doktorandské štúdium 11-01-9 Matematická logika a základy matematiky - školiteľ

<FONT FACE="ARIAL" SIZE="2"> - Redakčná rada Tatra Mountains Mathemat. Publ., člen<BR> - Komisia pre obhajoby PhD prác<BR>         11-01-9 Matematika a základy matematiky<BR>         11-08-9 Teoretická informatika<BR> - Akreditačná komisia SR, pracovná skupina pre informatiku<BR> - European Assoc. Theoret. Computer Science, člen<BR>

<FONT SIZE="2" FACE="ARIAL"> Kombinatorické štruktúry a zložitosť algoritmov, grant VEGA 1/7465/20

<FONT FACE="ARIAL" SIZE=2> - Dipartimento di Scienze dell'Informatione Universitá degli studi di Milano, Italia<BR> - Department of Computing, University of Coppenhagen, Denmark<BR> - Turku Centre for Computer Science, Turku, Finland

<BR><h3>New - not published yet</h3> <P> Linear-time in-place selection in epsilon.n element moves. Submitted.<BR> --- With J.Kollar.<BR> <A HREF="http://cs.science.upjs.sk/publikacie/geffert/select.ps">Download .PS file</A> </P> <P> Sorting with O(n.log n) comparisons and O(n) transports, in-place, in the worst case, simultaneously. Submitted. </P> <P> Converting two-way nondeterministic unary automata into simpler automata. To appear in <i>Theoret. Comput. Sci.</i>.<BR> --- With C.Mereghetti and G.Pighizzini. </P> <P> Translation of binary regular expressions into nondeterministic epsilon-free automata with O(n.log n) transitions. To appear in <i>J. Comput. Syst. Sci.</i> </P> <P> Space hierarchy theorem revised. To appear in <i>Theoret. Comput. Sci.</i>. </P> <P> Refinement of the alternating space hierarchy. To appear in <i>Computing and Informatics.</i>.<BR> --- With N.Popely. </P> <BR><h3>Formal languages and automata</h3> <P> A representation of recursively enumerable languages by two homomorphisms and a quotient. <i>Theoret. Comput. Sci.</i>, 62, 235-49, 1988. </P> <P> Grammars with context dependency restricted to synchronization. <i>Proc. Math. Found. Comput. Sci.</i>, vol. 233 of <i>Lect. Notes Comput. Sci.</i>, pp.370-378. Springer-Verlag, 1986. </P> <P> Normal forms for phrase-structure grammars. <i>RAIRO Inform. Theor.</i>, 25, 473-96, 1991. (Conference version: Context-free-like forms for the phrase-structure grammars. <i>Proc. Math. Found. Comput. Sci.</i>, vol. 324 of <i>Lect. Notes Comput. Sci.</i>, pp.309-17. Springer-Verlag, 1988). </P> <P> How to generate languages using only two pairs of parentheses. <i>J. Inform. Process. Cybernet. (EIK)</i>, 27, 303-15, 1991. </P> <P> Converting two-way nondeterministic unary automata into simpler automata. <i>Proc. Math. Found. Comput. Sci.</i>, vol. 2136 of <i>Lect. Notes Comput. Sci.</i>, pp.398-407. Springer-Verlag, 2001. (Journal version to appear in <i>Theoret. Comput. Sci.</i>).<BR> --- With C.Mereghetti and G.Pighizzini. </P> <P> Translation of binary regular expressions into nondeterministic epsilon-free automata with O(n.log n) transitions. To appear in <i>J. Comput. Syst. Sci.</i> </P> <BR><h3>Computational complexity - Space bounded computations</h3> <P> Nondeterministic computations in sublogarithmic space and space constructibility. <i>SIAM J. Comput.</i>, 20, 484-98, 1991. (Conference version: <i>Proc. Internat. Colloq. Automata, Languages, & Programming</i>, vol. 443 of <i>Lect. Notes Comput. Sci.</i>, pp.111-24. Springer-Verlag, 1990). </P> <P> Tally versions of the Savitch and Immerman-Szelepcsenyi theorems for sublogarithmic space. <i>SIAM J. Comput.</i>, 22, 102-13, 1993. </P> <P> A lower bound for the nondeterministic space complexity of context-free recognition. <i>Inform. Process. Lett.</i>, 42, 25-27, 1992.<BR> --- With H.Alt and K.Mehlhorn. </P> <P> Sublogarithmic \Sigma_2-SPACE is not closed under complement and other separation results. <i>RAIRO Inform. Theor.</i>, 27, 349-66, 1993. </P> <P> A hierarchy that does not collapse: Alternations in low level space. <i>RAIRO Inform. Theor.</i>, 28, 465-512, 1994. </P> <P> Bridging across the log(n) space frontier. <i>Inform. & Comput.</i>, 142, 127-58, 1998. (Conference version: <i>Proc. Math. Found. Comput. Sci.</i>, vol. 969 of <i>Lect. Notes Comput. Sci.</i>, pp.50-65. Springer-Verlag, 1995). </P> <P> Sublogarithmic bounds on space and reversals. <i>SIAM J. Comput.</i>, 28, 325-40, 1999.<BR> --- With C.Mereghetti and G.Pighizzini. </P> <P> A variant of inductive counting. <i>Theoret. Comput. Sci.</i>, 237, 465-75, 2000. </P> <P> A space lower bound for acceptance by one-way \Pi_2-alternating machines. <i>RAIRO Inform. Theor.</i>, 34, 357-72, 2000.<BR> --- With N.Popely. </P> <P> Space hierarchy theorem revised. <i>Proc. Math. Found. Comput. Sci.</i>, vol. 2136 of <i>Lect. Notes Comput. Sci.</i>, pp.387-97. Springer-Verlag, 2001. (Journal version to appear in <i>Theoret. Comput. Sci.</i>). </P> <P> Refinement of the alternating space hierarchy. To appear in <i>Computing and Informatics.</i>.<BR> --- With N.Popely. </P> <BR><h3>Computational complexity - Miscellaneous</h3> <P> A speed-up theorem without tape compression. <i>Theoret. Comput. Sci.</i>, 118, 49-65, 1993. (Conference version: <i>Proc. Math. Found. Comput. Sci.</i>, vol. 452 of <i>Lect. Notes Comput. Sci.</i>, pp.285-91. Springer-Verlag, 1990). </P> <P> A communication hierarchy of parallel computations. <i>Theoret. Comput. Sci.</i>, 198, 99-130, 1998. </P> <BR><h3>Sorting algorithms</h3> <P> Asymptotically efficient in-place merging. <i>Theoret. Comput. Sci.</i>, 237, 159-81, 2000.<BR> --- With J.Katajainen and T.Pasanen. </P>