
110 of 835 reviews 
Date Reviewed  

Languages with membership determined by single letter factors Higgins P., Alwan S. Theoretical Computer Science 680 1524, 2017. Type: Article
This paper continues a previous one [1] by the authors, Higgins and Alwan, expanding on the notion of scan languages that require a word to be read completely before determining whether the word belongs to the language. This applies to every word,...

Mar 8 2018 


The undecidability of arbitrary arrow update logic van Ditmarsch H., van der Hoek W., Kuijer L. Theoretical Computer Science 693 112, 2017. Type: Article
Arrow update logic is one instance of socalled dynamic epistemic logics. These are logical frameworks that allow for the modeling of change of knowledge or belief. In the special case of arrow update logics, one can in effect model that one agent...

Mar 7 2018 


Nonregular unary language and parallel communicating WatsonCrick automata systems Chatterjee K., Ray K. Theoretical Computer Science 705 113117, 2018. Type: Article
WatsonCrick finite automata have been introduced as a possible model of DNA computation. They differ from their classical counterpart in that they are capable of working on doublestranded sequences. The strands are processed by two independent h...

Feb 22 2018 


Asymptotic medians of random permutations sampled from reversal random walks Jamshidpey A., Sankoff D. Theoretical Computer Science 698 913, 2017. Type: Article
The area of application of this interesting, and quite advanced, fivepage paper is in the study of genomics and chromosomal rearrangements. The median specified in the title “is a point whose sum of distances to k given p...

Feb 15 2018 


Polynomial functions over finite commutative rings Bulyovszky B., Horváth G. Theoretical Computer Science 703 7686, 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 polynomial ~p

Jan 22 2018 


Inplace algorithms for exact and approximate shortest unique substring problems Hon W., Thankachan S., Xu B. Theoretical Computer Science 690 1225, 2017. Type: Article
The problem of exact shortest unique substring (SUS) is formulated as follows:...

Dec 27 2017 


A general approximation method for bicriteria minimization problems Halffmann P., Ruzika S., Thielen C., Willems D. Theoretical Computer Science 695 115, 2017. Type: Article
Many applications in operations research require the simultaneous optimization of multiple (typically mutually opposing) objective functions. Since the general problem is usually computationally intractable, bicriteria optimization restricts itsel...

Nov 9 2017 


Uniform continuity of relations and nondeterministic cellular automata Furusawa H. Theoretical Computer Science 673 1929, 2017. Type: Article
Cellular automata are computational structures that can be applied for modeling a wide range of systems in different areas of science. Usually they are characterized by local rules operating on individual cells and their neighborhoods. This paper ...

Oct 19 2017 


Fast rendezvous on a cycle by agents with different speeds Feinerman O., Korman A., Kutten S., Rodeh Y. Theoretical Computer Science 688 7785, 2017. Type: Article
Feinerman et al. provide illustrations concerned with the usefulness of different processing speeds and asynchrony of tasks of the operating agents in distributed computing systems. To investigate the rendezvous (meeting point) problem, a cycle to...

Oct 16 2017 


A linear algorithm for a perfect matching in polyomino graphs Lin Y., Zhang F. Theoretical Computer Science 6758288, 2017. Type: Article
Perfect matching in a graph is a set of edges where any pair does not share a common vertex and every vertex of the graph is the endpoint of an edge from that set. From the paper’s introduction: “A polyomino graph is a connected finite...

Aug 10 2017 







