A fuzzy computational model implementation
A non-deteministic time hierarchy over the reals.
A simplification functor for coalgebras.
A space lower bound for acceptance by one-way -alternating machines
A Space Lower Bound for Acceptance by One-Way Π2-Alternating Machines
We show that one-way Π2-alternating Turing machines cannot accept unary nonregular languages in o(log n) space. This holds for an accept mode of space complexity measure, defined as the worst cost of any accepting computation. This lower bound should be compared with the corresponding bound for one-way Σ2-alternating machines, that are able to accept unary nonregular languages in space O(log log n). Thus, Σ2-alternation is more powerful than Π2-alternation for space bounded one-way machines with...
A survey on real structural complexity theory.
A Turing machine oracle hierarchy. I.
A Turing machine oracle hierarchy. II.
A Turing machine space hierarchy
An application of results by Hardy, Ramanujan and Karamata to Ackermannian functions.
An O(n log n) Algorithm for the All-Nearest-Neighbors Problem.
An operational semantics for process algebra
Automata with modulo counters and nondeterministic counter bounds
We introduce and investigate Nondeterministically Bounded Modulo Counter Automata (NBMCA), which are two-way multi-head automata that comprise a constant number of modulo counters, where the counter bounds are nondeterministically guessed, and this is the only element of nondeterminism. NBMCA are tailored to recognising those languages that are characterised by the existence of a specific factorisation of their words, e. g., pattern languages. In this work, we subject NBMCA to a theoretically sound...
Automata with two-sided pushdowns defined over free groups generated by reduced alphabets
This paper introduces and discusses a modification of pushdown automata. This modification is based on two-sided pushdowns into which symbols are pushed from both ends. These pushdowns are defined over free groups, not free monoids, and they can be shortened only by the standard group reduction. We demonstrate that these automata characterize the family of recursively enumerable languages even if the free groups are generated by no more than four symbols.