MFCS'98:Abstracts of Accepted Papers

Gaussian elimination and a characterization of algebraic power series
by Werner Kuich

Abstract:
We show first how systems of equations can be solved by Gaussian elimination. This yields a characterization of algebraic power series and of Alg(A'), A \subseteq A', A a continuous semiring. In the case of context-free languages this characterization coincides with the characterization given by Gruska [3].

Flow Logic for Imperative Objects
by Flemming Nielson, Hanne Riis Nielson

Abstract:
We develop a control flow analysis for the Imperative Object Calculus. We prove the correctness with respect to two Structural Operational Semantics that differ in *minor* technical ways, and we show that the proofs differ in *major* ways as regards the use of proof techniques like coinduction and Kripke-logical relations.

Locally explicit construction of Rodl's asymptotically good packings
by Nikolai N. Kuzjurin

Abstract:
We present a family of asymptotically good packings of l-subsets of an n-set by k-subsets and an algorithm that given a natural i finds the i-th k-subset of this family. The bit complexity of this algorithm is almost linear in encoding length of i that is close to best possible complexity. A parallel NC-algorithm for this problem is presented as well.

Combinatorial Hardness Proofs for Polynomial Evaluation
by Mikel ALDAZ, Joos HEINTZ, Guillermo MATERA, Jose L. MONTANA, Luis M. PARDO

Abstract:
We exhibit a new method for showing lower bounds for the time complexity of polynomial evaluation procedures given by straight-line programs. Time, denoted by L, is measured in terms of nonscalar arithmetic operations. The time complexity function considered here is L^2. In contrast with known methods for proving lower complexity bounds, our method is purely combinatorial and does not require powerful tools from algebraic or diophantine geometry.
By means of our method we are able to verify the computational hardness of new natural families of univariate polynomials for which this was impossible up to now. By computational hardness we mean that the complexity function L^2 increases linearly in the degree of the polynomials of the family we are considering.
Our method can also be applied to classical questions of transcendence proofs in number theory and geometry. A list of (old and new) formal power series is given whose transcendency can be shown easily by our method.

On One-pass Term Rewriting
by Zoltan Fulop, Eija Jurvanen, Magnus Steinby, Sandor Vagvolgyi

Abstract:
Two restricted ways to apply a term rewriting system (TRS) to a tree are considered. When the one-pass root-started strategy is followed, rewriting starts from the root and continues stepwise towards the leaves without ever rewriting a part of the current tree produced in a previous rewrite step. One-pass leaf-started rewriting is defined similarly, but rewriting begins from the leaves. In the sentential form inclusion problem one asks whether all trees which can be obtained with a given TRS from the trees of some regular tree language T belong to another given regular tree language U, and in the normal form inclusion problem the same question is asked about the normal forms of T. We show that for a left-linear TRS these problems can be decided for both of our one-pass strategies. In all four cases the decision algorithm involves the construction of a suitable tree recognizer.

On some recognizable picture-languages
by Klaus Reinhardt

Abstract:
We show that the language of pictures over \{a,b\}, where all occurring b's are connected is recognizable, which solves an open problem in [Mat98]. We generalize the used construction to show that monocausal deterministically recognizable picture languages are recognizable, which is surprisingly nontrivial. Furthermore we show that the language of pictures over \{a,b\}, where the number of a's is equal to the number of b's is nonuniformly recognizable.

Blockwise Variable Orderings for Shared BDDs
by Harry Preuss, Anand Srivastav

Abstract:
A state-of-the-art data structure for the representation of Boolean functions are ordered binary decision diagrams (OBDDs). The size of an OBDD representing a Boolean function depends on the variable ordering. Finding a variable ordering with optimal (i.e. minimum) OBDD size is a central, but NP-hard problem. Thus it is of great interest to characterize optimal variable orderings from the structure of the given function. In this paper we investigate the problem of characterizing optimal variable orderings for shared OBDDs of two Boolean functions f_i = g_i \otimes_i h_i, \ i=1,2, where \otimes_i is an operator from the Base B^*_2 and g_i (resp.\ h_i) depends only on x-variables (resp. \y-variables). Tree-like circuits provide an example for such functions. In the special case f_1=\overline{f_2}, Sauerhoff, Wegener and Werchner [Sauerhoff] proved that there is some optimal ordering where all x-variables are tested before all y-variables or vice versa (blockwise variable ordering). We show that this is also true for arbitrary f_1,f_2 provided that \otimes_1 = \wedge and \otimes_2=\vee, and for shared OBDDs with complemented edges and arbitrary f_1,f_2 provided that \otimes_1 = \wedge and \otimes_2=\oplus. For all other combinations of \otimes_1 und \otimes_2 we give counterexamples.

Topological Definitions of Chaos applied to Cellular Automata Dynamics
by G. Cattane, L. Margara

Abstract:
We apply the two different definitions of chaos given by Devaney and by Knudsen for general discrete time dynamical systems (DTDS) to the case of 1-dimensional cellular automata. A DTDS is chaotic according to the Devaney's definition of chaos iff it is topologically transitive, has dense periodic orbits, and it is sensitive to initial conditions. A DTDS is chaotic according to the Knudsen's definition of chaos iff it has a dense orbit and it is sensitive to initial conditions. We continue the work initiated in~[ciac97], [stacs97], [CM97a], and~[TCS] by proving that an easy-to-check property of local rules on which cellular automata are defined--introduced by Hedlund in~[hed] and called {\em permutivity}--is a sufficient condition for chaotic behavior. Permutivity turns out to be also a necessary condition for chaos in the case of elementary cellular automata while this is not true for general 1-dimensional cellular automata. The main technical contribution of this paper is the proof that permutivity of the local rule either in the leftmost or in the rightmost variable forces the cellular automaton to have dense periodic orbits.

Shuffle on trajectories: a simplified approach to the Schutzenberger product and related operations
by Tero Harju, Alexandru Mateescu, Arto Salomaa

Abstract:
We investigate the problem of finding monoids that recognize languages of the form L_1\shu_TL_2, where T is an arbitrary set of trajectories. Thereby, we describe two such methods: one based on the so called trajectories monoids and the other based on monoids of matrices. Many well-known operations such as catenation, bi-catenation, shuffle, literal shuffle and insertion are just particular instances of the operation \shu_T. Hence, our results offer a uniform treatment for classical methods, notably the Sch\" utzenberger product. We investigate some other related operations, too.

Equations in transfinite strings
by Christian Choffrut, Sandor Horvath

Abstract:
We address the question of extending the theory of equations in finite strings to transfinite strings. We give a full description of the solutions of the equations in two unk nowns as well as the equations of the form x^my^p=z^q for m,p,q\geq 2. By so doing we introdu ce some new notions that we believe are interesting for their own sake.

A Finite Hierarchy of the Recursively Enumerable Real Numbers
by Klaus Weihrauch, Xizhong Zheng

Abstract:
In this paper we discuss the relationships between weak computabilities of a real number x and effective enumerabilities of corresponding set A which enumerates 1-position in the binary expresion of x. We call a real number x semi-computable if it is a limit a computable monotonic sequence of rational numbers, x is called weakly computable if it is a sum of two semi-computable real numbers and x is recursively enumerable if it is a limit of a computable sequence of rational numbers. We show that, there are d-r.e, k-r.e. and even \omega-r.e. sets which correspond to the semi-computable real numbers. On the other hand, there is also d-r.e set A which corresponds to a non-semi-computable but weakly computable real number. For the weakly computability of real numbers we give another characterization that x is weakly computable iff there is a computable sequence of rational numbers which converges to x weakly effectively. At last we show that there is an \omega-r.e set A which corresponds to a recursively enumerable but not weakly computable real number. Therefore, the classes of computable real numbers, semi-computable real numbers, weakly computable real numbers and r.e. real numbers form a noncollapsed hierarchy.

Minimal forbidden words and factor automata
by M. Crochemore, F. Mignosi, A. Restivo

Abstract:
Let L(M) be the (factorial) language avoiding a given anti-factorial language M. We design an automaton accepting L(M) and built from the language M. The construction is effective if M is finite.
If M is the set of minimal forbidden words of a single word v, the automaton turns out to be the factor automaton of v (the minimal automaton accepting the set of factors of v).
We also give an algorithm that builds the trie of M from the factor automaton of a single word. It yields a non-trivial upper bound on the number of minimal forbidden words of a word.
{\bf Keywords}: factorial language, anti-factorial language, factor code, factor automaton, forbidden word, avoiding a word, failure function.

Communication complexity and Lower Bounds on Multilective Computations
by Juraj Hromkovic

Abstract:
Communication complexity of two-party (multiparty) protocols has established itself as a successful method for proving lower bounds on the complexity of concrete problems for numerous computing models. While the relations between communication complexity and oblivious (semilective) computations are ususally transparent and the main difficulty is reduced to proving nontrivial lower bounds on the communication complexity of given computing problems, the situation essentially changes, if one considers non-oblivious or multilective computations. The known lower bound proofs for such computations are far from beeing transparent and the crucial ideas of these proofs are often hidden behind some nontrivial combinatorial analysis. The aim of this paper is to create a general framework for the use of two-party communication protocols for lower bound proofs on multilective computations. The result of this creation is not only a transparent presentation of some known lower bounds on multilective computation, but also the derivation of new nontrivial lower bounds on multilective VLSI circuits and branching programs. Another advantage of this framework is that it provides lower bounds for a lot of concrete functions. This contrasts to the typical papers devoted to lower bound proofs, where one establishes a lower bound for one or a few specific functions.

On the Word, Subsumption, and Complement Problem for Recurrent Term Schematizations
by Miki Hermann, Gernot Salzer

Abstract:
We investigate the word and the subsumption problem for recurrent term schematizations, which are a special type of constraints based on iteration. By means of unification, we reduce these problems to a fragment of Presburger arithmetic. Our approach is applicable to all recurrent term schematizations having a finitary unification algorithm. Furthermore, we study a particular form of the complement problem. Given a finite set of terms, we ask whether its complement can be finitely represented by schematizations, using only the equality predicate without negation. The answer is negative as there are ground terms too complex to be represented by schematizations with limited resources.

Characterization of Sensitive Linear Cellular Automata with Respect to the Counting Distance
by giovanni manzini

Abstract:
In this paper we give sufficient and necessary conditions for a linear 1-dimensional cellular automata F to be sensitive with respect to the counting distance defined in [Cattaneo et al, MFCS'97]. We prove an easy-to-check characterization in terms of the coefficients of the local rule, and an alternative characterization based on the properties of the iterated map F^n.

Average-Case Intractability vs. Worst-Case Intractability
by Johannes Koebler, Rainer Schuler

Abstract:
We use the assumption that all sets in NP (or other levels of the polynomial-time hierarchy) have efficient average-case algorithms to derive collapse consequences for MA, AM, and various subclasses of P/poly. As a further consequence we show for C=P(PP) and C=PSPACE that C is not tractable in the average-case unless C=P.

One Quantifier Will Do in Existential Monadic Second-Order Logic over Pictures
by Oliver Matz

Abstract:
We show that every formula of the existential fragment of monadic second-order logic over picture models (i.e., finite, two-dimensional, coloured grids) is equivalent to one with only one existential monadic quantifier.
The corresponding claim is true for the class of word models (see Thomas '82) but not for the class of graphs (see Otto '95).
The class of picture models is of particular interest because it has been used to show the strictness of the different (and more popular) hierarchy of quantifier alternation.

A Second Step Towards Circuit Complexity-Theoretic Analogs of Rice's Theorem
by Lane A. Hemaspaandra, Joerg Rothe

Abstract:
Rice's Theorem states that every nontrivial language property of the recursively enumerable sets is undecidable. Borchert and Stephan initiated the search for circuit complexity-theoretic analogs of Rice's Theorem. In particular, they proved that every nontrivial counting property of circuits is UP-hard, and that a number of closely related problems are SPP-hard. The present paper studies whether their UP-hardness result itself can be improved to SPP-hardness. We show that their UP-hardness result cannot be strengthened to SPP-hardness unless unlikely complexity class containments hold. Nonetheless, we prove that every P-constructibly bi-infinite counting property of circuits is SPP-hard. We also raise their general lower bound from unambiguous nondeterminism to constant-ambiguity nondeterminism.

On repetition-free binary words of minimal density
by Roman Kolpakov, Gregory Kucherov, Yuri Tarannikov

Abstract:
In [KolpakovKucherovMFCS97], a notion of minimal proportion (density) of one letter in n-th power-free binary words has been introduced and some of its properties have been proved. In this paper, we proceed with this study and substantially extend some of these results. First, we introduce and analyse a general notion of minimal letter density for any infinite set of words which don't contain a specified set of ``prohibited'' subwords. % is closed under subwords. We then prove that for n-th power-free binary words, the density function is \frac{1}{n}+\frac{1}{n^3}+\frac{1}{n^4}+{\cal O}(\frac{1}{n^5}) refining the estimate from [KolpakovKucherovMFCS97]. Following [KolpakovKucherovMFCS97], we also consider a natural generalization of n-th power-free words to x-th power-free words for real argument x. We prove that the minimal proportion of one letter in x-th power-free binary words, considered as a function of x, is discontinuous at all integer points n\geq 3. Finally, we give an estimate of the size of the jumps.

Encoding the Hydra Battle as a rewrite system
by H. Touzet

Abstract:
In rewriting theory, termination of a rewrite system by Kruskal's theorem implies a theoretical upper bound on the complexity of the system. This bound is, however, far from having been reached by known examples of rewrite systems. All known orderings used to establish termination by Kruskal's theorem yield a multiply recursive bound. Furthermore, the study of the order types of such orderings suggests that the class of multiple recursive functions constitutes the least upper bound. Contradicting this intuition, we construct here a rewrite system which reduce by Kruskal's theorem and whose complexity is not multiply recursive. This system is even totally terminating. This leads to a new lower bound for the complexity of totally terminating rewrite systems and to rewrite systems that reduces by Kruskal's theorem. Our construction relies on the Hydra battle using classical tools from ordinal theory and subrecursive functions.It can be extended to exhaust the provably total functions of Peano arithmetic.

Lazy Functional Algorithms for Exact Real Functionals
by Alex K. Simpson

Abstract:
We show how functional languages can be used to write programs for real-valued functionals in exact real arithmetic. We concentrate on two useful functionals: definite integration, and the functional returning the maximum value of a continuous function over a closed interval. The algorithms are a practical application of a method, due to Berger, for computing quantifiers over streams. Correctness proofs for the algorithms make essential use of domain theory.

Locality of order-invariant first-order formulas
by Martin Grohe, Thomas Schwentick

Abstract:
A query is local if the decision of whether a tuple in a structure satisfies this query only depends on a small neighborhood of the tuple. We prove that all queries expressible by order-invariant first-order formulas are local.

Spatial and Temporal Refinement of Typed Graph Transformation Systems
by M. Grosse--Rhode, F. Parisi--Presicce, M. Simeoni

Abstract:
Graph transformation systems support---among others---the formal modeling and specification of dynamic, concurrent, and distributed systems. States are given by their graphical structure, and transitions are modeled by graph transformation rules. In this paper we investigate two kinds of refinement relations for graph transformation systems. In a spatial refinement each rule is refined by an amalgamation of rules, in a temporal refinement it is refined by a sequence of rules. Types for graph transformation systems are used as a structuring means that allows uniform restrictions and extensions of rules and derivations. With these constructions hiding can be introduced in the refinement relations, which supports the modeling of implementation. The background of these investigations is the development of a module concept for typed graph transformation systems, with export and import interfaces, and a body implementing the services offered at the export interface.

Predicative Polymorphic Subtyping
by Marcin Benke

Abstract:
We consider a version of the Mitchell's subsumption. Here, it is not suited for the system F but for the predicative version of it introduced by Leivant. The aim of the approach is to propose a new notion of polymorphic functional subsumption which may be decidable unlike the Mitchell's one. We define a system for predicative subsumption in the style of Mitchell and then prove its equivalence with a Gentzen-style definition. Next, we study the notion of bicoercibility. This is followed by a reduction of the typability in the Leivant's system with subsumption to subsumption itself.

On defect effect of bi-infinite words
by Juhani Karhumaeki, Jan Manuch, Wojciech Plandowski

Abstract:
We prove the following two variants of the defect theorem. Let X be a finite set of words over a finite alphabet. Then if a nonperiodic bi-infinite word w has two X-factorizations, then the combinatorial rank of X is at most \card(X)-1, i.e.\ there exists a set F such that X\subseteq F^+ with \card(F)<\card(X). Moreover, in the case \card(F)=\card(X), the number of periodic bi-infinite words which has two different X-factorizations is finite. Further, if \card(X)=2 and a bi-infinite word possesses two X-factorizations which are not shift-equivalent, then the primitive roots of the words in X are conjugates.

Tally NP Sets and Easy Census Functions
by Judy Goldsmith, Mitsunori Ogihara, Joerg Rothe

Abstract:
We study the question of whether every P set has an easy (i.e., polynomial-time computable) census function. We characterize this question in terms of unlikely collapses of language and function classes such as the containment of #P_1 in FP, where #P_1 is the class of functions that count the witnesses for tally NP sets. We prove that every #P_{1}^{PH} function can be computed in FP^{#P_{1}^{#P_{1}}}. Consequently, every P set has an easy census function if and only if every set in the polynomial hierarchy does. We show that the assumption #P_1 being contained in FP implies P = BPP and that PH is contained in MOD_{k}P for each k \geq 2, which provides further evidence that not all sets in P have an easy census function. We also relate a set's property of having an easy census function to other well-studied properties of sets, such as rankability and scalability (the closure of the rankable sets under P-isomorphisms). Finally, we prove that it is no more likely that the census function of any set in P can be approximated (more precisely, can be n^{\alpha}-enumerated in time n^{\beta} for fixed \alpha and \beta) than that it can be precisely computed in polynomial time.

Minimum Propositional Proof Length is NP-Hard to Linearly Approximate
by Michael Alekhnovich, Sam Buss, Shlomo Moran, Toniann Pitassi

Abstract:
We prove that the problem of determining the minimum propositional proof length is NP-hard to approximate within any constant factor. These results hold for all Frege systems, for all extended Frege systems, for resolution and Horn resolution, and for the sequent calculus and the cut-free sequent calculus. Also, if NP is not in QP (quasi-polynomial time), then it is impossible to approximate minimum propositional proof length within a factor of 2^{\log^{(1-e)} n} for any constant e>0. All these hardness of approximation results apply to proof length measured either by number of symbols or by number of inferences, for tree-like or dag-like proofs. We introduce the Monotone Minimum (Circuit) Satisfying Assignment problems and prove the same hardness results for these problems.

A Superpolynomial Lower Bound for a Circuit Computing the Clique Function with at most (1/6)loglog n Negation Gates
by Kazuyuki Amano, Akira Maruoka

Abstract:
In this paper, we investigate about a lower bound on the number of gates in a Boolean circuit that computes the clique function with a limited number of negation gates. To derive strong lower bounds on the size of such a circuit we develop a new approach by combining the three approaches: the restriction applied for constant depth circuits, the approximation method applied for monotone circuits and boundary covering developed in the present paper. Based on the approach the following statement is established: If a circuit C with at most (1/6)loglog m negation gates detects cliques of size (log m)^(3 sqrt(log m)) in a graph with m vertices, then C contains at least 2^((1/5)(log m)^(sqrt(log m))) gates. No non-trivial lower bounds on the size of such circuits were previously known even if we restrict the number of negation gates to be a constant. Moreover, by the Fischer's result if one can improve the number of negation gates (1/6)loglog m up to 2log m in the statement, then we have that P not equal to NP. In addition, we present a general relationship between negation-limited circuit size and monotone circuit size of an arbitrary monotone function.

Degree-preserving forests
by Hajo Broersma, Andreas Huck, Ton Kloks,Otto Koppius, Dieter Kratsch, Haiko Mueller, Hilde Tuinstra

Abstract:
We consider the degree-preserving spanning tree (DPST) problem: given a connected graph G, find a spanning tree T of G such that as many vertices of T as possible have the same degree in T as in G. This problem is a graph-theoretical translation of a problem arising in the system-theoretical context of identifiability in networks, a concept which has applications in e.g., water distribution networks and electrical networks. We show that the DPST problem is NP-hard, even when restricted to split graphs or bipartite planar graphs, but that it can be solved in polynomial time for AT-free graphs and for graphs with bounded treewidth. Moreover, we present linear time approximation algorithms for planar graphs of worst case performance ratio (k-1)/k for every integer k>1.

The semi-full closure of Pure Type Systems
by Gilles Barthe

Abstract:
R. Pollack introduced the class of semi-full Pure Type Systems and gave an efficient type-checking algorithm for Pure Type Systems in that class. We show that every so-called functional Pure Type System may be extended to a semi-full Pure Type System. Moreover, the extension is conservative and preserves weak normalisation. Based on these results, we give a new efficient and conceptually simple type-checking algorithm for functional Pure Type Systems. As a further application of our method, we show that the Barendregt-Geuvers-Klop conjecture implies the K-conjecture for all functional specifications.

Proof Theory of Fuzzy Logics: Urquhart's C and Related Logics
by Matthias Baaz, Agata Ciabattoni, Christian Fermueller, Helmut Veith

Abstract:
We investigate the proof theory of Urquhart's C and other logics underlying the most prominent fuzzy logics, such as Goedel, Lukasiewicz and Product logic (cf. Hajek's forthcoming book.) All these logics share the property that their truth values are linearly ordered. We define hypersequent calculi for such logics, and show the following results: (1) The contraction-free counterparts of intuitionistic logic and Goedel logic (including C) admit cut-elimination. (2) Validity in these logics is decidable, and in fact in PSPACE. (3) Hajek's basic fuzzy logic BL properly extends the contraction-free Goedel logics. (4) The axiom for commutativity of the minimum is independent from the other axioms of BL. (5) All abovementioned logics are distinct from each other.

Facial circuits of planar graphs and context-free languages.
by Bruno Courcelle, Denis Lapoire

Abstract:
It is known that a language is context-free iff it is the set of borders of the trees of recognizable set, where the border of a (labelled) tree is the word consisting of its leaf labels read from left to right. We give a generalization of this result in terms of planar graphs of bounded tree-width. Here the border of a planar graph is the word of edge labels of a path which borders a face for some planar embedding. We prove that a language is context-free iff it is the set of borders of the graphs of a set of (labelled) planar graphs of bounded tree-width which is definable by a formula of monadic second-order logic.

The equivalence problem for deterministic pushdown transducers into abelian groups
by Geraud SENIZERGUES

Abstract:
the equivalence problem for deterministic pushdown transducers with inputs in a free monoid X^* and outputs in an abelian group H is shown to be decidable. The result is obtained by constructing a complete formal system for equivalent pairs of deterministic rational series on the variable alphabet associated with the dpdt M with coefficients in the monoid H^0 (the monoid obtained by adjoining a zero to the group H).

Nonstochastic languages being projections of 2-tape quasideterministic languages
by Richard Bonner, Rusins Freivalds, Janis Lapins, Antra Lukjanska

Abstract:
A language L_k of k-tuples of words which is recognized by a k-tape rational probabilistic finite automaton with probability 1 - \varepsilon, for arbitrary \varepsilon > 0, is called quasideterministic. It is proved by R. Freivalds in 1982 that each rational stochastic language is a projection of a quasideterministic language L_k of k-tuples of words. Had projections of quasideterministic languages on one tape always been rational stochastic languages, we would have a good characterization of the class of the rational stochastic languages. However we prove the opposite in this paper. A two-tape qusideterministic language exists, the projection of which on the first tape is a nonstochastic language.

forallexists^ast-Equational Theory of Context Unification is Pi_1^0-Hard
by Sergei Vorobyov

Abstract:
Context unification is a particular case of second-order unification, where all second-order variables are *unary* and only *linear* functions are sought for as solutions. Its decidability is an *open* problem. We present the simplest (currently known) undecidable quantified fragment of the theory of context unification by showing that for every signature containing a more-than-unary symbol one can construct a context equation E[p,r,F,w] with parameter p, first-order variables r, w, and context variables F such that the set of true sentences of the form forall r exists F exists w E[p,r,F,w] is \Pi_1^0-hard (i.e., every co-r.e. set is many-one reducible to it), as p ranges over finite words of a binary alphabet.
Moreover, the existential prefix above contains just 5 context and 3 first-order variables (this can be further improved). It follows, in particular, that the forall exists^8-equational theory of context unification is undecidable.

Tree decompositions of small diameter
by Hans L. Bodlaender, Torben Hagerup

Abstract:
Motivated by applications in parallel and dynamic graph algorithms, we investigate the tradeoff between width and diameter of tree decompositions. For all integers n, k and K with 1 <= k <= K <= n-1, denote by D(n,k,K) the maximum, over all n-vertex graphs G of treewidth k, of the smallest diameter of a tree decomposition of G of width K. We determine D(n,k,K), up to a constant factor, for all values of n, k and K. When K is bounded by a constant (the case of greatest practical relevance), D(n,k,K) is Theta(n) for K <= 2 k-1, Theta(sqrt(n)) for 2 k <= K <= 3 k-2, and Theta(log n) for K >= 3 k-1. We provide much more accurate bounds for the case K <= 2 k-1.

Speeding-up Nondeterministic Single-Tape Off-Line Computations by One Alterantion
by Jiri Wiedermann

Abstract:
It is shown that for a well-behaved function T(n) any nondeterministic single-tape off-line Turing amchine of time complexity T(n) can be speeded-up by one extra alternation by the factor log log n/\sqrt{T(n)}. This leads to the seaparation of the respective time bounded classes within the respective \Sigma hierarchy. Analogous result holds also for the complementary classes in the \Pi hierarchy. This is the first occasion where such separation results have been proved for a restricted type of multitape nondeterministic machines. For the general case of multitape nondeterministic machines similar results are not known to hold.

Iterated Length-Preserving Transductions
by Michel Latteux, David Simplot, Alain Terlutte

Abstract:
The purpose of this paper is the study of the smallest family of transductions containing length-preserving rational transductions and closed under union, composition and iteration. We give several characterizations of this class using restricted classes of length-preserving transductions, by showing the connections with ``context-sensitive transductions'' and transductions associated with recognizable picture languages. We also study the class obtained by only using length-preserving rational functions and we show the relations with ``deterministic context-sensitive transductions''.

Comparison between the complexity of a function and the complexity of its graph
by Bruno Durand, Sylvain Porrot

Abstract:
This paper investigates in terms of Kolmogorov complexity the differences between the complexity of a recursive function and the complexity of its graph. Our first result is that the complexity of the initial parts of the graph of a recursive function, although bounded, has almost never a limit. The second result is that the complexity of these initial parts approximate the complexity of the function itself in most cases (and in the average) but not always.

Representing Hyper-Graphs by Regular Languages
by Salvatore La Torre, Margherita Napoli

Abstract:
A new compact representation of infinite graphs is investigated. Regular languages are used to represent labelled hyper-graphs which can be also multi-graphs. Our approach is similar to that used by A. Ehrenfeucht, J. Engelfriet and G. Rozenberg for finite graphs since we use a regular prefix-free language as set of vertices, but it differs from th at in the representation of the edges. In fact, we use a regular language for the edges instead of a finite loop-free graph. Our approach preserves the finite representation of the edges and of the corresponding labelling mapping and yields to a higher expressive power. As a matter of fact, our graph representation results to be more powerful than the equational graphs introduced by B. Courcelle. Moreover, the use of a regular prefix-free language to represent the vertices allows (fixed the language of the edges) to express a graph by a labelled tree. The advantage to represent graphs by trees is that properties of graphs can be verified by induction on the tree, often leading to efficient algorithms.

Computing epsilon-Free NFA from Regular Expressions in O(n log^2(n)) Time
by Christian Hagenah, Anca Muscholl

Abstract:
The standard procedure to transform a regular expression to an \epsilon-free NFA yields a quadratic blow-up of the number of transitions. For a long time this was viewed as an unavoidable fact, until Hromkovi\u{c} et.al.~[hsw97] exhibited recently a construction yielding \epsilon-free NFA with O(n \log^2(n)) transitions. However, the complexity of the construction was left open. In this paper we present optimal sequential and parallel algorithms for the construction described in [hsw97].

Reducing AC-Termination to Termination
by Maria Ferreira, Delia Kesner, Laurence Puel

Abstract:
We present a new technique for proving AC-termination. We show that if certain conditions are met, AC-termination can be reduced to termination, i. e., termination of a TRS S modulo an AC-theory can be inferred from termination of another TRS R with no AC-theory involved. This is a new perspective and opens new possibilities to deal with AC-termination.

About Synchronization Languages
by Isabelle Ryl, Yves Roos, Mireille Clerbout

Abstract:
Synchronization languages are a model used to describe the behaviors of distributed applications whose synchronization constraints are expressed by synchronization expressions. Synchronization languages were conjectured by Guo, Salomaa and Yu to be characterized by a rewriting system. We have shown that this conjecture is not true. This negative result has led us to extend the rewriting system and Salomaa and Yu to extend the definition of synchronization languages. The aim of this paper is to establish the link between these two extensions, we show that the behaviors expressed by the two families of synchronization languages are only separated by morphisms.

A (non-elementary) modular decision procedure for LTrL
by Paul Gastin, Raphael Meyer, Antoine Petit

Abstract:
Thiagarajan and Walukiewicz have defined a temporal logic LTrL on Mazurkiewicz traces, patterned on the famous propositional temporal logic of linear time LTL defined by Pnueli. They have shown that this logic is equal in expressive power to the first order theory of finite and infinite traces. The hopes to get an ``easy'' decision procedure for LTrL, as it is the case for LTL, vanished very recently due to a result of Walukiewicz who showed that the decision procedure for LTrL is non-elementary. However, tools like Mona or Mosel show that it is possible to handle non-elementary logics on significant examples. Therefore, it appears worthwhile to have a direct decision procedure for LTrL; in this paper we propose such a decision procedure, in a modular way. Since the logic LTrL is not pure future, our algorithm constructs by induction a finite family of Buchi automata for each LTrL-formula. As expected by a recent results of Walukiewicz, the main difficulty comes from the ``Until'' operator.

When Can an Equational Simple Graph Be Generated by Hyperedge Replacement?
by Klaus Barthelmann

Abstract:
Infinite hypergraphs with sources arise as the canonical solutions of certain systems of recursive equations written with operations on graphs. There are basically two different sets of such operations known from the literature, HR and VR. VR is strictly more powerful than HR on simple graphs. Necessary conditions are known ensuring that a VR-equational simple graph is also HR-equational. We prove that two of them, namely having finite tree-width or not containing the infinite bipartite graph, are also sufficient. This shows that equational graphs behave like context-free sets of finite graphs.
Using an alternate characterization of VR-equational simple graphs [Barthelmann1997], this result provides a (necessary and) sufficient condition and an effective procedure to translate a language-theoretic definition of an infinite graph [Caucal1996] into an operational one based on substitution [Courcelle1989].

Positive Turing and Truth-Table Completeness for NEXP Are Incomparable
by Levke Bentzien

Abstract:
Using ideas introduced by Buhrman et al. ([BHT91], [BST93]) to separate various completeness notions for NEXP=NTIME(2^{poly}), positive Turing complete sets for NEXP are studied. In contrast to many-one completeness and bounded truth-table completeness with norm 1 which are known to coincide on NEXP ([BST93]), whence any such set for NEXP is positive Turing complete, we give sets A and B such that \begin{itemize} \item[(1)] A is bT(2)-complete but not posT-complete for NEXP \item[(2)] B is posT-complete but not tt-complete for NEXP. \end{itemize} These results come close to optimality since a further strengthening of (1), as was done by Buhrman in [Bu93] for EXP=DTIME(2^{poly}), seems to require the assumption NEXP=co-NEXP.

Improved Time and Space Hierarchies of One-Tape Off-Line TMs
by Kazuo Iwama, Chuzo Iwamoto

Abstract:
This paper presents improved time and space hierarchies of one-tape off-line Turing Machines (TMs), which have a single worktape and a two-way input tape: (i) For any time-constructible functions t_1(n) and t_2(n) such that \inf_{n\rightarrow\infty}\frac{t_1(n)\log\log t_1(n)}{t_2(n)}=0 and t_1(n)=n^{O(1)}, there is a language which can be accepted by a t_2(n)-time TM, but not by any t_1(n)-time TM. (ii) For any space-constructible function s(n) and positive constant \epsilon, there is a language which can be accepted in space s(n)+\log s(n)+(2+\epsilon)\log\log s(n) by a TM with two worktape-symbols, but not in space s(n) by any TM with the same worktape-symbols. The (\log\log t_1(n))-gap in~(i) substantially improves the Hartmanis and Stearns' (\log t_1(n))-gap which survived more than 30 years.

Deadlocking States in Context-free Process Algebra
by Jiri Srba

Abstract:
Recently it has been shown that the class of BPA (or context-free) processes can be widely used to describe sequential processes and to define their semantics. This class has been intensively studied. Bisimilarity and regularity appeared to be decidable within the BPA processes (see \cite{CHHS:BPA-bisimilarity-IC,BCS:elementaryBPA, BCS:BPA-regularity}). We extend these processes with a deadlocking state into \BPAd systems. Bosscher has proved that bisimilarity and regularity remain decidable [bosscher:PhD]. In this paper we continue with the study initiated by Bosscher. We generalise his approach introducing strict and nonstrict version of bisimilarity. We show that the \BPAd class is more expressive w.r.t. (both strict and nonstrict) bisimilarity but it remains language equivalent to BPA. Finally we give a characterisation of those \BPAd processes which can be equivalently (up to bisimilarity) described within the `pure' BPA syntax.

Expressive Completeness of Temporal Logic of Action
by Alexander Rabinovich

Abstract:
The paper compares the expressive power of monadic second order logic of order, a fundamental formalism in mathematical logic and theory of computation, with that of a fragment of Temporal Logic of Actions introduced by Lamport for specifying th e behavior of concurrent systems.

On the Complexity of Wavelength Converters
by Vincenzo Auletta, Ioannis Caragiannis, Christos Kaklamanis, Pino Persiano

Abstract:
In this paper the capabilities of an all--optical network model that supports wavelength conversion are investigated. The model applies to tree--shaped optical networks and was established in [sirocco]. A few wavelength converters are maintained at each non--leaf network node. We present a greedy wavelength routing algorithm that allocates a total bandwidth of w(l) wavelengths to any set of requests of load l (where load is defined as the maximum number of requests that go through any directed fiber link) and we give sufficient conditions for correct operation of the algorithm when applied to binary tree networks. We exploit properties of (explicitly constructed) Ramanujan graphs to show that (for the case of binary tree networks) our algorithm increases the bandwidth utilized compared to the algorithm presented in [gargano]. Furthermore, we use another class of graphs called dispersers, for which almost optimal explicit constructions are known, to implement wavelength converters of asymptotically optimal complexity with respect to their size (the number of all possible conversions). We prove that their use leads to optimal and nearly--optimal bandwidth allocation even in a greedy manner.

Randomness vs. Completeness: On the Diagonalization Strength of Resource-Bounded Random Sets
by Klaus Ambos-Spies, Steffen Lempp, Gunther Mainhardt

Abstract:
We show that the question whether the p-tt-complete or p-T-complete sets for the deterministic time classes {\bf E} and {\bf EXP} have measure 0 in these classes in the sense of Lutz's resource-bounded measure connot be decided by relativizable techniques. On the other hand we obtain the following absolute results if we bound the norm, i.e. the number of oracle queries of the reductions: For r=tt,T, \[\mu_p(\{C:\: C\: \mbox{p-r(kn)-complete for {\bf E}}\})=0\] and \[\mu_{p_2}(\{C:\: C\: \mbox{p-r(n^k)-complete for {\bf EXP} }\})=0.\] In the second part of the paper we investigate the diagonalization strength of random sets in an abstract way by relating randomness to a new genericity concept. This provides an alternative quite elegant and powerful approach for obtainig results on resource-bounded measures like the ones in the first part of the paper.

A Parallelization of Dijkstra's Shortest Path Algorithm
by A. Crauser, K. Mehlhorn, U. Meyer, P. Sanders

Abstract:
Despite much effort the single source shortest path (SSSP) problem has resisted parallel solutions which are fast and simultaneously work-efficient. We propose simple criteria which divide Dijkstra's sequential SSSP algorithm into a number of phases, such that the operations within a phase can be savely done in parallel. We give a PRAM algorithm based on these criteria and analyze its performance on random digraphs with random edge weights uniformly distributed in [0,1]. We use the G(n,d/n) model: the graph consists of n nodes and each edge is chosen with probability d/n. Our PRAM algorithm needs O(n^(1/3) log n) time and O(n log n + dn) work with high probability (whp). We also give extensions to external memory computation: we derive an algorithm which needs O(n/D + dn/(DB) log_(S/B) dn/(DB)) I/Os whp and can use up to D=O(min{ n^(2/3)/log n , S/B }) independent disks. The blocksize is given by B, S denotes the size of internal memory. Simulations show the applicability of our approach even on non-random graphs.

D0L-Systems and Surface Automorphisms
by Luis-Miguel Lopez, Philippe Narbel

Abstract:
We introduce a new relationship between language theory and surface theory. More specifically, we show how substitutions on words can represent automorphisms of surfaces. This fact is then applied to construct and analyze non-periodic irreducible automorphisms. This is obtained by using results about D0L-systems, mainly the decidability of the non-repetitiveness of a D0L-language. We also show how properties about substitutions like primitivity and non-cyclicity can be checked through topological means.

Probabilistic Concurrent Constraint Programming: Towards a Fully Abstract Model
by Alessandra Di Pierro, Herbert Wiklicky

Abstract:
This paper presents a Banach space based approach towards a denotational semantics of a probabilistic constraint programming language. The existence of fixed-points is guaranteed by the Brouwer-Schauder Fixed-Point Theorem. A concrete fixed-point construction is also presented which corresponds to a notion of observables capturing the exact results of both finite and infinite results.

Embedding of Hypercubes into Grids
by Sergej Bezrukov,Joe Chavez,Larry Harper,Markus Roettger,Ulf-Peter Schroeder

Abstract:
We consider one-to-one embeddings of the n-dimensional hypercube into grids with 2^n vertices and present lower and upper bounds and asymptotic estimates for minimal dilation, edge-congestion, and their mean values. We also introduce and study two new cost-measures for these embeddings, namely the sum over i=1,...,n of dilations and the sum of edge-congestions caused by the hypercube edges of the ith dimension. It is shown that, in the simulation via the embedding approach, such measures are much more suitable for evaluating the slowdown of uniaxial hypercube algorithms then the traditional cost measures.

Approximating Maximum Independent Sets in Uniform Hypergraphs
by Thomas Hofmeister,Hanno Lefmann

Abstract:
We consider the problem of approximating the independence number and the chromatic number of k-uniform hypergraphs on n vertices. For fixed integers k \geq 2, we obtain for both problems that one can achieve in polynomial time approximation ratios of at most O(n/(\log^{(k-1)} n)^2). This extends results of Boppana and Halld\'orsson [BH92] who showed for the graph case that an approximation ratio of O(n/(\log n)^2) can be achieved in polynomial time. On the other hand, assuming NP \neq ZPP, one cannot obtain in polynomial time for the independence number and the chromatic number of k-uniform hypergraphs an approximation ratio of n^{1-\epsilon} for fixed \epsilon > 0.

Iterated Function Systems and Control Languages
by Henning Fernau, Ludwig Staiger

Abstract:
The paper shows an application of formal language theory to fractals. Here we consider fractals generated by iterated function systems (IFS). It is known that introducing a structure (device) controlling the sequence of applications of the functions in the IFS allows for a wider range of representable fractals.
One of the major tasks in the analysis of fractals is the estimation of their dimension (Hausdorff dimension). In the present paper we investigate IFS with languages as control structures, that is, the set of allowed ``addresses'' (w.r.t. the IFS) of points in the fractal is restricted according to the underlying language.
We show that under some well-known assumption from fractal geometry (the so called Open Set Condition) on the IFS the fractal dimension can be easily estimated from a generalization of the entropy of languages.
We proceed in three steps:
First we investigate the so-called \beta-entropy, which is a generalization of the usual entropy of languages introduced by Chomsky and Miller. The definition of the \beta-entropy takes into account the different weights of the letters of alphabet, which is assigned according to the differing contracting factors of the mappings of the IFS.
Next we apply this result to estimate the fractal dimension (Hausdorff dimension) in the space of addresses.
In the subsequent section we investigate in more detail the relationships between the control language and the mappings of the IFS. Here our main result asserting that the real Hausdorff dimension of the fractal equals the Hausdorff dimension in the address space provided the IFS fulfills the Open Set Condition is proved.
KEYWORDS: entropy of languages, iterated function systems, fractals, dimension,

Additive Cellular Automata over {Z}_p and the Bottom of (CA,leq)
by I. Rapaport, J. Mazoyer

Abstract:
In a previous work we began to study the question of how to compare cellular automata (CA). In this context it was introduced a preorder (CA,\leq) admitting a global minimum and it was shown that on the bottom of (CA,\leq) are located all the CA satisfying very simple dynamical properties as nilpotency or periodicity. In this paper we prove that also the (algebraically amenable) additive CA over \Z_p are located on the bottom of (CA,\leq). This result encourages our conjecture that says that ``being on the bottom of (CA,\leq)'' means ``being simple'' or, in a more general way, that the ``distance'' from the minimum could represent a measure of ``complexity'' on CA. We also prove that the additive CA over \Z_p with p primes are two by two incomparable. This fact improves considerably our understanding of (CA,\leq) because it means that the minimum, even in the canonical order compatible with \leq, has infinite outdegree.

On the Composition Problem for OBDDs With Different Variable Orderings
by Anna Slobodova

Abstract:
Ordered Binary Decision Diagram is the favorite data structure used for representation Boolean functions in computer-aided synthesis and verification of digital systems. The secret of their success is the efficiency of the algorithms for Boolean operations, satisfiability and equivalence check. However, the algorithms work well under condition only that the variable ordering of considered OBDDs is the same.
In this paper, we discuss the problem of Boolean operations on OBDDs with different variable orderings, which naturally appears, e.g., in the connection with OBDD minimization techniques that are based on variable reordering. Our goal is to place the problem with respect to its complexity and to point out the difficulties in finding an acceptable solution.

A Computational Interpretation of the lambdamu-calculus
by G.M. Bierman

Abstract:
This paper proposes a simple computational interpretation of Parigot's \lambda\mu-calculus. The \lambda\mu-calculus is an extension of the typed \lambda-calculus which corresponds via the Curry-Howard correspondence to classical logic. Whereas other work has given computational interpretations by translating the \lmc\ into other calculi, I wish to propose here that the \lmc\ itself suggests a novel computational interpretation. This interpretation is best given as a single-step semantics which, in particular, leads to a relatively simple, but powerful, operational theory.

Complete Abstract Interpretations made Constructive
by Roberto Giacobazzi, Francesco Ranzato, Francesca Scozzari

Abstract:
Completeness is a desirable, although uncommon, property in abstract interpretation, formalizing the intuition that, relatively to the underlying abstract domains, the abstract semantics is as precise as possible. We consider here the most general form of completeness, where concrete semantic functions can have different domains and ranges, a case particularly relevant in functional programming. In this setting, our main contributions are as follows. (i) Under the weak and reasonable hypothesis of continuous semantic functions, a constructive characterization of the least complete extension and the greatest complete restriction of an abstract interpretation is given. The existence of more restricted forms of similar abstractions was recently proved by the first two authors. (ii) In projection-based program analysis, our results show that the so-called least backward abstractions of co-continuous semantic functions always exist and can be constructively characterized. This improves considerably over previous works in the field. (iii) Our results generalize the notion of quotient of abstract domains, a tool introduced by Cortesi et al. for comparing the expressive power of abstract interpretations. Fairly severe hypotheses are required for Cortesi et al.'s quotients to exist. We prove instead that continuity of the semantic functions guarantees the existence of our generalized quotients.

On Boolean vs. Modular Arithmetic for Circuits and Communication Protocols
by Carsten Damm

Abstract:
We compare two computational models that appeared in the literature in a Boolean setting and in an analog setting based on modular arithmetic. We prove that in both cases the arithmetic version can to some extend simulate the Boolean version. Although the models are very different, the proofs rely on the same idea based on the Schwartz-Zippel-Theorem.
In the first part we give a new simulation of semi-unbounded Boolean circuits by semiunbounded circuits with unbounded parity gates. Our simulation is simpler and more efficient with respect to depth than the original simulation of G\'al and Wigderson [GalWigderson]. In the second part we prove, that two-party parity communication protocols can approximate nondeterministic communication protocols. A strict simulation of one by the other is impossible as was shown in [DKMW97+].

Model Checking Real-Time Properties of Symmetric Systems
by E. Allen Emerson, Richard J. Trefler

Abstract:
We develop efficient algorithms for model checking quantitative properties of symmetric reactive systems in the general framework of a Real-Time Mu-calculus. Previous work has been limited to qualitative correctness properties. Our work not only permits handling of quantitative correctness, but it provides a strictly more expressive framework for qualitative correctness since the Mu-calculus strictly subsumes, e.g, CTL*. Unlike the previous ``group-theoretic'' approaches of [CEFJ96] and [ES96] and the technical ``automata-theoretic'' approach of [ES97], our new approach may be viewed as ``model-theoretic''.

On counting AC^0 circuits with negative constants
by Andris Ambainis, David Mix Barrington, Huong LeThanh

Abstract:
Continuing the study of the relationship between TC^0, AC^0 and arithmetic circuits, started by Agrawal et al., we answer a few questions left open in this paper. Our main result is that the classes DiffAC^0 and GapAC^0 coincide, under poly-time, log-space, or log-time uniformity. From that we can derive that under logspace uniformity, the following equalities hold: \[C_=AC^0=PAC^0=TC^0.\]

Reconstructing Polyatomic Structures from Discrete X-Rays: NP-Completeness Proof for Three Atoms
by Marek Chrobak, Christoph Durr

Abstract:
We address a discrete tomography problem arising in the study of the atomic structure of crystal lattices. A polyatomic structure T is an integer lattice in dimension D>=2, whose points may be occupied by c types of atoms. To ``analyze'' T, we conduct l measurements that we refer to as _discrete X-rays_. A discrete X-ray in direction xi determines the number of atoms of each type on each line parallel to xi. Given such l non-parallel X-rays, we wish to reconstruct T.
The complexity of the problem for c=1 (one atom) has been completely determined by Gardner, Gritzmann and Prangerberg, who proved that the problem is NP-complete for any dimension D>=2 and l>=3 non-parallel X-rays, and that it can be solved in polynomial time otherwise.
The NP-completeness result above clearly extends to any c>=2, and therefore when studying the polyatomic case we can assume that l = 2. As shown in another article by the same authors, this problem is also NP-complete for c>=6 atoms, even for dimension D=2 and for the axis-parallel X-rays. The authors of that article conjecture that the problem remains NP-complete for c =3,4,5.
We resolve this conjecture by proving that the problem is indeed NP-complete for c>=3 in 2D, even for the axis-parallel X-rays. Our construction relies heavily on some structure results for the realizations of 0-1 matrices with given row and column sums.

Polymorhic subtyping without distributivity
by Jacek Chrzaszcz

Abstract:
The subtyping relation in the polymorphic second-order lambda-calculus was introduced by John C. Mitchell in 1988. It is known that this relation is undecidable, but all known proofs of this fact strongly depend on the distributivity axiom. Nevertheless it has been conjectured that this axiom does not influence the undecidability.
The present paper shows undecidability of subtyping when we remove distributivity from its definition. Furthermore, the full equational axiomatisation of the corresponding equivalence relation is given. Both results follow from an analysis of rewriting-style subtyping derivations.

One guess one-way cellular arrays
by Thomas Buchholz, Andreas Klein, Martin Kutrib

Abstract:
One-way cellular automata with restricted nondeterminism are investigated. The number of allowed nondeterministic state transitions is limited to a constant. It is shown that a limit to exactly one step does not decrease the language accepting capabilities. We prove a speed-up result that allows any linear-time computation to be sped-up to real-time. Some relationships to deterministic arrays are considered. Finally we prove several closure properties of the real-time languages.

Timed Bisimulation and Open Maps
by Thomas Hune, Mogens Nielsen

Abstract:
Open maps have been used for defining bisimulations for a number of models, but none of these have modelled real-time. We define a category of timed transition systems, and use the general framework of open maps to obtain a notion of bisimulation. We show this to be equivalent to the standard notion of timed bisimulation. Thus the abstract results from the theory of open maps apply, e.g. the existence of canonical models and characteristic logics. Here, we provide an alternative proof of decidability of bisimulation for finite timed transition systems in terms of open maps, and illustrate the use of the open maps in presenting bisimulations.

Optimizing OBDDs Is Still Intractable for Monotone Functions
by Kazuo Iwama, Mitsushi Nozoe

Abstract:
Optimizing the size of Ordered Binary Decision Diagrams is shown to be NP-complete for monotone Boolean functions. The same result for general Boolean functions was obtained by Bollig and Wegener recently.

Tarskian set constraints are in NEXPTIME
by Pawel Mielniczuk, Leszek Pacholski

Abstract:
In this paper we show that satisfiability of Tarskian set of constraints can be decided in exponential time thus filling the "main gap" left in the paper "Tarskian set constraints" by Givan, Kozen, McAllester and Witty.

The Head Hierarchy for Oblivious Finite Automata with Polynomial Advice Collapses
by Holger Petersen

Abstract:
We show that the hierarchy of classes of languages accepted by finite multi-head automata with oblivious head movements that receive polynomial advice strings collapses to the fifth level. A characterization of nondeterministic logarithmic space with polynomial advice is simplified. In the presence of polynomial advice, the question whether deterministic and nondeterministic logarithmic space are equivalent can be reduced to the question whether simple nondeterministic automata can be simulated deterministically. Polynomial time can be characterized by a one-head device.
For automata without advice we prove that multi-head counter automata, stack automata and non-erasing stack automata do not lose power by the restriction to oblivious head movements.

A Separation of Planar Circuits
by B. Csaba, A. Pluhar, T. Szeles

Abstract:
There are several lower bounds for planar circuit complexity of Boolean functions. Here we are interested in that if planar circuits with all input and output nodes are located on the outer face are less powerfull than planar circuits in general. Using a special basis B, we shall give an `n against n^3/2' separation between the above mentioned two models. That is we exhibit a sequence of functions f_n, such that the computation of f_n by a planar circuit needs O(n) gates over the basis B, while it needs \Omega(n^{3/2}) in the restricted model. It is also shown that this is the worst case since, over any reasonable basis, a planar circuit of size O(n) can be transformed to a restricted one of size O(n^{3/2}).