A Faster Exact Algorithm for the Directed Maximum Leaf Spanning Tree Problem (2009)
Raible, Daniel, Fernau, Henning
Given a directed graph $G=(V,A)$, the Directed Maximum Leaf Spanning Tree problem asks to compute a directed spanning tree (i.e., an out-branching) with as many leaves as possible. By designing a...
Breaking the 2^n-Barrier for Irredundance: A Parameterized Route to Solving Exact Puzzles (2009)
Brankovic, Ljiljana, Fernau, Henning, Kneis, Joachim
The lower and the upper irredundance numbers of a graph $G$, denoted $ir(G)$ and $IR(G)$ respectively, are conceptually linked to domination and independence numbers and have numerous relations to...
The Complexity of Probabilistic Lobbying (2009)
Erdélyi, Gábor, Fernau, Henning, Goldsmith, Judy, Mattei, Nicholas, Raible, Daniel, Rothe, Jörg
We propose various models for lobbying in a probabilistic environment, in which an actor (called "The Lobby") seeks to influence the voters' preferences of voting for or against multiple issues when...
Kernel(s) for Problems with No Kernel: On Out-Trees with Many Leaves (2009)
Fernau, Henning, Fomin, Fedor V., Lokshtanov, Daniel, Raible, Daniel, Saurabh, Saket, Villanger, Yngve
The k-Leaf Out-Branching problem is to find an out-branching, that is a rooted oriented spanning tree, with at least k leaves in a given digraph. The problem has recently received much attention from...
Kernel(s) for Problems with No Kernel: On Out-Trees with Many Leaves (2009)
Fernau, Henning, Fomin, Fedor V., Lokshtanov, Daniel, Raible, Daniel, Saurabh, Saket, Villanger, Yngve
The k-Leaf Out-Branching problem is to find an out-branching, that is a rooted oriented spanning tree, with at least k leaves in a given digraph. The problem has recently received much attention from...
Kernel(s) for Problems with No Kernel: On Out-Trees with Many Leaves (2009)
Fernau, Henning, Fomin, Fedor V., Lokshtanov, Daniel, Raible, Daniel, Saurabh, Saket, Villanger, Yngve
The {sc $k$-Leaf Out-Branching} problem is to find an out-branching, that is a rooted oriented spanning tree, with at least $k$ leaves in a given digraph. The problem has recently received much...
Parallel Grammars -- A Phenomenology (2008)
The aim of this paper is at least twofold: − to give prospective PhD students in the area hints at where to start a promising research and − to supplement earlier reference lists on parallel...
Exact Exponential Time Algorithms for Max Internal Spanning Tree (2008)
Fernau, Henning, Raible, Daniel, Gaspers, Serge, Stepanov, Alexey A.
We are considering the \NP-hard problem of finding a spanning tree with many internal vertices. This problem is a generalization of the famous and well-studied {\sc Hamiltonian Path} problem. We...
Kernel(s) for Problems With no Kernel: On Out-Trees With Many Leaves (2008)
Fernau, Henning, Fomin, Fedor V., Lokshtanov, Daniel, Raible, Daniel, Saurabh, Saket, Villanger, Yngve
The {\sc $k$-Leaf Out-Branching} problem is to find an out-branching (i.e. a rooted oriented spanning tree) with at least $k$ leaves in a given digraph. The problem has recently received much...
A Parameterized Perspective on $P_2$-Packings (2008)
Chen, Jianer, Fernau, Henning, Ning, Dan, Raible, Daniel, Wang, Jianxin
}We study (vertex-disjoint) $P_2$-packings in graphs under a parameterized perspective. Starting from a maximal $P_2$-packing $\p$ of size $j$ we use extremal arguments for determining how many...
Remarks on propagating partition-limited ET0L systems (2008)
Abstract: In this paper, we sharpen the results of Gartner on the universality of partition-limited ET0L systems by showing that such deterministic systems characterize the recursively enumerable...
Nonblocker: Parameterized Algorithmics for Minimum Dominating Set (2008)
Elena Prieto, Complutense Madrid Spain, Awards Fellowships Honours, Frank Dehne, Michael Fellows, Henning Fernau, ...
Roman domination: A Parameterized Perspective (2008)
Abstract. We analyze Roman domination from a parameterized perspective. More specifically, we prove that this problem is W[2]-complete for general graphs. However, parameterized algorithms are...
An Invitation for Formal Language Theorists (2008)
Grammar Induction, Henning Fernau
Why should Formal Language specialists get interested and involved in the area of Grammar Induction (GI), likewise known as Grammatical Inference? This is the question we try to answer in this paper....
Exact Elimination of Cycles in Graphs (2008)
Abstract. One of the standard basic steps in drawing hierarchical graphs is to invert some arcs of the given graph to make the graph acyclic. We discuss exact and parameterized algorithms for this...
Local Elimination-Strategies in Automata for Shorter Regular Expressions (2008)
Abstract. We propose a construction of regular expressions from particularly restricted NFA via extended automata. It proceeds in two main steps, elimination of cycles in the state graph followed by...
Algorithms for Learning Regular Expressions (Extended Abstract) (2008)
Abstract. We describe algorithms that directly infer regular expressions from positive data and characterize the regular language classes that can be learned this way. 1
A New Upper Bound for Max-2-Sat: A Graph-Theoretic Approach (2008)
Raible, Daniel, Fernau, Henning
In {\sc MaxSat}, we ask for an assignment which satisfies the maximum number of clauses for a boolean formula in CNF. We present an algorithm yielding a run time upper bound of...
Bradford Starkie, Henning Fernau
Abstract. This paper introduces a new grammatical inference algorithm called the Boisdale algorithm. This algorithm can identify a class of contextfree unification grammar in the limit from positive...
Martin Kutrib, Thomas Worsch (hrsg, Thomas Worsch, Henning Bordihn, Henning Fernau, Accepting Programmed
Dem n"achsten Theorietag in Cunnersdorf bei K"onigsstein in der S"achsischen Schweiz w"unschen wir viel Erfolg. Giessen, im Dezember 1995 Martin Kutrib
An Optimal Construction of Finite Automata from Regular Expressions (2008)
Gulan, Stefan, Fernau, Henning
We consider the construction of finite automata from their corresponding regular expressions by a series of digraph-transformations along the expression's structure. Each intermediate graph...
Valences in Parallel Systems (2007)
Henning Fernau, Ralf Stiebe, H. Fernau, R. Stiebe
We investigate four variants of valence regulations incorporated in (limited) Lindenmayer systems, focussing on hierarchical relations and closure properties. Strong connections to well-known...
Regularly Controlled Formal Power Series (2007)
Regulated rewriting is one of the classical topics in formal language theory, see [2, 3]. This paper starts the research of regulated rewriting in the framework of formal power series, cf. [6, 7, 9]....
Henning Fernau, Henning Fernau, Henning Fernau
Nonterminal complexity of programmed grammars
Henning Fernau, Henning Fernau, Henning Fernau, Ralf Stiebe, Ralf Stiebe, Ralf Stiebe
We discuss the model of valence grammars, a simple extension of context-free grammars. We show closure properties of valence languages over arbitrary monoids. Chomsky and Greibach normal form...
The Generative Power of d-Dimensional #-Context-Free Array Grammars (2007)
Henning Fernau, Rudolf Freund, Markus Holzer
The main result proved in this paper shows that the natural embedding of any one-dimensional array language in the two-dimensional space can be generated by a two-dimensional #-context-free array...
Valences in Parallel Systems (2007)
Henning Fernau, Ralf Stiebe, H. Fernau, R. Stiebe
We investigate four variants of valence regulations incorporated in (limited) Lindenmayer systems, focussing on hierarchical relations and closure properties. Strong connections to well-known...
Regulated Array Grammars of Finite Index - Part I: Theoretical Investigations (2007)
Henning Fernau, Rudolf Freund, Markus Holzer
. We consider regulated (n-dimensional) context-free array grammars of finite index, i.e., with a limited number of active areas. This research is motivated by the observation that in several...
Remarks On Adult Languages Of Propagating Systems With Restricted Parallelism (2007)
this paper appear elsewhere.
How Powerful is Unconditional Transfer? - When UT meets AC. (2007)
. We prove that every recursively enumerable language can be generated by a programmed grammar with context-free core rules using unconditional transfer with leftmost derivation of type 3 or type 2....
Regulated Array Grammars of Finite Index - Part II: Syntactic pattern recognition (2007)
Henning Fernau, Rudolf Freund, Markus Holzer
. We introduce special k-head finite array automata, which characterize the array languages generated by specific variants of regulated n-dimensional context-free array grammars of finite index we...
Rudolf Freund, Henning Fernau, Markus Holzer
. The main result proved in this paper shows that the natural embedding of any one-dimensional array language in the two-dimensional space can be characterized by the projection of a two-dimensional...
Valuation Entropy of omega-Languages & IFS (2007)
Henning Fernau, Ludwig Staiger
. Valuations --- morphisms from (\Sigma ; \Delta; e) to ((0; 1); \Delta; 1) --- are a simple generalization of Bernoulli morphisms (distributions, measures) as introduced in [4,6]. Here, we show how...
Jochen Alber, Henning Fernau, Rolf Niedermeier, Hongbing Fan, Michael R. Fellows, Fran Rosamond, ...
We establish a refined search tree technique for the parameterized Dominating Set problem on planar graphs. Here, we are given an undirected graph and we ask for a set of at most k vertices such that...
Jochen Alber, Hans L. Bodlaender, Henning Fernau, Rolf Niedermeier
We present an algorithm that constructively produces a solution to the k-dominating set problem for planar graphs in time O(c p
Wilhelm-Schickhard-Institut, (2007)
Henning Fernau, Ludwig Staiger
Valuations--- morphisms from (S; \Delta; e) to ((0;); \Delta; 1)--- are a generalization of Bernoulli morphisms introduced in [10]. Here, we show how to generalize the notion of entropy (of a...
Stefan Edelkamp, Henning Fernau, Rolf Niedermeier
Abstract. We present solutions of benchmark instances to the solitaire computer game Atomix found with dierent heuristic search methods. The problem is PSPACE-complete. An implementation of the...
Stefan Edelkamp, Henning Fernau, Rolf Niedermeier
######## # We present solutions of benchmark instances to the solitaire computer game Atomix found with dierent heuristic search methods. The problem is PSPACE-complete. An implementation of the...
Jochen Alber, Hans L. Bodlaender, Henning Fernau, Rolf Niedermeier
We present an algorithm that constructively produces a solution to the k-dominating set problem for planar graphs in time O(c p
Jochen Alber, Hongbing Fan, Michael R. Fellows, Henning Fernau, Rolf Niedermeier, Fran Rosamond, ...
Abstract. We establish rened search tree techniques for the parameterized Dominating Set problem on planar graphs. We derive a xed parameter algorithm with running time O(8 k n), where k is the size...
Wilhelm-Schickard-Institut fur Informatik, Universitat Tubingen, (2007)
Henning Fernau, Rolf Niedermeier
The \Constraint Bipartite Vertex Cover " problem (CBVC for short) is: given a bipartite graph G with n vertices and two positive integers k 1; k 2, is there a vertex cover taking at most k 1...
Observations on grammar and language families. (2007)
In this report, we emphasize the differences of grammar families and their properties versus language families and their properties. To this end, we investigate grammar families from an abstract...
Accepting grammars and systems. (2007)
Bordihn, Henning, Fernau, Henning
We investigate several kinds of regulated rewriting (programmed, matrix, with regular control, ordered, and variants thereof) and of parallel rewriting mechanisms (Lindenmayer systems, uniformly...
Membership for limited ET0L languages is not decidable. (2007)
In this paper, we show how to encode arbitrary enumerable set of numbers given by register machines within limited EPT0L systems and programmed grammars with unconditional transfer.This result has...
Exact Elimination of Cycles in Graphs (2007)
Raible, Daniel, Fernau, Henning
One of the standard basic steps in drawing hierarchical graphs is to invert some arcs of the given graph to make the graph acyclic. We discuss exact and parameterized algorithms for this problem. In...
nonblocker: Parameterized Algorithmics for (2006)
Minimum Dominating Set, Frank Dehne, Michael Fellows, Henning Fernau, Elena Prieto, Frances Rosamond
We provide parameterized algorithms for nonblocker, the parametric dual of the well known dominating set problem. We exemplify three methodologies for deriving parameterized algorithms that can be...
Edge dominating set: efficient enumeration-based exact algorithms (2006)
Abstract. We analyze edge dominating set from a parameterized perspective. More specifically, we prove that this problem is in FPT for general (weighted) graphs. The corresponding algorithms rely on...
Vertex and edge covers with clustering properties: Complexity and algorithms (2006)
Henning Fernau, David F. Manlove
We consider the concepts of a t-total vertex cover and a t-total edge cover (t ≥ 1), which generalize the notions of a vertex cover and an edge cover, respectively. A t-total vertex (respectively...
A refined search tree technique for Dominating Set on planar graphs (2005)
Alber, Jochen, Fan, Hongbing, Fernau, Henning, Niedermeier, Rolf, ...
We establish a refined search tree technique for the parameterized DOMINATING SET problem on planar graphs. Here, we are given an undirected graph and we ask for a set of at most k vertices such that...
A refined search tree technique for Dominating Set on planar graphs (2005)
Alber, Jochen, Fan, Hongbing, Fernau, Henning, Niedermeier, Rolf, ...
We establish a refined search tree technique for the parameterized DOMINATING SET problem on planar graphs. Here, we are given an undirected graph and we ask for a set of at most k vertices such that...
Parametric duality and kernelization: Lower bounds and upper bounds on kernel size (2005)
Chen, J N, Fernau, Henning, Kanj, I A, Xia, G
We develop new techniques to derive lower bounds on the kernel size for certain parameterized problems. For example, we show that unless P = NP, PLANAR VERTEX COVER does not have a problem kernel of...
Two-layer planarization: Improving on parameterized algorithmics (2005)
A bipartite graph is biplanar if the vertices can be placed on two parallel lines in the plane such that, there are no edge crossings when edges are drawn as straight-line segments. We study two...
Approximability of a {0,1} - matrix problem (2005)
Brankovic, Ljiljana, Fernau, Henning
We consider the following combinatorial problem: given an n x m {0,1}-matrix M, find a minimum cardinality set S of meanings between neighboring rows or columns that yields an all-zeros matrix. Here,...
Approximability of a {0,1} - matrix problem (2005)
Brankovic, Ljiljana, Fernau, Henning
We consider the following combinatorial problem: given an n x m {0,1}-matrix M, find a minimum cardinality set S of meanings between neighboring rows or columns that yields an all-zeros matrix. Here,...
Parametric duality and kernelization: lower bounds and upper bounds on kernel size (2005)
Jianer Chen, Henning Fernau, Iyad A. Kanj, Ge Xia
Abstract. Determining whether a parameterized problem is kernelizable and has a small kernel size has recently become one of the most interesting topics of research in the area of parameterized...
Parameterized algorithmics for linear arrangement problems (2005)
We discuss different variants of linear arrangement problems from a parameterized perspective. More specifically, we concentrate on developing simple search tree algorithms for these problems....
Refining the nonterminal complexity of graph-controlled grammars (2005)
Henning Fernau, Rudolf Freund, Marion Oswald, Klaus Reinhardt
We refine the classical notion of the nonterminal complexity of graph-controlled grammars, programmed grammars, and matrix grammars by also counting, in addition, the number of nonterminal symbols...
Refining the nonterminal complexity of graph-controlled grammars (2005)
1 Introduction Nonterminal complexity is a classical measure of descriptional complexity of grammars. Withinthe area of regulated rewriting, graph-control can be seen as a framework in which many...
Parametric duality and kernelization: lower bounds and upper bounds on kernel size (2005)
Jianer Chen, Henning Fernau, Iyad A. Kanj, Ge Xia
Abstract. We develop new techniques to derive lower bounds on the kernel size for certain parameterized problems. For example, we show that unless P = N P, planar vertex cover does not have a problem...
Asymptotically faster algorithms for parameterized face cover (2005)
abstract. The parameterized complexity of the face cover problem is considered. The input to this problem is a plane graph, G, of order n. The question asked is whether, for any fixed k, there exists...
Two-layer planarization: Improving on parameterized algorithmics (2005)
A bipartite graph is biplanar if the vertices can be placed on two parallel lines in the plane such that there are no edge crossings when edges are drawn as straight-line segments connecting vertices...
Comparing trees via crossing minimization (2005)
Henning Fernau, Michael Kaufmann, Mathias Poths
Abstract. Two trees with the same number of leaves have to be embedded in two layers in the plane such that the leaves are aligned in two adjacent layers. Additional matching edges between the leaves...
1.1 Why practitioners may wish to continue reading........ 9 1.2 Standard notations........................ 11
Asymptotically faster algorithms for parameterized face cover (2005)
Henning Fernau, Michael A. Langston
Abstract. The parameterized complexity of the face cover problem is considered. The input to this problem is a plane graph, G, ofordern. The question asked is whether, for any fixed k, there exists a...
Approximability of a {0,1} - matrix problem (2005)
Brankovic, Ljiljana, Fernau, Henning
We consider the following combinatorial problem: given an n x m {0,1}-matrix M, find a minimum cardinality set S of meanings between neighboring rows or columns that yields an all-zeros matrix. Here,...
A refined search tree technique for Dominating Set on planar graphs (2005)
Alber, Jochen, Fan, Hongbing, Fellows, Michael R., Fernau, Henning, Niedermeier, Rolf, Rosamond, Fran, ...
We establish a refined search tree technique for the parameterized DOMINATING SET problem on planar graphs. Here, we are given an undirected graph and we ask for a set of at most k vertices such that...
Parametric duality and kernelization: Lower bounds and upper bounds on kernel size (2005)
Chen, J. N., Fernau, Henning, Kanj, I. A., Xia, G.
We develop new techniques to derive lower bounds on the kernel size for certain parameterized problems. For example, we show that unless P = NP, PLANAR VERTEX COVER does not have a problem kernel of...
Two-layer planarization: Improving on parameterized algorithmics (2005)
A bipartite graph is biplanar if the vertices can be placed on two parallel lines in the plane such that, there are no edge crossings when edges are drawn as straight-line segments. We study two...
Fixed Parameter Algorithms for one-sided crossing minimization Revisited (2004)
Dujmovic, Vida, Fernau, Henning, Kaufmann, Michael
We exhibit a small problem kernel for the problem one-sided crossing minimization which plays an important role in graph drawing algorithms based on the Sugiyama layering approach. Moreover, we...
Fixed parameter algorithms for one-sided crossing minimization revisited (2004)
Vida Dujmović, Henning Fernau, Michael Kaufmann
We exhibit a small problem kernel for the one-sided crossing minimization problem. This problem plays an important role in graph drawing algorithms based on the Sugiyama layering approach. Moreover,...
Fixed parameter algorithms for one-sided crossing minimization revisited (2004)
Vida Dujmović, Henning Fernau, Michael Kaufmann
Abstract. We exhibit a small problem kernel for the problem onesided crossing minimization which plays an important role in graph drawing algorithms based on the Sugiyama layering approach. Moreover,...
Parameterized Complexity: Exponential Speed-Up for Planar Graph Problems (2004)
Jochen Alber, Henning Fernau, Rolf Niedermeier
We discuss general techniques, centered around the "Layerwise Separation Property " (LSP) of a planar graph problem, that allow to develop algorithms with running |G|, given an instance G...
problems. In Scandinavian Workshop on Algorithm Theory, pages 97–110, (2003)
Daniel M. Klein, Jochen Alber, Hans L. Bodlaender, Henning Fernau, Rolf Niedermeier, Alewyn P. Burger, ...
A lottery is a game in which a person chooses n numbers from a universal set of m numbers to form a ticket, and where a winning ticket of t numbers is chosen and where the person wins if k or more of...
Graph separators: a parameterized view (2001)
Jochen Alber, Henning Fernau, Rolf Niedermeier
Graph separation is a well-known tool to make (hard) graph problems accessible to a divide and conquer approach. We show how to use graph separator theorems in combination with (linear) problem...
Graph separators: a parameterized view (2001)
Jochen Alber, Henning Fernau, Rolf Niedermeier
Abstract. Graph separation is a well-known tool to make (hard) graph problems accessible to a divide and conquer approach. We show how to use graph separator theorems in combination with (linear)...
Graph separators: a parameterized view (2001)
Jochen Alber, Henning Fernau, Rolf Niedermeier
Abstract. Graph separation is a well-known tool to make (hard) graph problems accessible for a divide and conquer approach. We show how to use graph separator theorems in order to develop xed...
Parameterized complexity: exponential speed-up for planar graph problems (2001)
Jochen Alber, Henning Fernau, Rolf Niedermeier
Abstract. A parameterized problem is xed parameter tractable if it admits a solving algorithm whose running time on input instance (I; k) is f(k) jIj, where f is an arbitrary function depending only...
Parameterized complexity: exponential speed-up for planar graph problems (2001)
Jochen Alber, Henning Fernau, Rolf Niedermeier
A parameterized problem is called xed parameter tractable if it admits a solving algorithm whose running time on input instance (I; k) is f(k) jIj , where f is an arbitrary function depending only on...
Henning Fernau, Henning Fernau, Henning Fernau
We sketch possible applications of grammatical inference techniques to problems arising in the context of XML. The idea is to infer document type denitions (DTDs) of XML documents in situations when...
Parameterized complexity: exponential speed-up for planar graph problems (2001)
Jochen Alber, Henning Fernau, Rolf Niedermeier
We discuss general techniques, centered around the “Layerwise Separation Property” (LSP) of a planar graph problem, that allow to develop algorithms with running time c √ k |G|, given an...
Graph separators: a parameterized view (2001)
Jochen Alber, Henning Fernau, Rolf Niedermeier
Abstract. Graph separation is a well-known tool to make (hard) graph problems accessible to a divide-and-conquer approach. We show how to use graph separator theorems in combination with (linear)...
Parameterized Complexity: Exponential (2001)
Jochen Alber, Henning Fernau, Rolf Niedermeier
A parameterized problem is called xed parameter tractable if it admits a solving algorithm whose running time on input instance (I; k) is f(k) jIj where f is an arbitrary function depending only on...
Parameterized complexity: exponential speed-up for planar graph problems (2001)
Jochen Alber, Henning Fernau, Rolf Niedermeier
We discuss general techniques, centered around the “Layerwise Separation Property” (LSP) of a planar graph problem, that allow to develop algorithms with running time c √ k |G|, given an...
Jochen Alber, Henning Fernau, Rolf Niedermeier, Hongbing Fan, Michael R. Fellows, ...
We establish a refined search tree technique for the parameterized Dominating Set problem on planar graphs. Here, we are given an undirected graph and we ask for a set of at most k vertices such that...
Decidability of code properties (2000)
Henning Fernau, Klaus Reinhard, Ludwig Staiger
Abstract. We explore the borderline between decidability and undecidability of the following question: "Let C be a class of codes. Given a machine M of type X, is it decidable whether the...
Efficient Learning of Some Linear Simple Matrix Languages (2000)
Henning Fernau, Henning Fernau
We show that so-called deterministic even linear simple matrix grammars can be inferred in polynomial time using the query-based learner-teacher model MAT proposed by Angluin for learning...
K-Gram Extensions Of Terminal Distinguishable Languages (2000)
We show how k-grams can be used to extend classes of terminal distinguishable right-linear languages (k-TDRL). Moreover, we present an efficient identification algorithm for k-TDRL languages. Our...
On Learning Function Distinguishable Languages (2000)
Henning Fernau, Henning Fernau, Henning Fernau
We show how appropriately chosen functions which we call distinguishing can be used to make deterministic finite automata backward deterministic. These ideas can be exploited to design regular...
Parallel Communicating Grammar Systems with Terminal Transmission (2000)
Henning Fernau, Henning Fernau, Henning Fernau
We introduce a new variant of PC grammar systems, called PC grammar systems with terminal transmission, PCGSTT for short. We show that right-linear centralized PCGSTT have nice formal language...
Fixed Parameter Algorithms for Planar Dominating Set and Related Problems (2000)
Jochen Alber, Hans L. Bodlaender, Henning Fernau, Rolf Niedermeier
We present an algorithm that constructively produces a solution to the k-dominating set problem for planar graphs in time O(c # k n), where c = 3 6 # 34 . To obtain this result, we show that the...
Fixed Parameter Algorithms for Planar Dominating Set and Related Problems (2000)
Jochen Alber, Hans L. Bodlaender, Henning Fernau, Rolf Niedermeier
We present an algorithm that constructively produces a solution to the k-dominating set problem for planar graphs in time O(c p k n), where c = 3 6 p 34 . To obtain this result, we show that the...
PC grammar systems with terminal transmission (2000)
We introduce a new variant of PC grammar systems, called PC grammar systems with terminal transmission, PCGSTT for short, motivated by questions concerning grammatical inference of such systems. We...
Fixed parameter algorithms for planar dominating set and related problems (2000)
Jochen Alber, Hans L. Bodlaender, Henning Fernau, Rolf Niedermeier
We present an algorithm that constructively produces a solution to the k-dominating set problem for planar graphs in time O(c √ kn), where c = 36√34. To obtain this result, we show that the...
Regulated Grammars under Leftmost Derivation (1999)
. In this paper, we investigate various concepts of leftmost derivation in grammars controlled by bicoloured digraphs, paying specic attention to their descriptive capacity. This approach allows us...
An Efficient Exact Algorithm for Constraint Bipartite Vertex Cover (1999)
Henning Fernau, Rolf Niedermeier
The "Constraint Bipartite Vertex Cover" problem (CBVC for short) is: given a bipartite graph G with n vertices and two positive integers k 1 ; k 2 , is there a vertex cover taking at most k...
On Accepting Pure Lindenmayer Systems (1999)
Henning Bordihn, Henning Fernau, Markus Holzer
. We consider pure Lindenmayer systems, more precisely, 0L and T0L systems as language accepting devices and compare them to their generating counterparts. Accepting Lindenmayer systems can be seen...
Learning of Terminal Distinguishable Languages (1999)
Henning Fernau, Henning Fernau, Henning Fernau
this paper are proper supersets of the language families TDRL (terminal
Decidability of Code Properties (1999)
Henning Fernau, Klaus Reinhardt, Ludwig Staiger
Introduction Surprisingly, there are very few results of the following kind: \Let C be a class of codes. Given a device D of some xed type, is it decidable whether the language L(D) dened by D is in...
Accepting Pure Grammars and Systems (1999)
Henning Bordihn, Henning Fernau, Markus Holzer
We consider several types of pure grammars and systems as language acceptors and compare them to their generating counterparts. In contrast with the case (considered in earlier papers of the authors)...
External Contextual and Conditional Languages (1999)
. We investigate three dierent aspects of external contextual languages, focusing mainly on linear selector sets: (1) comparison with conditional languages regarding their descriptive capacity (2) as...
An efficient exact algorithm for Constraint Bipartite Vertex Cover (1999)
Henning Fernau, Rolf Niedermeier
Abstract The "Constraint Bipartite Vertex Cover " problem (CBVC for short) is: given a bipartite graph G with n vertices and two positive integers k1; k2, is there a vertex cover...
Regulated Grammars with Leftmost Derivation (1998)
. In this paper, we investigate various concepts of leftmost derivation in grammars controlled by bicoloured digraphs, especially regarding their descriptive capacity. This approach allows us to...
Character Recognition with k-Head Finite Array Automata (1998)
Henning Fernau, Rudolf Freund, Markus Holzer
. We introduce the concept of k-head finite two-dimensional array automata and show how this model of two-dimensional array automata can be applied in the field of syntactic character recognition....
Cooperating/Distributed Grammar Systems { (1998)
Fakultat Informatik, Holger Petersen, Henning Bordihn, Erzsebet Csuhaj-varju, Volker Diekert, Henning Fernau, ...
This report contains abstracts of the lectures presented at the workshop \Formal Languages, Automata
Valences are a very simple and yet powerful method of regulated rewriting. In this paper we give an overview on different aspects of this subject. We discuss closure properties of valence languages....
On the Leftmost Derivation in Matrix Grammars (1997)
Jürgen Dassow, Henning Fernau, Gheorghe Paun
Matrix grammars are one of the classical topics of formal languages, more specically, regulated rewriting. Although this type of control on the work of context-free grammars is one of the earliest,...
How Powerful is Unconditional Transfer? - When UT meets AC. (1997)
Henning Fernau, Henning Fernau, Frank Stephan, Frank Stephan
. We prove that every recursively enumerable language can be generated by a programmed grammar with context-free core rules using unconditional transfer with leftmost derivation of type 3 or type 2....
Graph-Controlled Grammars as Language Acceptors (1997)
In this paper, we study the concept of accepting grammars within various forms of regulated grammars like programmed grammars, matrix (set) grammars, grammars with regular (set) control, periodically...
Unconditional Transfer in Regulated Rewriting (1997)
In this paper, we investigate the concept of unconditional transfer within various forms of regulated grammars like programmed grammars, matrix grammars, grammars with regular control, grammars...
Conditional Context-Free Languages of Finite Index (1997)
. We consider conditional context-free grammars that generate languages of finite index. Thereby, we solve an open problem stated in Dassow and Paun's monograph on regulated rewriting. Moreover,...
. Valences are a very simple and yet powerful method of regulated rewriting. In this paper we give an overview on different aspects of this subject. We discuss closure properties of valence...
A Remark on Parameterized Parallel Complexity (1997)
Henning Fernau, Klaus-Jörn Lange, Rolf Niedermeier
of the monotone circuit value problem MCVP to LP 2 given in [1], one sees that the implementation of a "copy"-operation (besides the logical operators) is missing, which seems to be an...
On Unconditional Transfer (1996)
. In this paper, we investigate the concept of unconditional transfer within various forms of regulated grammars like programmed grammars, matrix grammars, grammars with regular control, grammars...
Bounded Parallelism in Array Grammars Used for Character Recognition (1996)
. The aim of this paper is to elaborate the power of cooperation in generating and analysing (handwritten) characters by array grammars. We present various non-context-free sets of arrays that can be...
Remarks on Regulated Limited ET0L Systems and Regulated Context-Free Grammars (1996)
Henning Fernau, Dietmar Wätjen
We continue the studies of the second author on regulated uniformly k-limited and regulated k-limited ET0L systems. We focus on the permitting and forbidding random context regulation. Especially, we...
External Versus Internal Hybridization for Cooperating Distributed Grammar Systems (1996)
Henning Fernau, Markus Holzer, Rudolf Freund
. Mitrana and Paun commenced a study on cooperating distributed (CD) grammar systems with components working in different derivation modes, called hybrid CD grammar systems. In this paper, we...
Accepting Array Grammars With Control Mechanisms (1996)
. We consider (n-dimensional) array grammars in the accepting mode with various control mechanisms and compare these families of array grammars with the corresponding families obtained by array...
Unconditional Transfer in Regulated Rewriting (1996)
Henning Fernau, Henning Fernau, Henning Fernau
. In this paper, we investigate the concept of unconditional transfer within various forms of regulated grammars like programmed grammars, matrix grammars, grammars with regular control, grammars...
Accepting Multi-Agent Systems II (1996)
We continue our previous research on cooperating distributed grammar systems (CDGS) and variants thereof as language acceptors [16]. Here, we classify the accepting capacity of CDGS working in the...
Henning Fernau, Klaus-Jörn Lange, Klaus Reinhardt
. We show the equivalence of deterministic auxiliary pushdown automata to owner write PRAMs in a fairly large setting by proving that DAuxPDA-TISP \Gamma f O(1) ; log g \Delta and CROW-TIPR \Gamma...
Scattered Context Grammars with Regulation (1996)
In this paper, we consider generating and accepting (unordered) scattered context grammars with unconditional transfer and characterize the such-defined language classes, comparing them mutually and...
Accepting Pure Grammars (1996)
Henning Bordihn, Henning Fernau, Markus Holzer
. We consider several types of pure grammars as language acceptors and compare them to their generating counterparts. The focus is on pure grammars with controlled derivations (regulated rewriting)....
Closure Properties of Ordered Languages (1996)
. In this note, we solve questions regarding closure properties of ordered languages. Especially, ordered languages form a full abstract family of recursive languages which is neither intersection-...
Bidirectional Cooperating Distributed Grammar Systems (1996)
Henning Fernau, Henning Fernau, Henning Fernau, Markus Holzer, Markus Holzer, Markus Holzer
We consider bidirectional cooperating distributed (BCD) grammar systems in the sense of Asveld. Independently of their mode , , =, , or t, BCD grammar systems with two components characterize the...
Regulated Finite Index Language Families Collapse (1996)
Henning Fernau, Henning Fernau, Henning Fernau, Markus Holzer, Markus Holzer, Markus Holzer
. We prove normal form theorems for programmed, ordered, and random context, context-free grammars as well as context-free grammars with regular context conditions of finite index. Based on these...
Accepting Multi-Agent Systems II (1996)
We continue our previous research on cooperating distributed grammar systems (CDGS) and variants thereof as language acceptors [16]. Here, we classify the accepting capacity of CDGS working in the...
On Grammar and Language Families (1996)
. In this paper, we emphasize the differences of grammar families and their properties versus language families and their properties. To this end, we investigate grammar families from an abstract...
A Predicate for Separating Language Classes (1995)
: We show how a predicate can be used to separate language classes in a remarkably concise way, e.g., L(P,CF\Gamma) and L(P,CF\Gamma,ut). It has been a long-standing open problem whether appearance...
Accepting Grammars and Systems: An Overview (1995)
Henning Bordihn, Henning Fernau
We investigate several kinds of regulated rewriting (matrix, ordered, programmed, and variants thereof) and of parallel rewriting mechanisms (Lindenmayer systems, uniformly limited Lindenmayer...
Accepting Programmed Grammars without Nonterminals (1995)
Henning Bordihn, Fakultat Fur Informatik, Henning Fernau, Fur Informatik
this paper, we consider the pure versions of this grammar type where we give up the distinction between terminal and nonterminal symbols. Such pure grammars are of interest because of the following...
Accepting Grammars and Systems: An Overview (1995)
Henning Bordihn, Henning Fernau
: We investigate several kinds of regulated rewriting (matrix, ordered, programmed, and variants thereof) and of parallel rewriting mechanisms (Lindenmayer systems, uniformly limited Lindenmayer...
IIFS and codes (Extended Version) (1995)
: In the beginning of the eighties, Hutchinson and Hata proposed a mechanism to describe fractal images which today is well known as iterated function systems (IFS). Subsequently, Marion, Barnsley,...
Accepting Grammars and Systems (1995)
Henning Bordihn, Fakultat Fur Informatik, Henning Fernau, Lehrstuhl Informatik Fur
We investigate several kinds of regulated rewriting (programmed, matrix, with regular control, ordered, and variants thereof) and of parallel rewriting mechanisms (Lindenmayer systems, uniformly...
in Nebenl"aufigkeitsmonoiden 10 (1995)
September Martin Kutrib, Thomas Worsch (hrsg, Inhaltsverzeichnis Programm, Henning Bordihn, Henning Fernau, ...
Valuations and unambiguity of languages, with applications to fractal geometry (1994)
Henning Fernau, Ludwig Staiger
Valuations--- morphisms from (\Sigma; \Delta; e) to ((0; 1); \Delta; 1)--- are a simple generalization of Bernoulli morphisms (distributions, measures) as introduced in [11, 5]. This paper shows that...
Accepting Grammars and Systems (1994)
Henning Bordihn Fakultat, Henning Bordihn, Fakultat Fur Informatik, Henning Fernau, Lehrstuhl Informatik Fur
We investigate several kinds of regulated rewriting (programmed, matrix, with regular control, ordered, and variants thereof) and of parallel rewriting mechanisms (Lindenmayer systems, uniformly...
Membership for Limited ET0L Languages Is Not Decidable (1994)
In this paper, we show how to encode arbitrary enumerable set of numbers given by register machines within limited EPT0L systems and programmed grammars with unconditional transfer. This result has...
Valuations and Unambiguity of Languages, with Applications to Fractal Geometry (1994)
Henning Fernau, Und Naturwissenschaftler, Ludwig Staiger
Valuations --- morphisms from (\Sigma ; \Delta; e) to ((0; 1); \Delta; 1) --- are a simple generalization of Bernoulli morphisms (distributions, measures) as introduced in [11, 5]. This paper shows...
Observations on Grammar and Language Families (1994)
In this report, we emphasize the differences of grammar families and their properties versus language families and their properties. To this end, we investigate grammar families from an abstract...
Infinite Iterated Function Systems (1994)
: We examine iterated function systems consisting of a countably infinite number of contracting mappings (IIFS). We state results analogous to the well-known case of finitely many mappings (IFS)....
Membership for Limited ET0L Languages Is Not Decidable (1994)
In this paper, we show how to encode arbitrary enumerable set of numbers given by register machines within limited EPT0L systems and programmed grammars with unconditional transfer. This result has...
Valuations and Unambiguity of Languages, with Applications to Fractal Geometry (1994)
Henning Fernau, Ludwig Staiger
. Valuations --- morphisms from (\Sigma ; \Delta; ) to ((0; 1); \Delta; 1) --- are a simple generalization of Bernoulli morphisms (distributions, measures) as introduced in [12, 20, 6, 4, 5, 21]....
Valuations of Languages, with Applications to Fractal Geometry (1994)
Henning Fernau, Lehrstuhl Informatik, F Ur
Valuations -- morphisms from (\Sigma ; \Delta; ) to ((0; 1); \Delta; 1) -- are a simple generalization of Bernoulli morphisms (distributions, measures) as introduced in [28, 41, 11, 9, 10, 42]. This...
Valuations and Unambiguity of Languages, with Applications to Fractal Geometry (1994)
Henning Fernau, Ludwig Staiger
. Valuations --- morphisms from (\Sigma ; \Delta; ) to ((0; 1); \Delta; 1) --- are a simple generalization of Bernoulli morphisms (distributions, measures) as introduced in [12, 20, 6, 4, 5, 21]....
Valuations Of Languages, With Applications To Fractal Geometry (1993)
Henning Fernau, Lehrstuhl Informatik, F Ur
. Valuations ---morphisms from (\Sigma ; \Delta; ) to ((0; 1); \Delta; 1)--- are a simple generalization of Bernoulli morphisms (distributions, measures) as introduced in [28, 41, 11, 9, 10, 42]....
Remarks on Propagating Partition-Limited ET0L Systems
: In this paper, we sharpen the results of Gartner on the universality of partition-limited ET0L systems by showing that such deterministic systems characterize the recursively enumerable sets, and,...
Decidability of Code Properties
Henning Fernau, Klaus Reinhardt, Ludwig Staiger, H. Fernau, K. Reinhardt, L. Staiger
We explore the borderline between decidability and undecidability of the following question: "Let C be a class of codes. Given a machine M of type X , is it decidable whether the language L(M)...