Henning Bordihn
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Henning Bordihn has a total of 17 co-authors. Here are the top co-authors by number of shared publications:
- Markus Holzer
Universität Gießen
4 shared publications - Martin Kutrib
Institut für Informatik, Universität Gießen
4 shared publications - Victor Mitrana
Polytechnic University of Madrid
3 shared publications - Friedrich Otto
Universität Kassel
2 shared publications - György Vaszil
Department of Computer Science, Faculty of Informatics, University of Debrecen, Debrecen, Hungary
2 shared publications - Mika Hirvensalo
Department of Mathematics and Statistics, University of Turku, Turku, Finland
2 shared publications
Latest Publications
- 18 March 2025
- Published by World Scientific Pub Co Pte Ltd in International Journal of Foundations of Computer Science
- Vol. 36 (03) , 247-267
Leftmost Derivations in CD Grammar Systems
We investigate the power of CD grammar systems using different types of leftmost derivations for all standard cooperation strategies including the so-called full-competence mode of derivation. It is proved that, for some types of leftmost restrictions and cooperation strategies, CD grammar systems generate the same language classes as in the unrestricted, “non-leftmost” case, but the generative power is also increased or decreased in several cases. Thereby, some new relations to well-known Chomsky and Lindenmayer classes are presented.
- 18 March 2025
- Published by World Scientific Pub Co Pte Ltd in International Journal of Foundations of Computer Science
- Vol. 36 (03) , 247-267
Leftmost Derivations in CD Grammar Systems
We investigate the power of CD grammar systems using different types of leftmost derivations for all standard cooperation strategies including the so-called full-competence mode of derivation. It is proved that, for some types of leftmost restrictions and cooperation strategies, CD grammar systems generate the same language classes as in the unrestricted, “non-leftmost” case, but the generative power is also increased or decreased in several cases. Thereby, some new relations to well-known Chomsky and Lindenmayer classes are presented.
- Open Access
- 10 September 2024
- Published by Open Publishing Association in Electronic Proceedings in Theoretical Computer Science
- Vol. 407, 44-58
Determinism in Multi-Soliton Automata
Soliton automata are mathematical models of soliton switching in chemical molecules. Several concepts of determinism for soliton automata have been defined. The concept of strong determinism has been investigated for the case in which only a single soliton can be present in a molecule. In the present paper, several different concepts of determinism are explored for the multi-soliton case. It is shown that the degree of non-determinism is a connected measure of descriptional complexity for multi-soliton automata. A characterization of the class of strongly deterministic multi-soliton automata is presented. Finally, the concept of perfect determinism, forming a natural extension of strong determinism, is introduced and considered for multi-soliton automata.
- 10 September 2024
- Published by Open Publishing Association in Electronic Proceedings in Theoretical Computer Science
- Vol. 407, 44-58
Open AccessDeterminism in Multi-Soliton Automata
Soliton automata are mathematical models of soliton switching in chemical molecules. Several concepts of determinism for soliton automata have been defined. The concept of strong determinism has been investigated for the case in which only a single soliton can be present in a molecule. In the present paper, several different concepts of determinism are explored for the multi-soliton case. It is shown that the degree of non-determinism is a connected measure of descriptional complexity for multi-soliton automata. A characterization of the class of strongly deterministic multi-soliton automata is presented. Finally, the concept of perfect determinism, forming a natural extension of strong determinism, is introduced and considered for multi-soliton automata.
- 19 July 2021
- Published by Springer Nature in Acta Informatica
- Vol. 58 (4) , 301-318
On the number of active states in finite automata
- 19 July 2021
- Published by Springer Nature in Acta Informatica
- Vol. 58 (4) , 301-318
On the number of active states in finite automata
- Open Access
- 19 July 2021
- Published by Springer Nature in Acta Informatica
- Vol. 58 (4) , 263-279
Reversible parallel communicating finite automata systems
We study the concept of reversibility in connection with parallel communicating systems of finite automata (PCFA in short). We define the notion of reversibility in the case of PCFA (also covering the non-deterministic case) and discuss the relationship of the reversibility of the systems and the reversibility of its components. We show that a system can be reversible with non-reversible components, and the other way around, the reversibility of the components does not necessarily imply the reversibility of the system as a whole. We also investigate the computational power of deterministic centralized reversible PCFA. We show that these very simple types of PCFA (returning or non-returning) can recognize regular languages which cannot be accepted by reversible (deterministic) finite automata, and that they can even accept languages that are not context-free. We also separate the deterministic and non-deterministic variants in the case of systems with non-returning communication. We show that there are languages accepted by non-deterministic centralized PCFA, which cannot be recognized by any deterministic variant of the same type.
- 19 July 2021
- Published by Springer Nature in Acta Informatica
- Vol. 58 (4) , 263-279
Open AccessReversible parallel communicating finite automata systems
We study the concept of reversibility in connection with parallel communicating systems of finite automata (PCFA in short). We define the notion of reversibility in the case of PCFA (also covering the non-deterministic case) and discuss the relationship of the reversibility of the systems and the reversibility of its components. We show that a system can be reversible with non-reversible components, and the other way around, the reversibility of the components does not necessarily imply the reversibility of the system as a whole. We also investigate the computational power of deterministic centralized reversible PCFA. We show that these very simple types of PCFA (returning or non-returning) can recognize regular languages which cannot be accepted by reversible (deterministic) finite automata, and that they can even accept languages that are not context-free. We also separate the deterministic and non-deterministic variants in the case of systems with non-returning communication. We show that there are languages accepted by non-deterministic centralized PCFA, which cannot be recognized by any deterministic variant of the same type.
- 1 March 2020
- Published by Elsevier in Journal of Computer and System Sciences
- Vol. 108, 104-117
On the degrees of non-regularity and non-context-freeness
- 1 March 2020
- Published by Elsevier in Journal of Computer and System Sciences
- Vol. 108, 104-117
On the degrees of non-regularity and non-context-freeness
- 1 April 2018
- Published by EDP Sciences in RAIRO - Theoretical Informatics and Applications
- Vol. 52 (2-3-4) , 87-88
Preface: Non-classical models of automata and applications VIII
RAIRO - Theoretical Informatics and Applications, an international journal on theoretical computer science and its applications
- 1 April 2018
- Published by EDP Sciences in RAIRO - Theoretical Informatics and Applications
- Vol. 52 (2-3-4) , 87-88
Preface: Non-classical models of automata and applications VIII
RAIRO - Theoretical Informatics and Applications, an international journal on theoretical computer science and its applications
- 1 June 2017
- Published by Elsevier in Theoretical Computer Science
- Vol. 682, 42-48
Active symbols in grammars with valuations
- 1 June 2017
- Published by Elsevier in Theoretical Computer Science
- Vol. 682, 42-48
Active symbols in grammars with valuations
- 1 June 2016
- Published by Springer Nature in Soft Computing
- Vol. 21 (19) , 5529-5541
Networks of picture processors as problem solvers
- 1 June 2016
- Published by Springer Nature in Soft Computing
- Vol. 21 (19) , 5529-5541
Networks of picture processors as problem solvers
- 1 June 2015
- Published by SAGE Publications in Fundamenta Informaticae
- Vol. 138 (1-2) , 85-95
Ambiguity of the Multiple Interpretations on Regular Languages
A multiple interpretation scheme is an ordered sequence of morphisms. The ordered multiple interpretation of a word is obtained by concatenating the images of that word in the given order of morphisms. The arbitrary multiple interpretation of a word is the semigroup generated by the images of that word. These interpretations are naturally extended to languages. Four types of ambiguity of multiple interpretation schemata on a language are defined: o-ambiguity, internal ambiguity, weakly external ambiguity and strongly external ambiguity. We investigate the problem of deciding whether a multiple interpretation scheme is ambiguous on regular languages.
- 1 June 2015
- Published by SAGE Publications in Fundamenta Informaticae
- Vol. 138 (1-2) , 85-95
Ambiguity of the Multiple Interpretations on Regular Languages
A multiple interpretation scheme is an ordered sequence of morphisms. The ordered multiple interpretation of a word is obtained by concatenating the images of that word in the given order of morphisms. The arbitrary multiple interpretation of a word is the semigroup generated by the images of that word. These interpretations are naturally extended to languages. Four types of ambiguity of multiple interpretation schemata on a language are defined: o-ambiguity, internal ambiguity, weakly external ambiguity and strongly external ambiguity. We investigate the problem of deciding whether a multiple interpretation scheme is ambiguous on regular languages.
- Open Access
- 21 May 2014
- Published by Open Publishing Association in Electronic Proceedings in Theoretical Computer Science
- Vol. 151, 124-138
Measuring Communication in Parallel Communicating Finite Automata
Systems of deterministic finite automata communicating by sending their states upon request are investigated, when the amount of communication is restricted. The computational power and decidability properties are studied for the case of returning centralized systems, when the number of necessary communications during the computations of the system is bounded by a function depending on the length of the input. It is proved that an infinite hierarchy of language families exists, depending on the number of messages sent during their most economical recognitions. Moreover, several properties are shown to be not semi-decidable for the systems under consideration.Comment: In Proceedings AFL 2014, arXiv:1405.527
- 21 May 2014
- Published by Open Publishing Association in Electronic Proceedings in Theoretical Computer Science
- Vol. 151, 124-138
Open AccessMeasuring Communication in Parallel Communicating Finite Automata
Systems of deterministic finite automata communicating by sending their states upon request are investigated, when the amount of communication is restricted. The computational power and decidability properties are studied for the case of returning centralized systems, when the number of necessary communications during the computations of the system is bounded by a function depending on the length of the input. It is proved that an infinite hierarchy of language families exists, depending on the number of messages sent during their most economical recognitions. Moreover, several properties are shown to be not semi-decidable for the systems under consideration.Comment: In Proceedings AFL 2014, arXiv:1405.527