The Experts below are selected from a list of 27918 Experts worldwide ranked by ideXlab platform
Hiroki Arimura - One of the best experts on this subject based on the ideXlab platform.
-
inductive inference of unbounded unions of Pattern Languages from positive data
Algorithmic Learning Theory, 1996Co-Authors: Takeshi Shinohara, Hiroki ArimuraAbstract:A Pattern is a string consisting of constant symbols and variables. The language of a Pattern is the set of constant strings obtained by substituting nonempty constant strings for variables in the Pattern. For any fixed k, the class of unions of at most k Pattern Languages is already shown to be inferable from positive data. The class of all the unions of arbitrarily finitely many Pattern Languages is not inferable, because any constant string defines a singleton set consisting of itself, and the class of unions contains all the finite Languages. A proper Pattern is a Pattern that contains at least one variable. The language of a proper Pattern is infinite. In this paper, we consider the class of unions when Patterns are restricted to be proper and show that the class is not inferable from positive data. A regular Pattern is a Pattern that contains at most one occurrence of every variable. When regular Patterns are restricted not to contain more than l consecutive occurrences of constant symbols for some l, the class of unions is shown to be inferable from positive data.
-
finding minimal generalizations for unions of Pattern Languages and its application to inductive inference from positive data
Symposium on Theoretical Aspects of Computer Science, 1994Co-Authors: Hiroki Arimura, Takeshi Shinohara, Setsuko OtsukiAbstract:A Pattern is a string of constant symbols and variables. The language defined by a Pattern p is the set of constant strings obtained from p by substituting nonempty constant strings for variables in p. In this paper we are concerning with polynomial time inference from positive data of the class of unions of a bounded number of Pattern Languages. We introduce a syntactic notion of minimal multiple generalizations (mmg for short) to study the inferability of classes of unions. If a Pattern p is obtained from another Pattern q by substituting nonempty Patterns for variables in q, q is said to be more general than p. A set of Patterns defines a union of their Languages. A set Q of Patterns is said to be more general than a set P of Patterns if for any Pattern p in P there exists a more general Pattern q in Q than p. Clearly more general set of Patterns defines larger unions. A k-minimal multiple generalization (k-mmg) of a set S of strings is a minimally general set of at most k Patterns that defines a union containing S. The syntactic notion of minimality enables us to efficiently compute a candidate for a semantically minimal concept. We present a general methodology for designing an efficient algorithm to find a k-mmg. Under some conditions an mmg can be used as an appropriate hypothesis for inductive inference from positive data. As results several classes of unions of Pattern Languages are shown to be polynomial time inferable from positive data.
Takeshi Shinohara - One of the best experts on this subject based on the ideXlab platform.
-
developments from enquiries into the learnability of the Pattern Languages from positive data
Theoretical Computer Science, 2008Co-Authors: Takeshi ShinoharaAbstract:The Pattern Languages are Languages that are generated from Patterns, and were first proposed by Angluin as a non-trivial class that is inferable from positive data [D. Angluin, Finding Patterns common to a set of strings, Journal of Computer and System Sciences 21 (1980) 46-62; D. Angluin, Inductive inference of formal Languages from positive data, Information and Control 45 (1980) 117-135]. In this paper we chronologize some results that developed from the investigations on the inferability of the Pattern Languages from positive data.
-
inductive inference of unbounded unions of Pattern Languages from positive data
Algorithmic Learning Theory, 1996Co-Authors: Takeshi Shinohara, Hiroki ArimuraAbstract:A Pattern is a string consisting of constant symbols and variables. The language of a Pattern is the set of constant strings obtained by substituting nonempty constant strings for variables in the Pattern. For any fixed k, the class of unions of at most k Pattern Languages is already shown to be inferable from positive data. The class of all the unions of arbitrarily finitely many Pattern Languages is not inferable, because any constant string defines a singleton set consisting of itself, and the class of unions contains all the finite Languages. A proper Pattern is a Pattern that contains at least one variable. The language of a proper Pattern is infinite. In this paper, we consider the class of unions when Patterns are restricted to be proper and show that the class is not inferable from positive data. A regular Pattern is a Pattern that contains at most one occurrence of every variable. When regular Patterns are restricted not to contain more than l consecutive occurrences of constant symbols for some l, the class of unions is shown to be inferable from positive data.
-
finding minimal generalizations for unions of Pattern Languages and its application to inductive inference from positive data
Symposium on Theoretical Aspects of Computer Science, 1994Co-Authors: Hiroki Arimura, Takeshi Shinohara, Setsuko OtsukiAbstract:A Pattern is a string of constant symbols and variables. The language defined by a Pattern p is the set of constant strings obtained from p by substituting nonempty constant strings for variables in p. In this paper we are concerning with polynomial time inference from positive data of the class of unions of a bounded number of Pattern Languages. We introduce a syntactic notion of minimal multiple generalizations (mmg for short) to study the inferability of classes of unions. If a Pattern p is obtained from another Pattern q by substituting nonempty Patterns for variables in q, q is said to be more general than p. A set of Patterns defines a union of their Languages. A set Q of Patterns is said to be more general than a set P of Patterns if for any Pattern p in P there exists a more general Pattern q in Q than p. Clearly more general set of Patterns defines larger unions. A k-minimal multiple generalization (k-mmg) of a set S of strings is a minimally general set of at most k Patterns that defines a union containing S. The syntactic notion of minimality enables us to efficiently compute a candidate for a semantically minimal concept. We present a general methodology for designing an efficient algorithm to find a k-mmg. Under some conditions an mmg can be used as an appropriate hypothesis for inductive inference from positive data. As results several classes of unions of Pattern Languages are shown to be polynomial time inferable from positive data.
Thomas Zeugmann - One of the best experts on this subject based on the ideXlab platform.
-
stochastic finite learning of the Pattern Languages
Machine Learning, 2001Co-Authors: Peter Rossmanith, Thomas ZeugmannAbstract:The present paper proposes a new learning model—called stochastic finite learning—and shows the whole class of Pattern Languages to be learnable within this model. This main result is achieved by providing a new and improved average-case analysis of the Lange–Wiehagen (New Generation Computing, 8, 361–370) algorithm learning the class of all Pattern Languages in the limit from positive data. The complexity measure chosen is the total learning time, i.e., the overall time taken by the algorithm until convergence. The expectation of the total learning time is carefully analyzed and exponentially shrinking tail bounds for it are established for a large class of probability distributions. For every Pattern π containing k different variables it is shown that Lange and Wiehagen's algorithm possesses an expected total learning time of O(\hat\alpha^k \E\Lambda\log_{1/\beta}(k)), where \hat\alpha and β are two easily computable parameters arising naturally from the underlying probability distributions, and E[Λ] is the expected example string length. Finally, assuming a bit of domain knowledge concerning the underlying class of probability distributions, it is shown how to convert learning in the limit into stochastic finite learning.
-
learning one variable Pattern Languages in linear average time
Conference on Learning Theory, 1998Co-Authors: Rudiger Reischuk, Thomas ZeugmannAbstract:A new algorithm for learning one-variable Pattern Languages is proposed and analyzed with respect to its average-case behavior. We consider the total learning time that takes into account all operations till an algorithm has converged to a correct hypothesis. For the expectation it is shown that for almost all meaningful distributions defining how the Pattern variable is replaced by a string to generate random examples of the target Pattern language this algorithm converges within a constant number of rounds with a total learning time that is linear in the Pattern length. Thus, the algorithm is average-case optimal in a strong sense. Though one-variable Pattern Languages cannot be inferred finitely, our approach can also be considered as probabilistic finite learning with high confidence.
-
learning one variable Pattern Languages very efficiently on average in parallel and by asking queries
Algorithmic Learning Theory, 1997Co-Authors: Thomas Erlebach, Peter Rossmanith, Hans Stadtherr, Angelika Steger, Thomas ZeugmannAbstract:A Pattern is a finite string of constant and variable symbols. The langauge generated by a Pattern is the set of all strings of constant symbols which can be obtained from the Pattern by substituting non-empty strings for variables. We study the learnability of one-variable Pattern Languages in the limit with respect to the update time needed for computing a new single hypothesis and the expected total learning time taken until convergence to a correct hypothesis. Our results are as follows. First, we design a consistent and set-driven learner that, using the concept of descriptive Patterns, achieves update time O(n2logn), where n is the size of the input sample. The best previously known algorithm for computing descriptive one-variable Patterns requires time O(n4logn) (cf. Angluin, J. Comput. Systems Sci. 21 (1) (1980) 46-62). Second, we give a parallel version of this algorithm that requires time O(logn) and O(n3/logn) processors on an EREW-PRAM. Third, using a modified version of the sequential algorithm as a subroutine, we devise a learning algorithm for one-variable Patterns whose expected total learning time is O(l2logl) provided that sample strings are drawn from the target language according to a probability distribution with expected string length l. The probability distribution must be such that strings of equal length have equal probability, but can be arbitrary otherwise. Thus, we establish the first algorithm for learning one-variable Pattern Languages having an expected total learning time that provably differs from the update time by a constant factor only. Finally, we show how the algorithm for descriptive one-variable Patterns can be used for learning one-variable Patterns with a polynomial number of superset queries with respect to the one-variable Patterns as query language.
Barbara Mcmanus - One of the best experts on this subject based on the ideXlab platform.
-
evaluating Pattern Languages in participatory design
Human Factors in Computing Systems, 2002Co-Authors: Andy Dearden, Janet Finlay, Liz Allgar, Barbara McmanusAbstract:We present an evaluaion of Pattern Languages as tools for participatory design, based on three criteria, derived from the work of Christopher Alexander: empowering users, generative design and life-enhancing outcomes. Our results suggest that Pattern Languages can be used to enable users to participate in design, but that the role of facilitator and the form and physical presentaton of the Pattern language are factors in success.
-
Using Pattern Languages in Participatory Design
2002Co-Authors: Andy Dearden, Janet Finlay, Elizabeth Allgar, Barbara McmanusAbstract:In this paper, we examine the contribution that Pattern Languages could make to user participation in the design of interactive systems, and we report on our experiences of using Pattern Languages in this way. In recent years, there has been a growing interest in the use of Patterns and Pattern Languages in the design of interactive systems. Pattern Languages were originally developed by the architect, Christopher Alexander, both as a way of understanding the nature of building designs that promote a 'humane' or living built environment; and as a practical tool to aid in participatory design of buildings. Our experience suggests that Pattern Languages do have considerable potential to support participatory design in HCI, but that many pragmatic issues remain to be resolved.
-
Pattern Languages in Participatory Design
People and Computers XVI - Memorable Yet Invisible, 2002Co-Authors: Janet Finlay, Andy Dearden, Elizabeth Allgar, Barbara McmanusAbstract:In recent years the Human-Computer Interaction community has witnessed a growing interest in the use of design Patterns and Pattern Languages, a representation for design knowledge based on the work of the architect Christopher Alexander. In this paper, we re-examine Alexander’s work, highlighting his participatory approach to design, his use of Patterns in design generation and his ethical commitment to designing life-enhancing artefacts. Based on this review, we report on three studies exploring the use of Pattern Languages as tools to support a participatory approach to interactive systems design. Our results suggest that Pattern Languages can enable users to participate in a generative design process but that issues of form and facilitation need careful consideration.
-
CHI Extended Abstracts - Evaluating Pattern Languages in participatory design
CHI '02 extended abstracts on Human factors in computing systems - CHI '02, 2002Co-Authors: Andy Dearden, Janet Finlay, Liz Allgar, Barbara McmanusAbstract:We present an evaluaion of Pattern Languages as tools for participatory design, based on three criteria, derived from the work of Christopher Alexander: empowering users, generative design and life-enhancing outcomes. Our results suggest that Pattern Languages can be used to enable users to participate in design, but that the role of facilitator and the form and physical presentaton of the Pattern language are factors in success.
Daniel Reidenbach - One of the best experts on this subject based on the ideXlab platform.
-
Closure properties of Pattern Languages
Journal of Computer and System Sciences, 2017Co-Authors: Joel D. Day, Daniel Reidenbach, Markus L. SchmidAbstract:The terminal-free Pattern Languages are not closed under most standard operations.We achieve even stronger results for union and intersection of these Languages.Some of these results cease to hold if Patterns with terminal symbols are considered.We characterise unions of two NE-Pattern Languages that are an E-Pattern language.We characterise all unions of E-Pattern Languages that are an NE-Pattern language. Pattern Languages are a well-established class of Languages, but very little is known about their closure properties. In the present paper we establish a large number of closure properties of the terminal-free Pattern Languages, and we characterise when the union of two terminal-free Pattern Languages is again a terminal-free Pattern language. We demonstrate that the equivalent question for general Pattern Languages is characterised differently, and that it is linked to some of the most prominent open problems for Pattern Languages. We also provide fundamental insights into a well-known construction of E-Pattern Languages as unions of NE-Pattern Languages, and vice versa.
-
Developments in Language Theory - Closure Properties of Pattern Languages
Developments in Language Theory, 2014Co-Authors: Joel D. Day, Daniel Reidenbach, Markus L. SchmidAbstract:Pattern Languages are a well-established class of Languages that is particularly popular in algorithmic learning theory, but very little is known about their closure properties. In the present paper we establish a large number of closure properties of the terminal-free Pattern Languages, and we characterise when the union of two terminal-free Pattern Languages is again a terminal-free Pattern language. We demonstrate that the equivalent question for general Pattern Languages is characterised differently, and that it is linked to some of the most prominent open problems for Pattern Languages. We also provide fundamental insights into a well-known construction of E-Pattern Languages as unions of NE-Pattern Languages, and vice versa.
-
regular and context free Pattern Languages over small alphabets
Theoretical Computer Science, 2014Co-Authors: Daniel Reidenbach, Markus L. SchmidAbstract:Pattern Languages are generalisations of the copy language, which is a standard textbook example of a context-sensitive and non-context-free language. In this work, we investigate a counter-intuitive phenomenon: with respect to alphabets of size 2 and 3, Pattern Languages can be regular or context-free in an unexpected way. For this regularity and context-freeness of Pattern Languages, we give several sufficient and necessary conditions and improve known results.
-
A non-learnable class of E-Pattern Languages
Theoretical Computer Science, 2006Co-Authors: Daniel ReidenbachAbstract:We investigate the inferrability of E-Pattern Languages (also known as extended or erasing Pattern Languages) from positive data in Gold's learning model. As the main result, our analysis yields a negative outcome for the full class of E-Pattern Languages--and even for the subclass of terminal-free E-Pattern Languages--if the corresponding terminal alphabet consists of exactly two distinct letters. Furthermore, we present a positive result for a manifest subclass of terminal-free E-Pattern Languages. We point out that the considered problems are closely related to fundamental questions concerning the nondeterminism of E-Pattern Languages.
-
on the learnability of e Pattern Languages over small alphabets
Conference on Learning Theory, 2004Co-Authors: Daniel ReidenbachAbstract:This paper deals with two well discussed, but largely open problems on E-Pattern Languages, also known as extended or erasing Pattern Languages: primarily, the learnability in Gold’s learning model and, secondarily, the decidability of the equivalence. As the main result, we show that the full class of E-Pattern Languages is not inferrable from positive data if the corresponding terminal alphabet consists of exactly three or of exactly four letters – an insight that remarkably contrasts with the recent positive finding on the learnability of the subclass of terminal-free E-Pattern Languages for these alphabets. As a side-effect of our reasoning thereon, we reveal some particular example Patterns that disprove a conjecture of Ohlebusch and Ukkonen (Theoretical Computer Science 186, 1997) on the decidability of the equivalence of E-Pattern Languages.
