TY  - THES
A1  - Bordihn, Henning
T1  - Contributions to the syntactical analysis beyond context-freeness
T1  - Beiträge zur syntaktischen Analyse nicht-kontextfreier Sprachen
N2  - Parsability approaches of several grammar formalisms generating also non-context-free languages are explored. Chomsky grammars, Lindenmayer systems, grammars with controlled derivations, and grammar systems are treated. Formal properties of these mechanisms are investigated, when they are used as language acceptors. Furthermore, cooperating distributed grammar systems are restricted so that efficient deterministic parsing without backtracking becomes possible. For this class of grammar systems, the parsing algorithm is presented and the feature of leftmost derivations is investigated in detail.
N2  - Ansätze zum Parsing verschiedener Grammatikformalismen, die auch nicht-kontextfreie Sprachen erzeugen können, werden diskutiert. Chomsky-Grammatiken, Lindenmayer-Systeme, Grammatiken mit gesteuerten Ersetzungen und Grammatiksysteme werden behandelt. Formale Eigenschaften dieser Mechanismen als Akzeptoren von Sprachen werden untersucht. Weiterhin werden kooperierende verteilte (CD) Grammatiksysteme derart beschränkt, dass effizientes deterministisches Parsing ohne Backtracking möglich ist. Für diese Klasse von Grammatiksystemen wird der Parsingalgorithmus vorgestellt und die Rolle von Linksableitungen wird detailliert betrachtet.
KW  - Parsing
KW  - Akzeptierende Grammatiken
KW  - Gesteuerte Ableitungen
KW  - Grammatiksysteme
KW  - Linksableitungen
KW  - Parsing
KW  - Accepting Grammars
KW  - Controlled Derivations
KW  - Grammar Systems
KW  - Leftmost Derivations
Y1  - 2011
U6  - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus-59719
ER  - 
TY  - JOUR
A1  - Bordihn, Henning
A1  - Vaszil, György
T1  - Deterministic Lindenmayer systems with dynamic control of parallelism
JF  - International journal of foundations of computer science
N2  - M-rate 0L systems are interactionless Lindenmayer systems together with a function assigning to every string a set of multisets of productions that may be applied simultaneously to the string. Some questions that have been left open in the forerunner papers are examined, and the computational power of deterministic M-rate 0L systems is investigated, where also tabled and extended variants are taken into consideration.
KW  - parallel rewriting
KW  - Lindenmayer systems
KW  - restricted parallelism
KW  - determinism
KW  - developmental systems
KW  - formal languages
Y1  - 2019
U6  - https://doi.org/10.1142/S0129054120400031
SN  - 0129-0541
SN  - 1793-6373
VL  - 31
IS  - 1
SP  - 37
EP  - 51
PB  - World Scientific
CY  - Singapore
ER  - 
TY  - JOUR
A1  - Bordihn, Henning
A1  - Holzer, Markus
T1  - On the number of active states in finite automata
JF  - Acta informatica
N2  - We introduce a new measure of descriptional complexity on finite automata, called the number of active states. Roughly speaking, the number of active states of an automaton A on input w counts the number of different states visited during the most economic computation of the automaton A for the word w. This concept generalizes to finite automata and regular languages in a straightforward way. We show that the number of active states of both finite automata and regular languages is computable, even with respect to nondeterministic finite automata. We further compare the number of active states to related measures for regular languages. In particular, we show incomparability to the radius of regular languages and that the difference between the number of active states and the total number of states needed in finite automata for a regular language can be of exponential order.
Y1  - 2021
U6  - https://doi.org/10.1007/s00236-021-00397-8
SN  - 0001-5903
SN  - 1432-0525
VL  - 58
IS  - 4
SP  - 301
EP  - 318
PB  - Springer
CY  - Berlin ; Heidelberg [u.a.]
ER  - 
TY  - JOUR
A1  - Bordihn, Henning
A1  - Vaszil, György
T1  - Reversible parallel communicating finite automata systems
JF  - Acta informatica
N2  - 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.
KW  - Finite automata
KW  - Reversibility
KW  - Systems of parallel communicating
KW  - automata
Y1  - 2021
U6  - https://doi.org/10.1007/s00236-021-00396-9
SN  - 0001-5903
SN  - 1432-0525
VL  - 58
IS  - 4
SP  - 263
EP  - 279
PB  - Springer
CY  - Berlin ; Heidelberg ; New York, NY
ER  -