Henning Fernau

From MaRDI portal
Person:198229

Available identifiers

zbMath Open fernau.henningWikidataQ59857702 ScholiaQ59857702MaRDI QIDQ198229

List of research outcomes

PublicationDate of PublicationType
When Stars Control a Grammar's Work2024-04-09Paper
Profit parameterizations of \textsc{Dominating Set}2024-02-23Paper
Computational completeness of simple semi-conditional insertion-deletion systems of degree (2,1)2024-02-09Paper
https://portal.mardi4nfdi.de/entity/Q61870482024-02-05Paper
Synchronizing deterministic push-down automata can be really hard2024-02-02Paper
Investigations on the power of matrix insertion-deletion systems with small sizes2023-11-30Paper
https://portal.mardi4nfdi.de/entity/Q60706102023-11-23Paper
The space complexity of sum labelling2023-10-30Paper
Recognizing well-dominated graphs is coNP-complete2023-10-12Paper
Parameterizing path partitions2023-10-04Paper
Order Reconfiguration under Width Constraints2023-09-20Paper
Extension of some edge graph problems: standard, parameterized and approximation complexity2023-09-14Paper
On the generative capacity of matrix insertion-deletion systems of small sum-norm2023-09-08Paper
https://portal.mardi4nfdi.de/entity/Q61684162023-08-08Paper
Combinatorial properties and recognition of unit square visibility graphs2023-05-12Paper
Minimal Roman dominating functions: extensions and enumeration2023-05-05Paper
Preface of the special issue dedicated to selected papers from CSR 20202023-05-02Paper
Invited talks2023-03-22Paper
Synchronizing words and monoid factorization: a parameterized perspective2022-12-22Paper
Insertion-deletion systems with substitutions. I2022-12-16Paper
VALENCE GRAMMARS WITH TARGET SETS2022-12-06Paper
Pattern Matching with Variables2022-12-05Paper
Synchronizing words and monoid factorization, yielding a new parameterized complexity class?2022-11-17Paper
Properties of graphs specified by a regular language2022-08-30Paper
Improved descriptional complexity results on generalized forbidding grammars2022-08-04Paper
https://portal.mardi4nfdi.de/entity/Q50924262022-07-21Paper
https://portal.mardi4nfdi.de/entity/Q50892002022-07-18Paper
The space complexity of sum labelling2022-05-20Paper
Computer science -- theory and applications. 15th international computer science symposium in Russia, CSR 2020, Yekaterinburg, Russia, June 29 -- July 3, 2020. Proceedings2022-04-21Paper
Parsimonious computational completeness2022-03-25Paper
Properties of graphs specified by a regular language2022-03-25Paper
Adding matrix control: insertion-deletion systems with substitutions. III2022-03-24Paper
On the computational completeness of matrix simple semi-conditional grammars2022-03-14Paper
Insertion-deletion systems with substitutions I2022-02-28Paper
On the complexity of solution extension of optimization problems2022-02-01Paper
Synchronizing series-parallel deterministic finite automata with loops and related problems2022-01-12Paper
Generalized forbidding matrix grammars and their membrane computing perspective2021-12-01Paper
Self-Verifying Pushdown and Queue Automata2021-11-15Paper
Improved Descriptional Complexity Results for Simple Semi-Conditional Grammars2021-10-25Paper
On the power of generalized forbidding insertion-deletion systems2021-07-14Paper
Insertion-deletion with substitutions. II2021-07-14Paper
On the complexity of the smallest grammar problem over fixed alphabets2021-06-24Paper
Algorithmic aspects of upper edge domination2021-06-23Paper
https://portal.mardi4nfdi.de/entity/Q49949482021-06-22Paper
Aspects of upper defensive alliances2021-05-19Paper
On matrix ins-del systems of small sum-norm2020-10-22Paper
Universal insertion grammars of size two2020-10-13Paper
Diminishable parameterized problems and strict polynomial kernelization2020-09-08Paper
Parameterized Dynamic Variants of Red-Blue Dominating Set2020-07-20Paper
https://portal.mardi4nfdi.de/entity/Q51112442020-05-26Paper
Domination chain: characterisation, classical complexity, parameterised complexity and approximability2020-05-18Paper
Descriptional complexity of matrix simple semi-conditional grammars2020-05-12Paper
Regulated tree automata2020-05-12Paper
Extension of Vertex Cover and Independent Set in some classes of graphs2020-02-06Paper
Extension of some edge graph problems: standard and parameterized complexity2020-01-30Paper
https://portal.mardi4nfdi.de/entity/Q52083732020-01-15Paper
Complexity of independency and cliquy trees2019-12-30Paper
Modern aspects of complexity within formal languages2019-12-04Paper
Improved descriptional complexity results on generalized forbidding grammars2019-10-10Paper
Valuations and unambiguity of languages, with applications to fractal geometry2019-04-29Paper
https://portal.mardi4nfdi.de/entity/Q46230372019-02-18Paper
On path-controlled insertion-deletion systems2019-01-25Paper
On describing the regular closure of the linear languages with graph-controlled insertion-deletion systems2018-11-01Paper
Computational completeness of simple semi-conditional insertion-deletion systems2018-10-18Paper
Diminishable parameterized problems and strict polynomial kernelization2018-09-06Paper
New nonterminal complexity results for semi-conditional grammars2018-09-06Paper
Problems on finite automata and the exponential time hypothesis2018-08-20Paper
The complexity of probabilistic lobbying2018-08-17Paper
Clustering with lower-bounded sizes. A general graph-theoretic framework2018-07-26Paper
Minimizing rules and nonterminals in semi-conditional grammars: non-trivial for the simple case2018-06-26Paper
Extremal kernelization: a commemorative paper2018-06-15Paper
Revisiting Shinohara's algorithm for computing descriptive patterns2018-06-05Paper
Simple picture processing based on finite automata and regular grammars2018-05-08Paper
https://portal.mardi4nfdi.de/entity/Q46364852018-04-19Paper
On the Generative Power of Graph-Controlled Insertion-Deletion Systems with Small Sizes2018-03-29Paper
The many facets of upper domination2018-03-13Paper
Non-Isometric Contextual Array Grammars and the Role of Regular Control and Local Selectors2018-01-19Paper
On the (adjacency) metric dimension of corona and strong product graphs and their local variants: combinatorial and computational results2018-01-11Paper
https://portal.mardi4nfdi.de/entity/Q45982642017-12-19Paper
Universal matrix insertion grammars with small size2017-08-31Paper
Graph-controlled insertion-deletion systems generating language classes beyond linearity2017-08-31Paper
Computational completeness of path-structured graph-controlled insertion-deletion systems2017-08-22Paper
Characterization and complexity results on jumping finite automata2017-06-19Paper
Contextual array grammars with matrix control, regular control languages, and tissue P systems control2017-06-15Paper
On the computational completeness of graph-controlled insertion-deletion systems with binary sizes2017-06-15Paper
Parikh Images of Matrix Ins-Del Systems2017-05-19Paper
The differential and the roman domination number of a graph2017-03-14Paper
https://portal.mardi4nfdi.de/entity/Q29638972017-02-21Paper
Learning Tree Languages2017-02-15Paper
https://portal.mardi4nfdi.de/entity/Q29550042017-01-24Paper
https://portal.mardi4nfdi.de/entity/Q31788732016-12-20Paper
Contextual Array Grammars with Matrix and Regular Control2016-11-09Paper
Descriptional Complexity of Graph-Controlled Insertion-Deletion Systems2016-11-09Paper
Algorithmic Aspects of Upper Domination: A Parameterised Perspective2016-11-09Paper
Problems on Finite Automata and the Exponential Time Hypothesis2016-11-09Paper
Using Parametric Transformations Toward Polynomial Kernels for Packing Problems Allowing Overlaps2016-10-24Paper
Upper Domination: Complexity and Approximation2016-09-29Paper
Generative Power of Matrix Insertion-Deletion Systems with Context-Free Insertion or Deletion2016-09-28Paper
On the parameterised complexity of string morphism problems2016-09-21Paper
https://portal.mardi4nfdi.de/entity/Q28118182016-06-10Paper
The Finite Index Restriction Meets Hybrid Modes in Cooperating Distributed Grammar Systems2016-04-15Paper
On the Complexity Landscape of the Domination Chain2016-03-23Paper
Scanning Pictures the Boustrophedon Way2016-03-10Paper
Weak total resolvability in graphs2016-01-26Paper
Data reductions and combinatorial bounds for improved approximation algorithms2015-12-30Paper
Polynomial inference of universal automata from membership and equivalence queries2015-12-28Paper
On the partition dimension of unicyclic graphs2015-11-09Paper
Contextual array grammars and array P systems2015-10-06Paper
Kernelization Algorithms for Packing Problems Allowing Overlaps2015-09-30Paper
Jumping Finite Automata: Characterizations and Complexity2015-09-23Paper
Non-isometric Contextual Array Grammars with Regular Control and Local Selectors2015-09-15Paper
Approximation Algorithms Inspired by Kernelization Methods2015-09-11Paper
Computing the metric dimension for chain graphs2015-06-02Paper
Pattern matching with variables: a multivariate complexity analysis2015-06-01Paper
ON THE LEFTMOST DERVIATION IN MATRIX GRAMMARS2015-04-29Paper
A survey on alliances and related parameters in graphs2015-03-05Paper
A multi-parameter analysis of hard problems on deterministic finite automata2015-02-20Paper
On the parameterized complexity of vertex cover and edge cover with connectivity constraints2014-12-22Paper
Combinatorics for smaller kernels: the differential of a graph2014-12-02Paper
Kernel(s) for problems with no kernel2014-09-09Paper
Saving on Phases: Parameterized Approximation for Total Vertex Cover2014-08-19Paper
Notions of Metric Dimension of Corona Products: Combinatorial and Computational Results2014-06-24Paper
Computing the differential of a graph: hardness, approximability and exact algorithms2014-05-05Paper
https://portal.mardi4nfdi.de/entity/Q54139092014-05-02Paper
Packing paths: recycling saves time2014-04-16Paper
Digraphs of bounded elimination width2014-04-02Paper
A novel parameterised approximation algorithm for \textsc{minimum vertex cover}2014-01-13Paper
Array Insertion and Deletion P Systems2013-06-28Paper
Pattern Matching with Variables: A Multivariate Complexity Analysis2013-06-14Paper
Exact exponential-time algorithms for finding bicliques2013-04-04Paper
MAT Learning of Universal Automata2013-03-18Paper
A Multivariate Analysis of Some DFA Problems2013-03-18Paper
Exact and parameterized algorithms for \textsc{Max Internal Spanning Tree}2013-03-05Paper
Parameterized measure \& conquer for problems with no small kernels2012-11-21Paper
Cooperating Distributed Tree Automata2012-11-01Paper
Lower bounds on the differential of a graph2012-10-26Paper
https://portal.mardi4nfdi.de/entity/Q31659602012-10-19Paper
Charge and reduce: A fixed-parameter algorithm for string-to-string correction2012-10-16Paper
On families of categorial grammars of bounded value, their learnability and related complexity questions2012-10-11Paper
An exact exponential-time algorithm for the directed maximum leaf spanning tree problem2012-09-13Paper
Parameterized Approximation Algorithms for Hitting Set2012-07-16Paper
Constraint bipartite vertex cover: simpler exact algorithms and implementations2012-07-03Paper
An exact exponential time algorithm for \textsc{Power} \textsc{Dominating} \textsc{Set}2012-04-26Paper
https://portal.mardi4nfdi.de/entity/Q53899962012-04-24Paper
An exact algorithm for the maximum leaf spanning tree problem2012-01-09Paper
Breaking the \(2^{n}\)-barrier for irredundance: two lines of attack2011-08-23Paper
Facility location problems: a parameterized view2011-08-10Paper
On the Expressive Power of Valences in Cooperating Distributed Grammar Systems2011-06-24Paper
Ranking and Drawing in Subexponential Time2011-05-19Paper
Parameterized algorithmics for d-H<scp>itting</scp> S<scp>et</scp>2011-01-20Paper
A new upper bound for Max-2-SAT: A graph-theoretic approach2011-01-20Paper
Combining Two Worlds: Parameterised Approximation for Vertex Cover2010-12-09Paper
Enumerate and Measure: Improving Parameter Budget Management2010-12-07Paper
Hölder Norms and a Hierarchy Theorem for Parameterized Classes of CCG2010-09-10Paper
Comparing trees via crossing minimization2010-08-18Paper
The Curse of Connectivity: t-Total Vertex (Edge) Cover2010-07-20Paper
A Faster Exact Algorithm for the Directed Maximum Leaf Spanning Tree Problem2010-06-22Paper
A Parameterized Route to Exact Puzzles: Breaking the 2 n -Barrier for Irredundance2010-05-28Paper
Finding Consistent Categorial Grammars of Bounded Value: A Parameterized Approach2010-05-26Paper
Minimum dominating set of queens: a trivial programming exercise?2010-05-05Paper
Parameterized algorithms for \(d\)-hitting set: the weighted case2010-04-15Paper
A top-down approach to search-trees: Improved algorithmics for 3-hitting set2010-03-04Paper
A parameterized perspective on packing paths of length two2010-02-24Paper
PROGRAMMED GRAMMARS WITH RULE QUEUES2010-01-29Paper
An Amortized Search Tree Analysis for k-Leaf Spanning Tree2010-01-28Paper
Exact and Parameterized Algorithms for Max Internal Spanning Tree2010-01-21Paper
An Exact Algorithm for the Maximum Leaf Spanning Tree Problem2010-01-14Paper
The Complexity of Probabilistic Lobbying2009-11-17Paper
Graph Drawing2009-08-11Paper
On the complement graph and defensive \(k\)-alliances2009-06-24Paper
Vertex and edge covers with clustering properties: Complexity and algorithms2009-06-24Paper
Searching Trees: An Essay2009-06-03Paper
Algorithms for learning regular expressions from positive data2009-04-16Paper
A simultaneous reduction of several measures of descriptional complexity in scattered context grammars2009-03-23Paper
Parameterized algorithmics for linear arrangement problems2009-03-04Paper
Offensive \(r\)-alliances in graphs2009-03-04Paper
A bounded search tree algorithm for parameterized face cover2009-02-23Paper
A New Upper Bound for Max-2-SAT: A Graph-Theoretic Approach2009-02-03Paper
Power Domination in $\mathcal{O}^*(1.7548^n)$ Using Reference Search Trees2009-01-29Paper
A Parameterized Perspective on Packing Paths of Length Two2009-01-27Paper
Comparison of some descriptional complexities of 0L systems obtained by a unifying approach2008-10-08Paper
Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size2008-08-14Paper
https://portal.mardi4nfdi.de/entity/Q35170932008-08-12Paper
https://portal.mardi4nfdi.de/entity/Q35170982008-08-12Paper
Fixed parameter algorithms for one-sided crossing minimization revisited2008-08-08Paper
Learning tree languages from text2008-07-21Paper
Facility Location Problems: A Parameterized View2008-07-10Paper
Constraint Bipartite Vertex Cover Simpler Exact Algorithms and Implementations2008-06-19Paper
https://portal.mardi4nfdi.de/entity/Q35058842008-06-11Paper
edge dominating set: Efficient Enumeration-Based Exact Algorithms2008-06-03Paper
Kernels: Annotated, Proper and Induced2008-06-03Paper
Exact Algorithms for Maximum Acyclic Subgraph on a Superclass of Cubic Graphs2008-03-25Paper
A sum labelling for the generalised friendship graph2008-02-14Paper
R<scp>OMAN DOMINATION</scp>: a parameterized perspective†2008-01-28Paper
Decidability of code properties2007-11-14Paper
Parameterized Algorithms for Finding Small Independent Dominating Sets in Planar Graphs2007-05-29Paper
Speeding up Exact Algorithms With High Probability2007-05-29Paper
Parameterized Algorithms for Hitting Set: The Weighted Case2007-05-02Paper
Iterated sequential transducers as language generating devices2007-01-09Paper
FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science2006-11-14Paper
SOFSEM 2006: Theory and Practice of Computer Science2006-11-14Paper
SOFSEM 2006: Theory and Practice of Computer Science2006-11-14Paper
Algorithmic Learning Theory2006-11-01Paper
Grammatical Inference: Algorithms and Applications2006-10-20Paper
Grammatical Inference: Algorithms and Applications2006-10-20Paper
https://portal.mardi4nfdi.de/entity/Q54859902006-09-06Paper
Two-Layer Planarization: Improving on Parameterized Algorithmics2006-04-03Paper
A refined search tree technique for dominating set on planar graphs2005-12-07Paper
SOFSEM 2005: Theory and Practice of Computer Science2005-12-07Paper
STACS 20052005-12-02Paper
Mathematical Foundations of Computer Science 20042005-08-22Paper
https://portal.mardi4nfdi.de/entity/Q30222932005-06-23Paper
https://portal.mardi4nfdi.de/entity/Q46628292005-03-30Paper
Parameterized complexity: exponential speed-up for planar graph problems2004-11-23Paper
https://portal.mardi4nfdi.de/entity/Q48207852004-10-01Paper
Graph separators: A parameterized view2004-08-19Paper
https://portal.mardi4nfdi.de/entity/Q30467032004-08-12Paper
https://portal.mardi4nfdi.de/entity/Q48086792004-08-12Paper
https://portal.mardi4nfdi.de/entity/Q48089282004-08-12Paper
https://portal.mardi4nfdi.de/entity/Q47379152004-08-11Paper
https://portal.mardi4nfdi.de/entity/Q44732352004-08-04Paper
https://portal.mardi4nfdi.de/entity/Q44739882004-08-04Paper
https://portal.mardi4nfdi.de/entity/Q44653342004-05-27Paper
Identifying terminal distinguishable languages2004-05-27Paper
https://portal.mardi4nfdi.de/entity/Q44584892004-03-18Paper
https://portal.mardi4nfdi.de/entity/Q44532012004-03-07Paper
https://portal.mardi4nfdi.de/entity/Q44403892003-12-17Paper
https://portal.mardi4nfdi.de/entity/Q44378142003-12-15Paper
https://portal.mardi4nfdi.de/entity/Q44363542003-12-04Paper
Parallel grammars: A phenomenology2003-08-25Paper
Identification of function distinguishable languages.2003-08-17Paper
On the degree of scattered context-sensitivity.2003-08-17Paper
Nonterminal complexity of programmed grammars.2003-08-17Paper
https://portal.mardi4nfdi.de/entity/Q44144962003-07-25Paper
https://portal.mardi4nfdi.de/entity/Q27089602003-07-09Paper
Hybrid modes in cooperating distributed grammar systems: Combining the \(t\)-mode with the modes \(\leqslant k\) and \(=k\)2003-05-25Paper
https://portal.mardi4nfdi.de/entity/Q47974302003-03-13Paper
https://portal.mardi4nfdi.de/entity/Q47931272003-02-18Paper
Even linear simple matrix languages: formal language properties and grammatical inference.2003-01-21Paper
Iterated function systems and control languages2003-01-14Paper
Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs2002-12-01Paper
https://portal.mardi4nfdi.de/entity/Q47821132002-11-27Paper
https://portal.mardi4nfdi.de/entity/Q47791382002-11-25Paper
https://portal.mardi4nfdi.de/entity/Q47803382002-11-19Paper
https://portal.mardi4nfdi.de/entity/Q45513702002-09-05Paper
Sequential grammars and automata with valences2002-07-15Paper
https://portal.mardi4nfdi.de/entity/Q45357992002-06-16Paper
https://portal.mardi4nfdi.de/entity/Q45300002002-05-07Paper
https://portal.mardi4nfdi.de/entity/Q27706752002-02-13Paper
https://portal.mardi4nfdi.de/entity/Q27296662001-12-18Paper
https://portal.mardi4nfdi.de/entity/Q27540032001-11-11Paper
https://portal.mardi4nfdi.de/entity/Q27521452001-10-21Paper
Hybrid modes in cooperating distributed grammar systems: Internal versus external hybridization2001-08-20Paper
Parallel communicating grammar systems with terminal transmission2001-08-20Paper
An Efficient Exact Algorithm for Constraint Bipartite Vertex Cover2001-07-23Paper
https://portal.mardi4nfdi.de/entity/Q27219712001-07-11Paper
https://portal.mardi4nfdi.de/entity/Q45203342001-02-26Paper
Regulated grammars under leftmost derivation2001-02-22Paper
https://portal.mardi4nfdi.de/entity/Q49395772000-06-13Paper
https://portal.mardi4nfdi.de/entity/Q49391952000-06-04Paper
https://portal.mardi4nfdi.de/entity/Q49419172000-03-19Paper
https://portal.mardi4nfdi.de/entity/Q49420502000-03-19Paper
https://portal.mardi4nfdi.de/entity/Q49392022000-02-23Paper
https://portal.mardi4nfdi.de/entity/Q46993001999-11-10Paper
https://portal.mardi4nfdi.de/entity/Q42181521999-08-23Paper
https://portal.mardi4nfdi.de/entity/Q42476801999-06-16Paper
https://portal.mardi4nfdi.de/entity/Q42261881999-01-24Paper
Remarks on regulated limited ET0L systems and regulated context-free grammars1998-08-13Paper
https://portal.mardi4nfdi.de/entity/Q43758121998-06-02Paper
https://portal.mardi4nfdi.de/entity/Q43658211998-02-26Paper
Unconditional transfer in regulated rewriting1997-12-10Paper
https://portal.mardi4nfdi.de/entity/Q31251811997-08-07Paper
https://portal.mardi4nfdi.de/entity/Q31251701997-03-16Paper
A note on uniformly limited ET0L systems with unique interpretation1997-02-28Paper
Valuations of languages, with applications to fractal geometry1997-02-28Paper
https://portal.mardi4nfdi.de/entity/Q48867951996-10-15Paper
https://portal.mardi4nfdi.de/entity/Q48644651996-06-27Paper
Valuations, regular expressions, and fractal geometry1996-06-24Paper
Remarks on accepting parallel systems1996-06-23Paper
https://portal.mardi4nfdi.de/entity/Q48589341996-05-27Paper
Accepting grammars with regulation1995-10-10Paper
https://portal.mardi4nfdi.de/entity/Q48401611995-07-20Paper
Infinite Iterated Function Systems1995-02-02Paper
https://portal.mardi4nfdi.de/entity/Q43068901994-09-21Paper
https://portal.mardi4nfdi.de/entity/Q32101891991-01-01Paper

Research outcomes over time


Doctoral students

No records found.


Known relations from the MaRDI Knowledge Graph

PropertyValue
MaRDI profile typeMaRDI person profile
instance ofhuman


This page was built for person: Henning Fernau