| |
|
|
| |
| |
|
Date Reviewed |
|
| |
1 - 10 of 17
reviews
|
|
|
 |
|
|
|
|
On the uniform computational content of computability theory
Brattka V., Hendtlass M., Kreuzer A. Theory of Computing Systems 61(4): 1376-1426, 2017. Type: Article
Weihrauch reducibility (≤W) is a type of reducibility relation that can be used to classify the uniform computational content of various mathematical objects. It is first defined for multivalued functions between s...
|
Jun 26 2018 |
|
|
|
|
|
|
Polynomial functions over finite commutative rings
Bulyovszky B., Horváth G. Theoretical Computer Science 703 76-86, 2017. Type: Article
The problem dealt with is as follows: given a finite ring ~R and a function f: R → R, decide if f can be represented by a polynomi...
|
Jan 22 2018 |
|
|
|
|
|
|
Parameterized complexity of critical node cuts
Hermelin D., Kaspi M., Komusiewicz C., Navon B. Theoretical Computer Science 651(C): 62-75, 2016. Type: Article
The critical node cut (CNC) problem is defined as follows: given an (undirected) graph G and two integers k and x, decide if k nodes can be removed from
|
Feb 13 2017 |
|
|
|
|
|
|
On bounded languages and reversal-bounded automata
Ibarra O., Ravikumar B. Information and Computation 24630-42, 2016. Type: Article
A language L is bounded context-free if it is accepted by a pushdown automaton (PDA) M with a bounded number of reversals; that is, there is a constant upper bound for the number of times ...
|
May 2 2016 |
|
|
|
|
|
|
Verifying time complexity of Turing machines
Gajser D. Theoretical Computer Science 600(C): 86-97, 2015. Type: Article
For any function T, consider the following decision problem HALTT: does a given Turing machine M run in time at most T(n)? More g...
|
Dec 8 2015 |
|
|
|
|
|
|
DFA minimization
García P., López D., Vázquez de Parga M. Theoretical Computer Science 583(C): 78-85, 2015. Type: Article
One classical problem in theoretical computer science is the minimization of a given deterministic finite automaton (DFA). This paper establishes a relationship between the two principal methods: minimization by splitting of partitions...
|
Oct 20 2015 |
|
|
|
|
|
|
Oblivious two-way finite automata: decidability and complexity
Kutrib M., Malcher A., Pighizzini G. Information and Computation 237294-302, 2014. Type: Article
Finite automata (FA) have been a topic of considerable interest during the last decades, and several variants have been considered. Specifically, a finite automaton may be deterministic or nondeterministic as well as one-way or two-way...
|
Jan 27 2015 |
|
|
|
|
|
|
Computational completeness of equations over sets of natural numbers
Jeż A., Okhotin A. Information and Computation 23756-94, 2014. Type: Article
One basic issue in several areas of theoretical computer science is to characterize various classes C of functions or sets as those functions/sets that can be created from certain simple initial objects by means of c...
|
Nov 13 2014 |
|
|
|
|
|
|
On a compact encoding of the swap automaton
Fredriksson K., Giaquinta E. Information Processing Letters 114(7): 392-396, 2014. Type: Article
A swapped version of a string P is a string obtained from P by a combination of swaps of adjacent symbols, with each symbol involved in at most one swap. This paper deals with the problem of findin...
|
Aug 19 2014 |
|
|
|
|
|
|
Approximately counting semismooth integers
Bach E., Sorenson J. ISSAC 2013 (Proceedings of the 38th International Symposium on Symbolic and Algebraic Computation, Boston, MA, Jun 26-29, 2013) 23-30, 2013. Type: Proceedings
An integer n is y-smooth if and only if (iff) all prime factors of n are ≤ y. An integer n is (y,z
|
Apr 3 2014 |
|
|
|
|
|
| |
|
|
| |
|
|
