Prof. Dr. Benedek Nagy

Further Research Activity

Logic, Puzzles, Combinatorics, Graphs, Diagrams, Artificial Intelligence, Game theory, Soft Computing

Keywords: Artificial Intelligence. Graphs. Logic, logical puzzles, logical games. Games, game theory.
Visual Computing. Diagrams. Genetic Algorithms. Simulated annealing. Fuzzy logic.
Combinatorics. Graphs.

Research partners:

Gerard Allwein (Naval Research Laboratory, US)
Márk Kósa (University of Debrecen, Hungary)
Tibor Lukic (University of Novi Sad, Serbia)
Elisa Moisi (University of Oradea, Romania)
János Pánovics (University of Debrecen, Hungary)
Hans-Jörg Kreowski (Bremen University, Germany)
Sándor Vályi (College of Nyíregyháza, Hungary)

Artificial Intelligence.

In artificial intelligence, during problem solving choosing the right representation of the problem may be a cardinal point. In [ia7,ic20] various representations of a simple problem are presented and it is shown how much the efficiency of the search algorithms are influenced with these representations using backtracking and breadth-first algorithms.
A paper is also written about the teaching method and requirements of the laboratory courses related to the introductory course of Artificial Intelligence in 2002 [hc2].

Research papers:

  • (ic20) with M. Kósa and J. Pánovics, Megoldáskereső algoritmusok hatékonyságának vizsgálata az állapottér-reprezentáció függvényében (Performance Analysis of Search Algorithm Depending on the State Space Representation) (2006), SzámOkt 2006 Számítástechnika az oktatásban XVI. nemzetközi konferencia, 16th International Conference in Computer Science and Education, Sovata, Romania, 76-81.
  • (ia7) with M. Kósa and J. Pánovics: Performance Analysis of Search Algorithm Depending on the State Space Representation, 6th MaCS, 6th Joint Conference on Mathematics and Computer Science, July 2006, Pécs, Hungary
  • (hc2) with Magda Várterész, Márk Kósa and János Pánovics, A mesterséges intelligencia tárgy bevezető kurzusának gyakorlatai a Debreceni Egyetemen (Laboratories of artificial intelligence I course at University of Debrecen) (2002), Conference on Informatics in Higher Education, Debrecen, 1103-1109.

Logic. Many-valued logic, Interval-valued logic. Reasoning. Temporal logic. SAT.

