A representation of recursively enumerable languages by two
homomorphisms and a quotient. Theoretical Computer Science,
62, 235-49, 1988.
\bb
Abstract:
A new representation for recursively enumerable languages is
presented. It uses a pair of homomorphisms and the left (or right)
quotient: For each recursively enumerable language $L$ one can
find homomorphisms $h_1,h_2:\Sigma_A^*\rightarrow\Sigma_B^*$, such
that $w\in\Sigma_L^*$ is a word in $L$ if and only if
$w=h_1(\alpha){\backslash}h_2(\alpha)$ for some
$\alpha\in\Sigma_A^*$. (Or, each recursively enumerable language
can be given by $L=O(h_1{\backslash}h_2)\cap\Sigma_L^*$, where
$O(h_1{\backslash}h_2)$ is the so-called right overflow language
defined as $O(h_1{\backslash}h_2) = \{h_1(x){\backslash}h_2(x);
x\in\Sigma_A^*\}$.)
\bb
Grammars with context dependency restricted to synchronization.
Proc. Math. Found. Comput. Sci., vol. 233 of Lect. Notes
Comput. Sci., pp.370-378. Springer-Verlag, 1986.
\bb
Abstract:
The paper investigates the properties of the class of languages
that are generated by phrase-structure grammars having all of the
rules context-free, with the exception of a single rule, which is
of the form $AB\rightarrow\varepsilon$. The importance of this
language class follows from the fact that using just two
non-context-free rules, or using a single non-context-free rule
with a left hand side of length three, gives grammars capable of
generating any recursively enumerable language. On the other hand,
without non-context-free rules, we are able to generate
context-free languages only. The class of languages generated by
grammars using only one non-context-free rule
$AB\rightarrow\varepsilon$ were named context-synchronized, since
the only context dependency we can utilize is synchronized
rewriting by context-free rules. Nevertheless, this is sufficient
to generate an NP-complete language (knapsack problem). Several
different characterizations of context-synchronize languages are
presented. It also turned out that the class forms an AFL
(abstract family of languages).
\bb
Normal forms for phrase-structure grammars. RAIRO Inform.
Theor., 25, 473-96, 1991.
(Conference version: Context-free-like forms for the
phrase-structure grammars. Proc. Math. Found. Comput.
Sci., vol. 324 of Lect. Notes Comput. Sci.,
pp.309-17. Springer-Verlag, 1988).
\bb
Abstract:
Some new normal forms for the phrase-structure grammars are
presented. Each phrase-structure grammar can be replaced by an
equivalent grammar with all of the context free rules being of the
form $S{\rightarrow}v$, where $S$ is the initial nonterminal, what
concerns non context free rules five different situations may
occur: either two extra rules of the form
$AB\rightarrow\varepsilon$, $CD\rightarrow\varepsilon$, or two
extra rules $AB\rightarrow\varepsilon$,
$CC\rightarrow\varepsilon$, or two extra rules
$AA\rightarrow\varepsilon$, $BBB\rightarrow\varepsilon$, or even
a single extra rule $ABBBA\rightarrow\varepsilon$, or a single
extra rule $ABC\rightarrow\varepsilon$. In all cases, no
additional nonterminal symbols are required.
\bb
How to generate languages using only two pairs of parentheses.
J. Inform. Process. Cybernet. (EIK), 27, 303-15, 1991.
\bb
Abstract:
A new normal form for the phrase-structure grammar is presented:
Each phrase-structure grammar can be replaced by an equivalent
grammar with all of the rules being context-free, but two extra
rules $(\,)\rightarrow\varepsilon$, $[\,]\rightarrow\varepsilon$,
using only five nonterminal symbols, namely, $S, (, ), [, ],$
where $S$ is the initial symbol. Moreover, the simulation of
a general phrase-structure grammar by a grammar in this normal
form is linear, so that there is no loss of time or space
efficiency.
\bb
Nondeterministic computations in sublogarithmic space and space
constructibility. SIAM J. Comput., 20, 484-98, 1991.
(Conference version: Proc. Internat. Colloq. Automata,
Languages, \& Programming, vol. 443 of Lect. Notes Comput.
Sci., pp.111-24. Springer-Verlag, 1990).
\bb
Abstract:
The open problem of nondeterministic space constructibility for
sublogarithmic functions is resolved. It is shown that there are
no unbounded monotone increasing nondeterministically space
constructible functions such that
$\sup_{n\rightarrow\infty}s(n)/log(n)=0$. Consequently, space
constructibility of monotone functions cannot be used to separate
nondeterministic space from deterministic space, even for a very
low-level complexity range, since functions like $\log\log(n)$ and
$\sqrt{\log(n)}$ are not space constructible by nondeterministic
Turing machines. This result is obtained by the extension of the
$n{\rightarrow}n+n!$ method, described in [Hierarchies of memory
limited computations, IEEE Conference Record on Switching Circuit
Theory and Logical Design, 1965, pp.179-190], to the
nondeterministic case.
\bb
Tally versions of the Savitch and Immerman-Szelepcsenyi theorems
for sublogarithmic space. SIAM J. Comput., 22, 102-13, 1993.
\bb
Abstract:
We shall show that for each $s(n)$-space-bounded nondeterministic
Turing machine recognizing a language $L{\subseteq}1^*$ there
exists an equivalent deterministic $O(s^2(n))$-space-bounded
machine, and also a nondeterministic $O(s(n))$-space-bounded
machine recognizing the complement of $L$, for any $s(n)$,
independent of whether $s(n)$ is below $\log(n)$ or space
constructible. In other words, the Savitch [J. Comput. System
Sci., 4(1970), pp.177-192] and Immerman-Szelepcsenyi [SIAM J.
Comput., 17(1988), pp.935-938], [Acta Inform., 26(1988),
pp.279-284] theorems can be extended to any space bound $s(n)$ for
languages over a single-letter alphabet.
\bb
A lower bound for the nondeterministic space complexity of
context-free recognition. Inform. Process. Lett., 42,
25-27, 1992.
With H.Alt and K.Mehlhorn.
\bb
Abstract:
We prove a $\log(n)$ lower bound on the nondeterministic space
complexity of every nonregular deterministic context-free
language.
\bb
Sublogarithmic $\Sigma_2$-SPACE is not closed under complement and
other separation results. RAIRO Inform. Theor., 27, 349-66,
1993.
\bb
Abstract:
We shall show, for each $s(n)$ between $\log\log(n)$ and
$\log(n)$, that $\Sigma_2$-SPACE$(s(n))$ is not closed under
complement, because $\Sigma_2$-SPACE$(s(n)) - \Pi_2$-SPACE$(s(n))
\neq\emptyset$. This implies that the alternating hierarchy does
not collapse below the level 3 and that the first three levels are
separated, i.e., $\Sigma_1$-SPACE$(s(n)) \subset
\Sigma_2$-SPACE$(s(n)) \subset \Sigma_3$-SPACE$(s(n))$.
\bb
A hierarchy that does not collapse: Alternations in low level
space. RAIRO Inform. Theor., 28, 465-512, 1994.
\bb
Abstract:
The alternation hierarchy of $s(n)$ space bounded machines does
not collapse for $s(n)$ below $\log(n)$. That is, for each $s(n)$
between $\log\log(n)$ and $\log(n)$ and each $k{\geq}2$,
$\Sigma_{k-1}$-SPACE$(s(n))$ and $\Pi_{k-1}$-SPACE$(s(n))$ are
proper subsets of $\Sigma_k$-SPACE$(s(n))$ and also of
$\Pi_k$-SPACE$(s(n))$. Moreover, $\Sigma_k$-SPACE$(s(n))$ is not
closed under complement and intersection, similarly,
$\Pi_k$-SPACE$(s(n))$ is not closed under complement and union.
\bb
Bridging across the log(n) space frontier. Inform. \&
Comput., 142, 127-58, 1998.
(Conference version: Proc. Math. Found. Comput. Sci.,
vol. 969 of Lect. Notes Comput. Sci., pp.50-65.
Springer-Verlag, 1995).
\bb
Abstract:
The paper establishes the importance of even the lowest possible
level of space bounded computations. We show that DLOG does not
coincide with NLOG if and only if there exists a tally set in
NSPACE$(\log\log(n))$ $-$ DSPACE$(\log\log(n))$. This result
stands in perfect analogy to the related results concerning linear
space or exponential time. Moreover, the above problem is
equivalent to the existence of a function $s(n)$, with arbitrarily
slow or rapid growth rate, that is nondeterministically fully
space constructible but cannot be constructed deterministically.
We also present a `hardest' fully space constructible $s(n) \in
O(\log\log(n))$, a functional counterpart of $\log$-space complete
languages. These nonrelativized results are obtained by the use of
oracle machines consuming much larger amount of space, in range
between $n$ and $2^{d{\cdot}n}$.
\bb
Sublogarithmic bounds on space and reversals. SIAM J.
Comput., 28, 325-40, 1999.
With C.Mereghetti and G.Pighizzini.
\bb
Abstract:
The complexity measure under consideration is SPACE $\times$
REVERSALS for Turing machines that are able to branch both
existentially and universally. We show that, for any function
$h(n)$ between $\log\log(n)$ and $\log(n)$, $\Pi_1$SPACE $\times$
REVERSALS$(h(n))$ is separated from $\Sigma_1$SPACE $\times$
REVERSALS$(h(n))$ as well as from $co\Sigma_1$SPACE $\times$
REVERSALS$(h(n))$, for middle, accept, and weak modes of this
complexity measure. This also separates determinism from the
higher levels of the alternating hierarchy. For `well-behaved'
functions $h(n)$ between $\log\log(n)$ and $\log(n)$, almost all
of the above separations can be obtained by using unary witness
languages.
In addition, the construction of separating languages contributes
to the research on minimal resource requirements for computational
devices capable of recognizing nonregular languages. For any
(arbitrarily slow growing) unbounded monotone recursive function
$f(n)$, a nonregular unary language is presented that can be
accepted by a middle $\Pi_1$ alternating Turing machine in $s(n)$
space and $i(n)$ input head reversals, with $s(n){\cdot}i(n) \in
O(\log\log(n){\cdot}f(n))$. Thus, there is no exponential gap for
the optimal lower bound on the product $s(n){\cdot}i(n)$ between
unary and general nonregular language acceptance --- in sharp
contrast with the one-way case.
\bb
A variant of inductive counting. Theoret. Comput. Sci.,
11 pages, to appear.
\bb
Abstract:
We present a new version of the inductive counting, accepting the
complement of an NSPACE$(s(n))$ language nondeterministically in
space $O(s(n))$, independent of whether $s(n){\geq}\log(n)$, but
using an additional `one-way pebble' --- a movable marker placed
on the input tape. This reduces the space used by inductive
counting to $\log(n)+O(s(n))$ bits on the binary work tape and
gives the weakest known nondeterministic device accepting
a co-NSPACE$(o(\log(n)))$ language.
\bb
A speed-up theorem without tape compression. Theoret. Comput.
Sci., 118, 49-65, 1993.
(Conference version: Proc. Math. Found. Comput. Sci.,
vol. 452 of Lect. Notes Comput. Sci., pp.285-91.
Springer-Verlag, 1990).
\bb
Abstract:
We shall show that, for each nondeterministic single-tape Turing
machine $M$ of time complexity $T(n){\geq}n^2$ and each
$K{\geq}1$, there exists an equivalent $K$ times faster
nondeterministic Turing machine $M'$ writing only zeroes and ones
on its tape. In other words, we can obtain the linear speed-up
while preserving the binary worktape alphabet. Therefore,
nondeterministic single-tape Turing machines do not require tape
compression for speeding up.
\bb
A communication hierarchy of parallel computations. Theoret.
Comput. Sci., 198, 99-130, 1998.
\bb
Abstract:
The paper extends and generalizes the notion of synchronized
alternation, studied in the literature. We show that, though the
underlying machine for the synchronized alternation is
alternating, the nature of message broadcasting is
nondeterministic. Therefore, we introduce a new computational
model, the so-called communicating alternation machines;
alternating machines equipped with an alternating communication.
Then we show that the two-level communication, i.e., existential
and universal, can be generalized uniformly arbitrarily many
times, giving communication with $r$ communication levels. This
allows, among others, to extend the well-known characterization of
DLOGSPACE, NLOGSPACE, P, and PSPACE by deterministic,
nondeterministic, alternating, and synchronized alternating
two-way read-only multihead finite automata. The above
characterization represents just the first four members of an
infinite hierarchy of multihead automata, representing the entire
fundamental complexity hierarchy. The first `new' class added is
DEXPTIME, corresponding to the two-level communicating alternation
automata.
\bb
Asymptotically efficient in-place merging. Theoret. Comput.
Sci., 27 pages, to appear.
With J.Katajainen and T.Pasanen.
\bb
Abstract:
Two linear-time algorithms for in-place merging are presented.
Both algorithms perform at most $m(t+1)+n/2^t+o(m)$ comparisons,
where $m$ and $n$ are the sizes of the input sequences,
$m{\leq}n$, and $t=\lfloor\log_2(n/m)\rfloor$. The first algorithm
is for unstable merging and it carries out no more than
$3(n+m)+o(m)$ element moves. The second algorithm is for stable
merging and it accomplishes at most $5n+12m+o(m)$ moves.
\bb