Author name cluster

D. Haussler

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

4 papers

1 author row

I&C Journal 1994 Journal Article

Predicting {0, 1}-Functions on Randomly Drawn Points

D. Haussler
N. Littlestone
M.K. Warmuth

We consider the problem of predicting {0, 1}-valued functions on R n and smaller domains, based on their values on randomly drawn points. Our model is related to Valiant′s PAC learning model, but does not require the hypotheses used for prediction to be represented in any specified form. In our main result we show how to construct prediction strategies that are optimal to within a constant factor for any reasonable class F of target functions. This result is based on new combinatorial results about classes of functions of finite VC dimension. We also discuss more computationally efficient algorithms for predicting indicator functions of axis-parallel rectangles, more general intersection closed concept classes, and halfspaces in R n. These are also optimal to within a constant factor. Finally, we compare the general performance of prediction strategies derived by our method to that of those derived from methods in PAC learning theory.

Details DOI

TCS Journal 1985 Journal Article

On total regulators generated by derivation relations

W. Bucher
A. Ehrenfeucht
D. Haussler

A derivation relation is a total regulator on Σ∗ if, for every language L ⊆ Σ∗, the set of all words derivable from L is a regular language. We show that for a wide class of derivation relations ⇒P ∗, ⇒P ∗ is a total regulator on Σ∗ if, and only if it is a well-quasi-order (wqo) on Σ∗. Using wqo theory, we give a characterization of all non-erasing pure context-free (0S) derivation relations which are total regulators.

Details DOI

TCS Journal 1985 Journal Article

The smallest automation recognizing the subwords of a text

A. Blumer
J. Blumer
D. Haussler
A. Ehrenfeucht
M.T. Chen
J. Seiferas

Let a partial deterministic finite automaton be a DFA in which each state need not have a transition edge for each letter of the alphabet. We demonstrate that the smallest partial DFA for the set of all subwords of a given word w, |w|>2, has at most 2|w|−2 states and 3|w|−4 transition edges, independently of the alphabet size. We give an algorithm to build this smallest partial DFA from the input w on-line in linear time.

Details DOI

TCS Journal 1983 Journal Article

On regularity of context-free languages

A. Ehrenfeucht
D. Haussler
G. Rozenberg

This paper considers conditions under which a context-free language is regular and conditions which imposed on (productions of) a rewriting system generating a context-free language will guarantee that the generated language is regular. In particular: 1. (1) necessary and sufficient conditions on productions of a unitary grammar are given that guarantee the generated language to be regular (a unitary grammar is a semi-Thue system in which the left-hand of each production is the empty word), and 2. (2) it is proved that commutativity of a linear language implies its regularity. To obtain the former result, we give a generalization of the Myhill–Nerode characterization of the regular languages in terms of well-quasi orders, along with a generalization of Higman's well-quasi order result concerning the subsequence embedding relation on Σ*. In obtaining the latter results, we introduce the class of periodic languages, and demonstrate how they can be used to characterize the commutative regular languages. Here we also utilize the theory of well-quasi orders.

Details DOI