Skip Navigation Linkstheoretical-computer-science

Theoretical Computer Science

Traditional and novel approaches to define languages and establish their properties, including various grammars and automata. New computational paradigms, including interval-valued and DNA computing. 

PhD Thesis

  • Madeeha Fatima: Transduced-Input Finite Automata with Translucent Letters, EMU, January 2020.
  • László Hegedüs: Unconventional Models in the Theory of Formal Languages and Automata, University of Debrecen, Hungary, February, 2017

MS Thesis

  • MohammadReza Saadat: Cellular Automata in the Triangular Grid, EMU, January 2016 .
  • Awe Ayodeji Samson: 2 Head Pushdown Automata, EMU, January 2015.


  • There were various bilateral projects with, e.g., Kyoto, Japan and Kassel, Germany


  • Géza Horváth, Benedek Nagy: Formal Languages and Automata Theory, Typotex, Budapest, Hungary, 2014.
  • Tamás Herendi, Benedek Nagy: Parallel Approach of Algorithms, Typotex, Budapest, Hungary 2014.

 Edited issues

  • Henning Bordihn, Benedek Nagy, György Vaszil: RAIRO - Theoretical Informatics and Applications (RAIRO: ITA), Volume 52/No 2-3-4 (April–December 2018): Special Issue: NON-CLASSICAL MODELS OF AUTOMATA AND APPLICATIONS VIII.
  • Jérôme Durand-Lose, Jarkko Kari, Benedek Nagy: Fundamenta Informaticae - Volume 155, issue 1-2 Special Issue on Machines, Computations and Universality (MCU 2015) .
  • Henning Bordihn, Rudolf Freund, Benedek Nagy, György Vaszil: Eighth Workshop on NonClassical Model of Automata and Applications, NCMA 2016, August 29th-30th, Debrecen, Hungary,, Austrian Computer Society, BAND 321 (2016).
  • Jérôme Durand-Lose, Benedek Nagy: Machines, Computations and Universality, MCU 2015, LNCS 9288, Springer.


  • Benedek Nagy: On The Membership Problem of Permutation Grammars - A direct Proof of NPcompleteness, International Journal of Foundations of Computer Science, accepted for publication.
  • Benedek Nagy, Shaghayegh Parchami: On deterministic sensing 5' → 3' Watson–Crick finite automata: a full hierarchy in 2detLIN, Acta Informatica, accepted for publication.
  •  Madeeha Fatima, Benedek Nagy: Transduced-Input Automata with Translucent Letters, Comptes rendus de l'Académie bulgare des Sciences 73/1, (2020), 33-39. 
  • Mani Mehraei, Benedek Nagy, Nimet Ilke Akcay, Sükrü Tüzmen: Potential Therapeutic Modalities of Reawakening Fetal Hemoglobin Simulated by Reaction Systems, Acta Polytechnica Hungarica 16/3 (2019), 19-35.
  •  MohammadReza Saadat, Benedek Nagy: Cellular Automata Approach to Mathematical Morphology in the Triangular Grid, Acta Polytechnica Hungarica (Journal of Applied Sciences) 15/6 (2018), 45-62. 
  • Dávid Angyal, Benedek Nagy, György Vaszil: On the Complexity of a Mildly Context-Sensitive Language Class, Journal of Automata, Languages and Combinatorics 23/1-3 (2018), 5-18. 
  • Benedek Nagy, Sándor Vályi: A Shift-free Characterization of NP within Interval-valued Computing. Fundam. Inform. 155 (2017), 187-207.
  •  László Hegedüs, Benedek Nagy: On periodic properties of circular words, Discrete Mathematics 339/3 (2016), 1189-1197. 
  •  Benedek Nagy, László Kovács: Finite Automata with Translucent Letters applied in Natural and Formal Language Theory, LNCS Transactions on Computational Collective Intelligence 17, LNCSTCCI XVII, LNCS 8790 (Springer), (2014), 107-127. 

 Invited conference talk and paper

  • Benedek Nagy: Union-Freeness, Deterministic Union-Freeness and Union-Complexity (invited paper), M. Hospodár et al. (Eds.): DCFS 2019: Descriptional Complexity of Formal Systems, Lecture Notes in Computer Science, LNCS 11612 (2019), 46-56.

Conference presentations

  • Madeeha Fatima, Benedek Nagy: On the Combination of Finite State Transducers and Finite Automata with Translucent Letter, IS2019-MATCOS 2019: Proceedings of the 22nd International Multiconference INFORMATION SOCIETY, Volume I: Middle-European Conference on Applied Theoretical Computer Science, Koper, Slovenia (2019), 27-30. 
  • Benedek Nagy, Zita Kovács: On simple 5'→3' sensing Watson-Crick finite-state transducers, NCMA 2019: Eleventh Workshop on Non-Classical Models of Automata and Applications, Valencia, Spain, 155-170. 
  • Benedek Nagy, Friedrich Otto: Two-Head Finite-State Acceptors with Translucent Letters, SOFSEM 2019: 45th International Conference on Current Trends in Theory and Practice of Computer Science, Lecture Notes in Computer Science, LNCS 11376 (2019), 406-418. 
  •  Radim Kocman, Benedek Nagy, Zbynek Krivka, Alexander Meduna: A jumping 5' → 3' WatsonCrick finite automata model, NCMA 2018: Tenth Workshop on Non-Classical Models of Automata and Applications, Kosice, Slovakia, 117-132.
  • Benedek Nagy, Sándor Vályi: An Extension of Interval-Valued Computing Equivalent to RedGreen Turing Machines, MCU 2018: 8th International Conference on Machines, Computations, and Universality, LNCS 10881 (2018), 137-152.
  • Shaghayegh Parchami, Benedek Nagy: Deterministic Sensing 5' → 3' Watson-Crick Automata Without Sensing Parameter, UCNC 2018: 17th International Conference on Unconventional Computation and Natural Computation, LNCS 10867 (2018), 173-187. 
  •  Benedek Nagy, Shaghayegh Parchami, Hamid Mir-Mohammad-Sadeghi: A New Sensing 5'->3' Watson-Crick Automata Concept, AFL 2017: Proceedings 15th International Conference on Automata and Formal Languages, EPTCS 252 (2017), 195-204. 
  • Dávid Angyal, Benedek Nagy: An extension of the LR parsing algorithm for two-head pushdown automata, NCMA 2017: Ninth Workshop on Non-Classical Models of Automata and Applications, Prague, 71-86. 
  • Dávid Angyal, Benedek Nagy: On Linear Grammars with Exact Control, MATCOS-2016: MiddleEuropean Conference on Applied Theoretical Computer Science (held in conjunction with the 19th Multi-Conference on Information Society, Ljubljana), Koper, Slovenia, October 2016, 95-98.
  •  Gergely T. Bálint, Benedek Nagy: Finiteness of Chain-code Picture Languages on the Triangular Grid, ISPA 2015: 9th International Symposium on Image and Signal Processing and Analysis, Zagreb, Croatia, 310-315. (IEEE).
  •  Benedek Nagy, Sándor Vályi: A Characterization of NP within Interval-Valued Computing, MCU 2015: 7th Conference on Machines, Computations and Universality, LNCS 9288 (2015), 164-179.

 Contact Person: Prof. Dr. Benedek Nagy

EMU Websites