Péter Battyányi
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Péter Battyányi has a total of 7 co-authors. Here are the top co-authors by number of shared publications:
- György Vaszil
Department of Computer Science, Faculty of Informatics, University of Debrecen, Debrecen, Hungary
6 shared publications - Karim Nour
LAMA -Équipe LIMD Université Savoie Mont Blanc 73376 Le Bourget du Lac France
3 shared publications - Bogdan Aman
Faculty of Computer Science, Alexandru Ioan Cuza University, Iaşi, Romania
2 shared publications - Gabriel Ciobanu
Institute of Computer Science, Romanian Academy, Iaşi, România
2 shared publications - Attila Bagossy
Department of Computer Science, Faculty of Informatics, University of Debrecen, Debrecen, Hungary
1 shared publication György Vaszil
1 shared publication
Latest Publications
- Open Access
- 13 March 2024
- Published by Springer Nature in Acta Informatica
- Vol. 61 (2) , 161-181
An encoding of the $\lambda $-calculus in the String MultiSet Rewriting calculusIn this paper, we present an encoding of the $$\lambda $$ -calculus in a multiset rewriting system and provide a few applications of the construction. For this purpose, we choose the calculus named String MultiSet Rewriting, which was introduced in Barbuti et al. (Electron Notes Theor Comput Sci 194:19–34, 2008) by Barbuti et al. With the help of our encoding, we give alternative proofs for the standardization and the finiteness of developments theorems in the $$\lambda $$ -calculus.- 13 March 2024
- Published by Springer Nature in Acta Informatica
- Vol. 61 (2) , 161-181
Open AccessAn encoding of the $\lambda $-calculus in the String MultiSet Rewriting calculusIn this paper, we present an encoding of the $$\lambda $$ -calculus in a multiset rewriting system and provide a few applications of the construction. For this purpose, we choose the calculus named String MultiSet Rewriting, which was introduced in Barbuti et al. (Electron Notes Theor Comput Sci 194:19–34, 2008) by Barbuti et al. With the help of our encoding, we give alternative proofs for the standardization and the finiteness of developments theorems in the $$\lambda $$ -calculus. - Open Access
- 6 February 2024
- Published by Springer Nature in Computing
- Vol. 106 (5) , 1321-1334
Solving the SAT problem with the string multiset rewriting calculus
In this paper, we develop computing machinery within the framework of the String Multiset Rewriting calculus (SMSR), as defined by Barbuti et al. [4], to solve the SAT problem in linear time regarding the number of variables of a given conjunctive normal form. This shows that SMSR can be considered a computational model capable of significantly reducing the time requirement of classical decision problems.
- 6 February 2024
- Published by Springer Nature in Computing
- Vol. 106 (5) , 1321-1334
Open AccessSolving the SAT problem with the string multiset rewriting calculus
In this paper, we develop computing machinery within the framework of the String Multiset Rewriting calculus (SMSR), as defined by Barbuti et al. [4], to solve the SAT problem in linear time regarding the number of variables of a given conjunctive normal form. This shows that SMSR can be considered a computational model capable of significantly reducing the time requirement of classical decision problems.
- Open Access
- 9 November 2022
- Published by Springer Nature in Natural Computing
- Vol. 22 (1) , 13-25
On the power of boundary rule application in membrane computing
In this paper, it is investigated how different features of membrane systems can be simulated by the boundary rule application. Firstly, it is discussed how the effect of maximally parallel mode can be obtained by non-cooperative boundary rules applied only in sequential mode, then it is also demonstrated how membrane dissolution, or the application of using promoters and inhibitors can be simulated.
- 9 November 2022
- Published by Springer Nature in Natural Computing
- Vol. 22 (1) , 13-25
Open AccessOn the power of boundary rule application in membrane computing
In this paper, it is investigated how different features of membrane systems can be simulated by the boundary rule application. Firstly, it is discussed how the effect of maximally parallel mode can be obtained by non-cooperative boundary rules applied only in sequential mode, then it is also demonstrated how membrane dissolution, or the application of using promoters and inhibitors can be simulated.
- Open Access
- 1 September 2022
- Published by Cambridge University Press (CUP) in Mathematical Structures in Computer Science
- Vol. 32 (8) , 1066-1098
Normalization in the simply typed -calculus
In this paper, in connection with the program of extending the Curry–Howard isomorphism to classical logic, we study the $\lambda \mu$ -calculus of Parigot emphasizing the difference between the original version of Parigot and the version of de Groote in terms of normalization properties. In order to talk about a satisfactory representation of the integers, besides the usual $\beta$ -, $\mu$ -, and $\mu '$ -reductions, we consider the $\lambda \mu$ -calculus augmented with the reduction rules $\rho$ , $\theta$ and $\varepsilon$ . We show that we need all of these rules for this purpose. Then we prove that, with the syntax of Parigot, the calculus enjoys the strong normalization property even when we add the rules $\rho$ , $\theta$ , and $\epsilon$ , while the $\lambda \mu$ -calculus presented with the more flexible de Groote-style syntax, in contrast, has only the weak normalization property. In particular, we present a normalization algorithm for the $\beta \mu \mu '\rho \theta \varepsilon$ -reduction in the de Groote-style calculus.- 1 September 2022
- Published by Cambridge University Press (CUP) in Mathematical Structures in Computer Science
- Vol. 32 (8) , 1066-1098
Open AccessNormalization in the simply typed -calculus
In this paper, in connection with the program of extending the Curry–Howard isomorphism to classical logic, we study the $\lambda \mu$ -calculus of Parigot emphasizing the difference between the original version of Parigot and the version of de Groote in terms of normalization properties. In order to talk about a satisfactory representation of the integers, besides the usual $\beta$ -, $\mu$ -, and $\mu '$ -reductions, we consider the $\lambda \mu$ -calculus augmented with the reduction rules $\rho$ , $\theta$ and $\varepsilon$ . We show that we need all of these rules for this purpose. Then we prove that, with the syntax of Parigot, the calculus enjoys the strong normalization property even when we add the rules $\rho$ , $\theta$ , and $\epsilon$ , while the $\lambda \mu$ -calculus presented with the more flexible de Groote-style syntax, in contrast, has only the weak normalization property. In particular, we present a normalization algorithm for the $\beta \mu \mu '\rho \theta \varepsilon$ -reduction in the de Groote-style calculus. - Open Access
- 27 October 2020
- Published by Springer Nature in Journal of Membrane Computing
- Vol. 2 (4) , 341-354
Description of membrane systems with time Petri nets: promoters/inhibitors, membrane dissolution, and priorities
We continue the investigations of the connection between membrane systems and time Petri nets by extending the examined class of systems from simple symbol-object membrane systems to more complex cases: rules with promoters/inhibitors, membrane dissolution, and priority relation on the rules. By constructing the simulating time Petri net, we retain one of the main characteristics of the Petri net model; namely, the firings of the transitions can take place in any order, and there is no need to introduce maximal parallelism in the Petri net semantics. Instead, we substantially exploit the gain in computational strength obtained by the introduction of the timing feature for Petri nets.
- 27 October 2020
- Published by Springer Nature in Journal of Membrane Computing
- Vol. 2 (4) , 341-354
Open AccessDescription of membrane systems with time Petri nets: promoters/inhibitors, membrane dissolution, and priorities
We continue the investigations of the connection between membrane systems and time Petri nets by extending the examined class of systems from simple symbol-object membrane systems to more complex cases: rules with promoters/inhibitors, membrane dissolution, and priority relation on the rules. By constructing the simulating time Petri net, we retain one of the main characteristics of the Petri net model; namely, the firings of the transitions can take place in any order, and there is no need to introduce maximal parallelism in the Petri net semantics. Instead, we substantially exploit the gain in computational strength obtained by the introduction of the timing feature for Petri nets.
- Open Access
- 1 January 2020
- Published by American Institute of Mathematical Sciences (AIMS) in AIMS Mathematics
- Vol. 5 (4) , 3702-3713
Normalization proofs for the un-typed μμ'-calculus
A long-standing open problem of Parigot has been solved by David and Nour, namely, they gave a syntactical and arithmetical proof of the strong normalization of the untyped μμ'-reduction. In connection with this, we present in this paper a proof of the weak normalization of the μ and μ'-rules. The algorithm works by induction on the complexity of the term. Our algorithm does not necessarily give a unique normal form: sometimes we may get different normal forms depending on our choice. We also give a simpler proof of the strong normalization of the same reduction. Our proof is based on a notion of a norm defined on the terms.
- 1 January 2020
- Published by American Institute of Mathematical Sciences (AIMS) in AIMS Mathematics
- Vol. 5 (4) , 3702-3713
Open AccessNormalization proofs for the un-typed μμ'-calculus
A long-standing open problem of Parigot has been solved by David and Nour, namely, they gave a syntactical and arithmetical proof of the strong normalization of the untyped μμ'-reduction. In connection with this, we present in this paper a proof of the weak normalization of the μ and μ'-rules. The algorithm works by induction on the complexity of the term. Our algorithm does not necessarily give a unique normal form: sometimes we may get different normal forms depending on our choice. We also give a simpler proof of the strong normalization of the same reduction. Our proof is based on a notion of a norm defined on the terms.
- 1 January 2020
- Published by Elsevier in Theoretical Computer Science
- Vol. 805, 175-192
Local time membrane systems and time Petri nets
- 1 January 2020
- Published by Elsevier in Theoretical Computer Science
- Vol. 805, 175-192
Local time membrane systems and time Petri nets
- 9 June 2019
- Published by Springer Nature
- p. 239-252
Membrane Systems and Multiset Approximation: The Cases of Inner and Boundary Rule Application
- 9 June 2019
- Published by Springer Nature
- p. 239-252
Membrane Systems and Multiset Approximation: The Cases of Inner and Boundary Rule Application
- 26 April 2019
- Published by Springer Nature
- p. 15-29
Generalized Membrane Systems with Dynamical Structure, Petri Nets, and Multiset Approximation Spaces
- 26 April 2019
- Published by Springer Nature
- p. 15-29
Generalized Membrane Systems with Dynamical Structure, Petri Nets, and Multiset Approximation Spaces
- 17 February 2017
- Published by Springer Nature in Lecture Notes in Computer Science
- p. 136-150
Chemical Term Reduction with Active P Systems
- 17 February 2017
- Published by Springer Nature in Lecture Notes in Computer Science
- p. 136-150
Chemical Term Reduction with Active P Systems