Two-layer planarization: improving on parameterized algorithmics.
Learning tree languages from text
We study the problem of learning regular tree languages from text. We show that the framework of function distinguishability, as introduced by the author in [ (2003) 1679–1711], can be generalized from the case of string languages towards tree languages. This provides a large source of identifiable classes of regular tree languages. Each of these classes can be characterized in various ways. Moreover, we present a generic inference algorithm with polynomial update time and prove...
Decidability of code properties
We explore the borderline between decidability and undecidability of the following question: “Let be a class of codes. Given a machine of type , is it decidable whether the language lies in or not?” for codes in general, -codes, codes of finite and bounded deciphering delay, prefix, suffix and bi(pre)fix codes, and for finite automata equipped with different versions of push-down stores and counters.
Weak Total Resolvability In Graphs
A vertex v ∈ V (G) is said to distinguish two vertices x, y ∈ V (G) of a graph G if the distance from v to x is di erent from the distance from v to y. A set W ⊆ V (G) is a total resolving set for a graph G if for every pair of vertices x, y ∈ V (G), there exists some vertex w ∈ W − {x, y} which distinguishes x and y, while W is a weak total resolving set if for every x ∈ V (G)−W and y ∈ W, there exists some w ∈ W −{y} which distinguishes x and y. A weak total resolving set of minimum cardinality...
Page 1