Liar puzzles have been popularized by Raymond Smullyan in several books. A logical and diagrammatic examination of such puzzles in terms of a epistemic truth values is presented in [ij7]. Also, non-monotonic reasoning may occur as new information is learned about a puzzle. A way to think about such non-monotonic reasoning is presented which does not involve the use of a non-monotonic logic but instead utilizes context shifts among static logics. The information coming from the presented diagrams is timeless, it is a monotonic back-bone of the whole non-monotonic knowledge.
The logic of the programming language C, where integers used as logical values is analysed in [ic15]. The logical laws are analysed, this logic is also compared to various many-valued logic systems. It is shown that the logic of C is neither the classical (two-valued) logic, neither a 'classical many-valued system'. The commutative laws are violated because the use of lazy evaluation (when error message is produced in a part of the evaluation of a condition). A three-valued system is proposed to describe the logic of C.
An interval-valued logic system in which the truth values are intervals or sets of disjoint intervals over [0,1] is investigated. A way of reasoning by interval-values over the unit interval [0,1] is presented in [ij20]. Logical inference is visualized by interval-values. Boolean operators are extended to these values in a natural way. Some other useful (non logical) operators are also defined. The way of reasoning by Euler/Venn diagrams works by interval-values as well. Moreover based on the length of the intervals probabilistic and fuzzy reasoning is possible: the simulation of many-valued and fuzzy logic systems (such as Heyting's logic, Belnap's logic, Post's logic, Gödelian logic, Łukasiewicz-type logics and product logic) and some properties of the interval-valued general fuzzy logic are also presented [ic18]. A temporal logic connected to interval-values is shown in [ic30].
It is shown that the set of valid SAT-formulae and n-SAT formulae (for any fixed n) over finite set of variables are regular languages [ij6]. We also construct a deterministic finite automaton to accept the Boolean tautologies in disjunctive normal form. So the language of tautologies in disjunctive normal form is regular as well. Moreover using arbitrary many variables the language of tautologies is not even context-free, but context sensitive.
Boolean programming problems are related to satisfiabilty problem and they are presented later on (logical puzzles and graphs) based on [hj1,ic4].

Research papers:

Logical puzzles.

Everybody knows logical puzzles. For example, some books written by Smullyan contain many of them. In [ic1] a complex program is presented which makes logical puzzles by using some parameters. The program can generate logical puzzles and is able to explain the way of their solution, as well. It can be useful to obtain the ability of logical thinking. These ideas seem to be applicable in e-learning.
See also the next part, where various methods are used to solve puzzles using their graph-representations.

Research papers:

  • (ic1) with Márk Kósa, Logical puzzles (truth-tellers and liars)(2001), ICAI'01, 5th International Conference on Applied Informatics, Eger, Hungary, 105-112.

Logical puzzles and graphs.

Liar puzzles have been popularized by Raymond Smullyan in several books. A strong truth teller as someone who only utters truths and a weak liar as someone who utters at least one false statement. A weak truth teller is someone who utters at least one truth and a strong liar is someone who utters only falsehoods. Various types of these puzzles are represented by graphs, see e.g. [ij5], and are solved by help of graph-transformations. Various types of truth-tellers and liars puzzles, especially SS, SW and SW-L types are presented in [ij5]. In SS-type puzzles (Strong truth-tellers and Strong liars) each person can say only simple statements about a person type. A truth-teller can have only true assertions, and a liar can make only false statements. The graph-representations of these puzzles are presented [ij5,hj2]. The graph of a puzzle has all the information about the puzzle in the case of clear puzzles. Some interesting properties of the possible graphs of puzzles are presented. It is proven that there is no clear SS-type puzzle with a unique solution. We present an algorithm which can provide all possible solutions of a clear puzzle. In the case of non-clear puzzles, we must choose among the possible solutions of the clear puzzle with the same graph.
SW-type (Strong truth-tellers, Weak liars) truth-teller and liar puzzles are also analysed [ij5,ij4,ij16]. In these puzzles each person can utter a sentence about some persons' type and in which he uses only the `and' connective. The graph of a puzzle has all information about the puzzle if we have no other information to solve the puzzle than the statements given (clear puzzles). We analyze the graphs of the possible puzzles. We give some transformations of graphs based on local information, for instance arrow-adding steps. These local steps are very helpful to solve these puzzles. We show an example that we can solve using these local steps. After this, we analyse the global properties of the graphs. We show a special example when the local steps do not help, but the puzzle is solvable by using global information. Finally we show a graph-algorithm which is a combination of local and global information, and show that it can solve the SW-type puzzles [ij4]. In [ij16] WS (Weak truth-tellers, Strong liars) puzzles are also considered by the analogy to SW puzzles. In WS puzzles everybody uses only `or' connective. By duality these puzzles can be translated to SW puzzles, and graph method can solve them.
A logical and diagrammatic examination of WW puzzles (Weak truth-tellers and Weak liars: persons who can say both truth and can lie are Normal people), i.e., KNK puzzles (allowing 4 types of atomic statements: 'A can lie', 'A can say the truth', 'A cannot lie', 'A cannot say the truth' and three types of people: Knights, Normal people, Knaves) in terms of a epistemic truth values is presented in [ij7]. Also, non-monotonic reasoning may occur as new information is learned about a puzzle. A way to think about such non-monotonic reasoning is presented which does not involve the use of a non-monotonic logic but instead utilizes context shifts among static logics. The information coming from the presented diagrams is timeless, it is a monotonic back-bone of the whole non-monotonic knowledge.
Some Boolean programming probelms are closely related to our puzzles [hj1,ic4]. Boolean programming problems are special integer-valued programming problems in which each variable is either 0 or 1. Basic and modified Boole-programming problems are considered. In the basic Boole-programming problems we can write to linear form to our conditions. These conditions are represented in a graph and the problem is solved using this graph. In the modified case our conditions are non-linear, but we can use nearly similar graph representation and solving method. In graph representation we use so-called 'relevant (or critical) edges' to represent the non-linear conditions. We present a general algorithm to get the solutions of these problems [hj1].
Some Boolean programming (0-1 programming) problems and some truth-teller-liar puzzles (using only 'and' connectives) with their relations are presented in [ic4]. Puzzles are translated to Boolean programming problems. The constraints of these problems are equalities and inequalities; they can be written in atomic form. Using these atomic restrictions the graph-representation is constructed. A graph-algorithm is presented to get a/all solution(s) of the presented Boolean programming problems and puzzles, with examples. A version of the algorithm to get the optimal solution was also be given.

Research papers:

Graphs and hypergraphs.

Some results about graphs in formal language theory is presented. The concepts of the graph of generative grammars and Lindenmayer systems are investigated [ic39,bc5]. These special and-or graphs represent all information about the grammar. For regular grammars the new concept is equivalent to the finite automata. In context-free case it is an extension of the dependency graph. Relation to programmed grammars (using context-free rules) is also analysed. Moreover the graph of the grammar is more general; it can be defined for generative grammars to any recursively enumerable languages containing all information of the grammar. By the help of tokens the new concept can effectively be used to follow derivations. Moreover parallel derivations can be simulated in non-linear grammars. While in regular and linear case only sequential derivations are going, in context-free case a kind of maximal parallelism can be involved. In context-sensitive case communication/synchronization is also needed in these processes. The Lindenmayer systems are well-known parallel rewriting systems; our concept is defined and used for various Lindenmayer systems. Especially the main difference is not in the graph form, but in the simulation process.
Programmed grammars, one of the most important and well investigated classes of grammars with context-free rules and a mechanism controlling the application of the rules, can be described by graphs. We investigated whether or not the restriction to special classes of graphs restricts the generative power of programmed grammars with erasing rules and without appearance checking, too [ij23]. It is obtained that Eulerian, Hamiltonian, planar and bipartite graphs and regular graphs of degree at least three are pr-universal in that sense that any language which can be generated by programmed grammars (with erasing rules and without appearance checking) can be obtained by programmed grammars where the underlying graph belongs to the given special class of graphs, whereas complete graphs, regular graphs of degree 2 and backbone graphs lead to proper subfamilies of the family of programmed languages.
In [ij17] a subclass of the regular languages is analysed, namely the unionfree regular languages. These languages can be given by regular expressions without the operation union. In a union-free language the words look like each other, each word contains the so-called “backbone" word of the language in scattered way. The family of special type of finite automata is investigated to recognize these languages. These automata are the 1-cycle-free-path-automata: in these class from each state there is exactly one cycle-free path going to the final state, i.e., the automata have special graphs: there are no alternative (cycle-free) paths from a state to another state.
(Hyper)graph generation: Contextual hypergraph grammars have been introduced as generalization of total contextual string grammars. We study the position of the class of languages generated by contextual hypergraph grammars in comparison with graph languages generated by hyperedge replacement grammars and double-pushout hypergraph grammars. Moreover, several examples show the potential of the new class of grammars [ij19]. Various trees are computed and self-assembly is modelled in this framework [ic27,ic29].

Research papers:

  • (ij23) The power of programmed grammars with graphs from various classes, Journal of Applied Mathematics and Computing - JAMC 22 (2006), 21-38. (co-authors: M. Barbaiani, C. Bibire, J. Dassow, A. Delaney, Sz. Fazekas, M. Ionescu, G. Liu and A. Lodhi)
  • (ij19) Contextual Hypergraph Grammars - A New Approach to the Generation of Hypergraph Languages, DLT 2006, Tenth International Conference DEVELOPMENTS IN LANGUAGE THEORY, Santa Barbara, CA, USA, 327-338. (Lecture Notes in Computer Science, LNCS 4036, co-authors: A.-H. Dediu, R. Klempien-Hinrichs and H.-J. Kreowski)
  • (ic29) with Adrian-Horia Dediu, Self-assembling tilings of Boolean tree-like circuits modelled by contextual hypergraph grammars (2007), NSIP2007, IEEE International Workshop on Nonlinear Signal and Image Processing, Bucharest, Romania, 150-153.
  • (ic27) with Adrian-Horia Dediu, Computing Trees with Contextual Hypergraph Grammars (2007), ForLing2007-FCT2007, International Workshop on NON-CLASSICAL FORMAL LANGUAGES IN LINGUISTICS, Budapest, Hungary, 39-53.
  • (ij17) Union-free languages and 1-cycle-free-path-automata, Publicationes Mathematicae Debrecen 68 (2006), 183-197.
  • (bc5) Graphs of Grammars – Derivations as Parallel Processes, in: Computational Intelligence in Engineering, Studies in Computational Intelligence - SCI 313, Springer (2010), 1-13.
  • (ic39) Graphs of generative grammars (2009), 10th International Symposium of Hungarian Researchers on Computational Intelligence and Informatics, Budapest, Hungary, 339-350.

Game theory, games.

In [ij31], games with chance nodes are analysed. The evaluation of these game trees uses the expectiminimax algorithm. We present pruning techniques involving random effects. The gamma-pruning aims at increasing the efficiency of expectiminimax (analogously to alpha-beta pruning and the classical minimax). Some interesting properties of these games are shown: for instance, a game without draw can be fair. A fair game may not be fair any more if it is played iteratively. To handle these phenomena, the use of additional indicators, such as the minimal guaranteed outcome value, is suggested.
In [ic8] multiplayer games with few participants are analysed. In these games the number of participants is less than in the usual n-player games. For this reason we use a variation of the methods which are used for the 2-player zero-sum strategic games. Some definitions are given analogously and in some cases more definitions are needed because loosing the special case of 2 persons. The game-trees are built with the so-called expected outcome-vectors. The situation - comparing to the 2-player games - looks more like the non-zero-sum games, because more values are needed to calculate the `optimal' strategy. Assuming at least 3 players in a game it is not guaranteed that any of the players has a non-loosing strategy. Some methods (based on the well-known minimax algorithm) are presented for evaluation of these games. Methods to help for making decisions for the players are also shown both with partial and full evaluation of the game-tree. The question of `rational strategy' is interesting in these games, as for example at the prisoner's dilemma.
The terms of `new media', `hypermedia', `integral media' and `interactive multimedia' have been appeared around 2000. This possibility is an effective tool of environmental education. We can use it as simulation of learning experiments. We need some interdisciplinary knowledge such as game psychology, culture, economy and education. The techniques of learning must be open for young generation. We must know their habits to motivate them to learn. The young more like play than work. This is the reason why we try to use games to teach. In the pilot study (which is a pedagogical feedback experiment) we analyse how the students play computer games and how these games cause development skills and personal growth. The aim of using multimedia in learning is that the students will able to get information and make decisions. In our opinion, some computer games help to develop critical thinking [hc4,ic14]. By our hypothesis, the psychological form of the games and the human-computer interaction (such as, for instance, the usage of the mouse) can be connected to the system of connections of personal psychology. Grouping the various types of games gives a possibility to develop skills. In this point, we can make a difference between the genders of the players due to their biological and social differences [ia9].

Research papers:

Visual computing.

We have already mentioned graphs-based visual algorithms for puzzle solving. Now other way of visual computaions are presented: the interval-valued computations. Intervals are very common things (draws restricted to one dimension). In interval-valued computing paradigm the basic data unit is the interval-value that is a finite union of subintervals (components) over the unit interval [0,1). Logical operations are straightforward generalizations of the classical operations, moreover shift operations is also used to carry some pieces of information to other parts of the unit interval. The product operation zoom an interval-value to the components of an interval-value. It is shown that, among other hard problems, the PSPACE-complete qSAT is decidable by a linear/polynomial interval-valued computation in a visual way [ij33,ij56,ic56]. For more details on this paradigm see also the page of R.G. of Theoretical Computer Science and Computing Paradigms.

Research papers:

  • (ij56) Prime factorization by interval-valued computing, Publicationes Mathematicae Debrecen, accepted (co-author: S. Vályi)
  • (ij33) Interval-valued computations and their connection with PSPACE, Theoretical Computer Science - TCS 394/3 (2008), 208-222. (co-author: S. Vályi)
  • (ij20) Reasoning by Intervals, Diagrams 2006, Fourth International Conference on the Theory and Application of Diagrams, Stanford, CA, USA, 145-147. (Lecture Notes in Computer Science - Lecture Notes in Artificial Intelligence, LNCS-LNAI 4045)
  • (ic56) with S. Vályi: Computing discrete logarithm by interval-valued paradigm, (Benedikt Loewe, Glynn Winskel, eds.), Proceedings 8th Workshop on Developments in Computational Models - DCM 2012, Cambridge, England, Electronic Proceedings in Theoretical Computer Science - EPTCS, to appear
  • (ic40) Effective Computing by Interval-values, INES 2010, 14th IEEE International Conference on Intelligent Engineering Systems 2010, Las Palmas of Gran Canaria, Spain, 91-96.
  • (ic34) with Á. Tajti, Solving Tripartite Matching by Interval-valued Computation in Polynomial Time (2008), CiE 2008, Fourth Conference on Computability in Europe: Logic and Theory of Algorithms (Local Proceedings), Athens, Greece, 435-444.
  • (ic30) with Sándor Vályi, Visual reasoning by generalized interval-values and interval temporal logic (2007), VLL 2007, Workshop on Visual Languages and Logic, - VL/HCC 07, IEEE Symposium on Visual Languages and Human Centric Computing, (CEUR Workshop Proceedings Vol-274), Coeur d'Aléne, Idaho, USA, 13-26.
  • (ic28) with Sándor Vályi, Interval-valued computing as a visual reasoning system (2007), DMS2007, The Thirteenth International Conference on Distributed Multimedia Systems - VLC'2007, International Workshop on Visual Languages and Computing, San Francisco, CA, USA, 247-250.
  • (ic24) with Sándor Vályi, Interval-valued computations without the product operator (2007), ICAI 2007, 7th International Conference on Applied Informatics, Eger, Hungary, volume I. 83-90.
  • (ic19) with Sándor Vályi, Solving a PSPACE-complete problem by a linear interval-valued computation, CiE 2006, Computability in Europe 2006: Logical Approaches to Computational Barriers, University of Wales Swansea, UK, 216-225.
  • (ic18) A general fuzzy logic using intervals (2005), 6th International Symposium of Hungarian Researchers on Computational Intelligence, Budapest, Hungary, 613-624.
  • (ic13) An interval-valued computing device (2005), CiE 2005, "Computability in Europe": New Computational Paradigms, Amsterdam, Netherlands, 166-177.

DNA-Prolog.

A natural way of executing Prolog programs by DNA computations is presented in [ic41]. The philosophy of the programming language Prolog is very close to the classical idea of DNA computations. Based on Adleman's groundbreaking experiment a system is presented that gives answer to simple Prolog queries.

Research papers:

  • (41) with P. Battyányi: DNA-Prolog, CiE 2010: 6th Conference on Computability in Europe: Programs, Proofs, Processes, Ponta Delgada, Azores, Portugal, (Abstract and Handout Booklet), 281-290.

Parallelism in computations, parallel computing.

The concepts of the graph of generative grammars and Lindenmayer systems are investigated [bc5]. These special and-or graphs represent all information about the grammar. For regular grammars the new concept is equivalent to the finite automata. In context-free case it is an extension of the dependency graph. We also analyze how it is related to programmed grammars (using context-free rules). Moreover the graph of the grammar is more general; it can be defined for generative grammars to any recursive enumerable languages containing all information of the grammar. By the help of tokens the new concept can effectively be used to follow derivations. Moreover parallel derivations can be simulated in non-linear grammars. While in regular and linear case only sequential derivations are going, in context-free case a kind of maximal parallelism can be involved. In context-sensitive case communication/synchronization is also needed in these processes. The Lindenmayer systems are well-known parallel rewriting systems; our concept also can be defined and used for various Lindenmayer systems. Especially the main difference is not in the graph form, but in the simulation process.
The appearance and the role of the parallelism is analysed in some algorithms and approaches of problem solving in Artificial Intelligence and in Computational Intelligence. Well-known that parallel algorithms can solve the problems in a more effective way than the sequential algorithms. Two basic types of parallelism are presented. The so-called 'or'-parallelism uses the parallelism to do brute-force search. In the so-called 'and'-parallelism the solution is built up by several parts given by the parallel branches of the computation [ic22]. DNA and membrane computing have also been considered, both as theoretical models and as problem solving devices. The basic motivation behind these models of natural computing is using parallelism to make hard problems tractable. The concept of parallelism is analysed: it is shown that parallelism has very different meanings in these models: both 'or-parallelism' and 'and-parallelism' appear [ic25,ij57].

Research papers:

Soft Computing.

Soft computing techiques uses fuzzy values, genetic or other evolutionary approaches, simulated annealing, etc. or their combinations. Below we list some of our results connected to this field.

Genetic algorithms. Evolutionary algoritms.

Genetic algorithms are frequently used for optimization. In [ic52],the Painting problem is solved by using some specific knowledge about the problem itself and by interval-values to show that they improve the effectiveness of a genetic algorithm.
A memetic algorithm is presented in [ic49] for the reconstruction of binary images represented on a triangular grid. Crossover and mutation operators are introduced on this grid. A discrete tomography algorithm is proposed which uses a switch and compactness operators for the triangular grid to improve the quality of the image in each generation. The algorithm was tested on some images for its effectiveness.
In [ic55] other evolutionary algorithm are used for the reconstruction of binary images represented on the triangular grid.

Research papers:

  • (ic55) Reconstruction of Binary Images Represented on Equilateral Triangular Grid Using Evolutionary Algorithms, Advances in Intelligent Systems and Computing - AISC 195 (Springer): Soft Computing Applications (2012), 561-571. (co-authors: E. V. Moisi, V. I. Cretu)
  • (ic52) with L. Zámbó: Optimization of the Painting Problem by a Genetic Approach using Interval-values, CINTI 2011, 12th IEEE International Symposium on Computational Intelligence and Informatics, 127-132.
  • (ic49) with E. Moisi: Discrete Tomography on the Triangular Grid: a Memetic Approach, 7th International Symposium on Image and Signal Processing and Analysis (ISPA 2011), Dubrovnik, Croatia, 579-584.

Simulated annealing.

This method is based on by analogy with annealing of a metal, to lower the temperature. It can effectively be used in optimization processes. In [ij67] this technique is used for the reconstruction of binary images represented on the triangular grid using three and six projections.

Research papers:

  • (ij67) Energy-Minimization Based Discrete Tomography Reconstruction Method for Images on Triangular Grid, IWCIA 2012, Lecture Notes in Computer Science - LNCS 7655, (2012), 274–284. (co-author: T. Lukic)

Fuzzy logic. Interval-valued logic. Interval-valued computing and combined computations.

Many-valued and fuzzy logic is analysed in [tr7,ic15,ic18]. In [ic15] the logic used in the programming language C is also compared to some many-valued logical systems. In [tr7,ic18] interval-valued logic as a generalisation of various fuzzy logics is presented. Interval-values can be used in reasoning [ij20]. They can also be used to support genetic algorithms [ic52].
The interval-valued computing paradigm based on the interval-valued logic. It is investigated in [ic13]. Some further details and intersting results on/about the interval-valued paradigm can be found on the page about New Computing Paradigms.

Research papers:

    (ic52) with L. Zámbó: Optimization of the Painting Problem by a Genetic Approach using Interval-values, CINTI 2011, 12th IEEE International Symposium on Computational Intelligence and Informatics, 127-132.

  • (ij20) Reasoning by Intervals, Diagrams 2006, Fourth International Conference on the Theory and Application of Diagrams, Stanford, CA, USA, 145-147. (Lecture Notes in Computer Science - Lecture Notes in Artificial Intelligence, LNCS-LNAI 4045)
  • (ic18) A general fuzzy logic using intervals (2005), 6th International Symposium of Hungarian Researchers on Computational Intelligence, Budapest, Hungary, 613-624.
  • (ic15) Many-valued Logics and the Logic of the C Programming Language (2005), ITI 2005, 27th International Conference on Information Technology Interfaces, Cavtat/Dubrovnik, Croatia, 657-662.
  • (ic13) An interval-valued computing device (2005), CiE 2005, "Computability in Europe": New Computational Paradigms, Amsterdam, Netherlands, 166-177.
  • (tr7) Interval-valued logic as generalization of many valued logics, Tech. Rep., Inst. Math. Inf., Univ. Debrecen, 2002/20.

Selected research grants:

  • SegraVis, Bremen University, 2005, 2006
  • Soros scholarship ESSLLI 1996

Contact:

  • Benedek Nagy
  • E-mail: nbenedek (dot) inf (at) gmail

If you have any problem with downloading any of these papers please email me for a copy.

Prof. Dr. Benedek Nagy