Grammatical Inference
4th International Colloquium, ICGI-98 Ames, Iowa, USA, July 12–14, 1998 Proceedings
Page
%P
-
Chapter and Conference Paper
Kee** Secrets in \(\mathcal {EL}^{+}\) Knowledge Bases
In this paper we study Secrecy-Preserving Query Answering problem under Open World Assumption (OWA) for \(\mathcal {EL}^+\) ...
-
Article
PSPACE Tableau Algorithms for Acyclic Modalized \(\boldsymbol{\mathcal{ALC}}\)
We study \(\mathcal{ALCK}_m\) and $\mathc...
-
Chapter and Conference Paper
Secrecy-Preserving Query Answering for Instance Checking in \(\mathcal{EL}\)
We consider the problem of answering queries against an \(\mathcal{EL}\) knowledge base (KB) using secrets, whenever it is possib...
-
Chapter
Package-Based Description Logics
We present the syntax and semantics of a family of modular ontology languages, Package-based Description Logics (P-DL), to support context- specific reuse of knowledge from multiple ontology modules. In partic...
-
Article
Scoring of web pages and tournaments—axiomatizations
Consider a set of elements which we want to rate using information about their bilateral relationships. For instance sports teams and the outcomes of their games, journals and their mutual citations, web sites...
-
Article
Ranking participants in generalized tournaments
Consider the problem of ranking social alternatives based on the number of voters that prefer one alternative to the other. Or consider the problem of ranking chess players by their past performance. A wide va...
-
Chapter and Conference Paper
Parametric Multiple Sequence Alignment and Phylogeny Construction
Bounds are given on the size of the parameter-space decomposition induced by multiple sequence alignment problems where phylogenetic information may be given or inferred. It is shown that many of the usual for...
-
Chapter and Conference Paper
Complexity of Some Problems in Universal Algebra
In this paper we consider the complexity of several problems involving finite algebraic structures. Given finite universal algebras A and B, these problems ask: (1) Do A and B satisfy precisely the same identitie...
-
Book and Conference Proceedings
-
Chapter and Conference Paper
Using sparsification for parametric minimum spanning tree problems
Two applications of sparsification to parametric computing are given. The first is a fast algorithm for enumerating all distinct minimum spanning trees in a graph whose edge weights vary linearly with a parame...
-
Chapter and Conference Paper
Linear-time algorithms for parametric minimum spanning tree problems on planar graphs
We give a linear-time algorithm for the minimum-ratio spanning tree problem on planar graphs. The algorithm is based on a new planar minimum spanning tree algorithm. The approach extends to other parametric mi...
-
Chapter and Conference Paper
Optimal parametric search on graphs of bounded tree-width
We give linear-time algorithms for a class of parametric search problems on weighted graphs of bounded tree-width. We also discuss the implications of our results to approximate parametric search on planar gra...
-
Chapter and Conference Paper
A hierarchy of deterministic top-down tree transformations
The class DTT DR (respectively, DTT) is the family of all deterministic top-down tree transductions with deterministic top-down look-ahead (respectively, no look-ahead). In this pa...
-
Chapter and Conference Paper
Parametric problems on graphs of bounded tree-width
We consider optimization problems on weighted graphs where vertex and edge weights are polynomial functions of a parameter λ. We show that, if a problem satisfies certain regularity properties and the underlying ...
-
Chapter and Conference Paper
Solving parametric problems on trees
-
Chapter and Conference Paper
The complexity of a counting finite-state automaton
A counting finite-state automaton is a nondeterministic finite-state automaton which, on an input over its input alphabet, (magically) writes in binary the number of accepting computations on the input. We exa...
-
Chapter and Conference Paper
Alternating tree automata
-
Article
Finite state relational programs
We introduce a new class of programs, called Finite Relational Linear Programs (FRLP), capable of modeling simple data processing applications. We analyze these programs with respect to tradeoffs between featu...
-
Article
Transductions of dags and trees
Directed acyclic graphs (dags) model derivations of phrasestructure grammars analogously to the way that trees model derivations of context-free grammars.
-
Chapter and Conference Paper
Descriptional complexity of concurrent processes (preliminary version)
This paper compares several algebraic software description techniques which were proposed recently. Using language theoretic tools we show that some of the most handy concurrent behavior descriptors (inverse s...
