0000000000069043
AUTHOR
Clemens Lautemann
showing 13 related works from this author
A comparison of compatible, finite, and inductive graph properties
1993
Abstract In the theory of hyperedge-replacement grammars and languages, one encounters three types of graph properties that play an important role in proving decidability and structural results. The three types are called compatible, finite, and inductive graph properties. All three of them cover graph properties that are well-behaved with respect to certain operations on hypergraphs. In this paper, we show that the three notions are essentially equivalent. Consequently, three lines of investigation in the theory of hyperedge replacement - so far separated - merge into one.
The Crane Beach Conjecture
2002
A language L over an alphabet A is said to have a neutral letter if there is a letter e/spl isin/A such that inserting or deleting e's from any word in A* does not change its membership (or non-membership) in L. The presence of a neutral letter affects the definability of a language in first-order logic. It was conjectured that it renders all numerical predicates apart from the order predicate useless, i.e., that if a language L with a neutral letter is not definable in first-order logic with linear order then it is not definable in first-order. Logic with any set /spl Nscr/ of numerical predicates. We investigate this conjecture in detail, showing that it fails already for /spl Nscr/={+, *…
Logical definability of NP-optimisation problems with monadic auxiliary predicates
1993
Given a first-order formula ϕ with predicate symbols e1...el, so,...,sr, an NP-optimisation problem on -structures can be defined as follows: for every -structure G, a sequence of relations on G is a feasible solution iff satisfies ϕ, and the value of such a solution is defined to be ¦S0¦. In a strong sense, every polynomially bounded NP-optimisation problem has such a representation, however, it is shown here that this is no longer true if the predicates s1, ...,sr are restricted to be monadic. The result is proved by an Ehrenfeucht-Fraisse game and remains true in several more general situations.
Incremental termination proofs and the length of derivations
1991
Incremental termination proofs, a concept similar to termination proofs by quasi-commuting orderings, are investigated. In particular, we show how an incremental termination proof for a term rewriting system T can be used to derive upper bounds on the length of derivations in T. A number of examples show that our results can be applied to yield (sharp) low-degree polynomial complexity bounds.
The complexity of graph languages generated by hyperedge replacement
1990
Although in many ways, hyperedge replacement graph grammars (HRGs) are, among all graph generating mechanisms, what context-free Chomsky grammars are in the realm of string rewriting, their parsing problem is known to be, in general, NP-complete. In this paper, the main difficulty in HRG parsing is analysed and some conditions on either grammar or input graphs are developed under which parsing can be done in polynomial time. For some of the cases, the parsing problem is shown to be log-space reducible to context-free string parsing.
Tree automata, tree decomposition and hyperedge replacement
2005
Recent results concerning efficient solvability of graph problems on graphs with bounded tree-width and decidability of graph properties for hyperedge-replacement graph grammars are systematised by showing how they can be derived from recognisability of corresponding tree classes by finite tree automata, using only well-known techniques from tree-automata theory.
The Descriptive Complexity Approach to LOGCFL
1999
Building upon the known generalized-quantifier-based firstorder characterization of LOGCFL, we lay the groundwork for a deeper investigation. Specifically, we examine subclasses of LOGCFL arising from varying the arity and nesting of groupoidal quantifiers. Our work extends the elaborate theory relating monoidal quantifiers to NC1 and its subclasses. In the absence of the BIT predicate, we resolve the main issues: we show in particular that no single outermost unary groupoidal quantifier with FO can capture all the context-free languages, and we obtain the surprising result that a variant of Greibach's "hardest contextfree language" is LOGCFL-complete under quantifier-free BIT-free interpre…
An Ehrenfeucht-Fraïssé Approach to Collapse Results for First-Order Queries over Embedded Databases
2001
We present a new proof technique for collapse results for first-order queries on databases which are embedded in N or R>o. Our proofs are by means of an explicitly constructed winning strategy for Duplicator in an Ehrenfeucht-FraissE game, and can deal with certain infinite databases where previous, highly involved methods fail. Our main result is that first-order logic has the natural-generic collapse over {N,≤ ,+} for arbitrary (i.e., possibly infinite) databases. Furthermore, a first application of this result shows the natural-generic collapse of first-order logic over {R>o,≤,+} for a certain kind of databases over R>o which consist of a possibly infinite number of regions.
A Logical Characterisation of Linear Time on Nondeterministic Turing Machines
1999
The paper gives a logical characterisation of the class NTIME(n) of problems that can be solved on a nondeterministic Turing machine in linear time. It is shown that a set L of strings is in this class if and only if there is a formula of the form ∃f1..∃fk∃R1..∃Rm∀xφv; that is true exactly for all strings in L. In this formula the fi are unary function symbols, the Ri are unary relation symbols and φv; is a quantifierfree formula. Furthermore, the quantification of functions is restricted to non-crossing, decreasing functions and in φv; no equations in which different functions occur are allowed. There are a number of variations of this statement, e.g., it holds also for k = 3. From these r…
A simple proof of the polylog counting ability of first-order logic
2007
The counting ability of weak formalisms (e.g., determining the number of 1's in a string of length N ) is of interest as a measure of their expressive power, and also resorts to complexity-theoretic motivations: the more we can count the closer we get to real computing power. The question was investigated in several papers in complexity theory and in weak arithmetic around 1985. In each case, the considered formalism (AC 0 -circuits, first-order logic, Δ 0 ) was shown to be able to count up to a polylogarithmic number. An essential part of the proofs is the construction of a 1-1 mapping from a small subset of {0, ..., N - 1} into a small initial segment. In each case the expressibility of …
The Descriptive Complexity Approach to LOGCFL
1998
Building upon the known generalized-quantifier-based first-order characterization of LOGCFL, we lay the groundwork for a deeper investigation. Specifically, we examine subclasses of LOGCFL arising from varying the arity and nesting of groupoidal quantifiers. Our work extends the elaborate theory relating monoidal quantifiers to NC1 and its subclasses. In the absence of the BIT predicate, we resolve the main issues: we show in particular that no single outermost unary groupoidal quantifier with FO can capture all the context-free languages, and we obtain the surprising result that a variant of Greibach's ``hardest context-free language'' is LOGCFL-complete under quantifier-free BIT-free proj…
Logics for context-free languages
1995
We define matchings, and show that they capture the essence of context-freeness. More precisely, we show that the class of context-free languages coincides with the class of those sets of strings which can be defined by sentences of the form ∃ bϕ, where ϕ is first order, b is a binary predicate symbol, and the range of the second order quantifier is restricted to the class of matchings. Several variations and extensions are discussed.
First-order expressibility of languages with neutral letters or: The Crane Beach conjecture
2005
A language L over an alphabet A is said to have a neutral letter if there is a letter [email protected]?A such that inserting or deleting e's from any word in A^* does not change its membership or non-membership in L. The presence of a neutral letter affects the definability of a language in first-order logic. It was conjectured that it renders all numerical predicates apart from the order predicate useless, i.e., that if a language L with a neutral letter is not definable in first-order logic with linear order, then it is not definable in first-order logic with any set N of numerical predicates. Named after the location of its first, flawed, proof this conjecture is called the Crane Beach …