Jürgen Dassow

Jürgen Dassow

Auto-generated profile, based on publicly available information

Jürgen Dassow

Fakultät für Informatik, Otto-von-Guericke-Universität Magdeburg, PSF 4120, 39016 Magdeburg, Germany

Research Focus & Metrics

Academic Career Length

38Years (1989-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
14 December 2001 in Theoretical Computer Science
Verified
Journal Article
Closed access
PDF file
JDJürgen Dassow
Jürgen Dassow
VMVictor Mitrana
Victor Mitrana
ASArto Salomaa
Arto Salomaa

1 June 1999 in Journal of Computer and System Sciences
Verified
Journal Article
Closed access
JDJürgen Dassow
Jürgen Dassow
Victor MitranaVictor Mitrana
Victor Mitrana

7 October 2011 in Theoretical Computer Science
Verified
Journal Article
Closed access
DLDaniel Lobo
Daniel Lobo
FVFrancisco J. Vico
Francisco J. Vico
JDJürgen Dassow
Jürgen Dassow

20 July 2022 in Acta Informatica
Verified
Journal Article
Open access
PDF file
JDJürgen Dassow
Jürgen Dassow
IJIsmaël Jecker
Ismaël Jecker
The well-known pumping lemma for regular languages states that, for any regular language L, there is a constant p (depending on L) such that the following holds: If $$w\in L$$ w ∈ L and $$\vert w\vert \ge p$$ | w | ≥ p , then there are words $$x\in V^{*}$$ x ∈ V ∗ , $$y\in V^+$$ y ∈ V + , and $$z\in V^{*}$$ z ∈ V ∗ such that $$w=xyz$$ w = x y z and $$xy^tz\in L$$ x y t z ∈ L for $$t\ge 0$$ t ≥ 0 . The minimal pumping constant $${{{\,\mathrm{mpc}\,}}(L)}$$ mpc ( L ) of L is the minimal number p for which the conditions of the pumping lemma are satisfied. We investigate the behaviour of $${{{\,\mathrm{mpc}\,}}}$$ mpc with respect to operations, i. e., for an n-ary regularity preserving operation $$\circ $$ ∘ , we study the set $${g_{\circ }^{{{\,\mathrm{mpc}\,}}}(k_1,k_2,\ldots ,k_n)}$$ g ∘ mpc ( k 1 , k 2 , … , k n ) of all numbers k such that there are regular languages $$L_1,L_2,\ldots ,L_n$$ L 1 , L 2 , … , L n with $${{{\,\mathrm{mpc}\,}}(L_i)=k_i}$$ mpc ( L i ) = k i for $$1\le i\le n$$ 1 ≤ i ≤ n and $${{{\,\mathrm{mpc}\,}}(\circ (L_1,L_2,\ldots ,L_n)=~k}$$ mpc ( ∘ ( L 1 , L 2 , … , L n ) = k . With respect to Kleene closure, complement, reversal, prefix and suffix-closure, circular shift, union, intersection, set-subtraction, symmetric difference,and concatenation, we determine $${g_{\circ }^{{{\,\mathrm{mpc}\,}}}(k_1,k_2,\ldots ,k_n)}$$ g ∘ mpc ( k 1 , k 2 , … , k n ) completely. Furthermore, we give some results with respect to the minimal pumping length where, in addition, $$\vert xy\vert \le p$$ | x y | ≤ p has to hold.

21 November 2012 in Acta Informatica
Verified
Journal Article
Closed access
PDF file
JDJürgen Dassow
Jürgen Dassow
FMFlorin Manea
Florin Manea
BTBianca Truthe
Bianca Truthe

25 September 2012 in Acta Informatica
Verified
Journal Article
Open access
PDF file
FAFernando Arroyo
Fernando Arroyo
JCJuan Castellanos
Juan Castellanos
JDJürgen Dassow
Jürgen Dassow
Victor MitranaVictor Mitrana
Victor Mitrana
JSJosé-Ramón Sánchez-Couso
José-Ramón Sánchez-Couso
In this paper we propose a generalization of the accepting splicing systems introduced in Mitrana et al. (Theor Comput Sci 411:2414–2422, 2010). More precisely, the input word is accepted as soon as a permitting word is obtained provided that no forbidding word has been obtained so far, otherwise it is rejected. Note that in the new variant of accepting splicing system the input word is rejected if either no permitting word is ever generated (like in Mitrana et al. in Theor Comput Sci 411:2414–2422, 2010) or a forbidding word has been generated and no permitting word had been generated before. We investigate the computational power of the new variants of accepting splicing systems and the interrelationships among them. We show that the new condition strictly increases the computational power of accepting splicing systems. Although there are regular languages that cannot be accepted by any of the splicing systems considered here, the new variants can accept non-regular and even non-context-free languages, a situation that is not very common in the case of (extended) finite splicing systems without additional restrictions. We also show that the smallest class of languages out of the four classes defined by accepting splicing systems is strictly included in the class of context-free languages. Solutions to a few decidability problems are immediately derived from the proof of this result.