Range Searching with Efficient Hierarchical Cuttings.
Rational stochastic automata in formal language theory
Rational strong codes and structure of rational group languages.
Rational tree relations.
Reaction automata working in sequential manner
Based on the formal framework of reaction systems by Ehrenfeucht and Rozenberg [Fund. Inform. 75 (2007) 263–280], reaction automata (RAs) have been introduced by Okubo et al. [Theoret. Comput. Sci. 429 (2012) 247–257], as language acceptors with multiset rewriting mechanism. In this paper, we continue the investigation of RAs with a focus on the two manners of rule application: maximally parallel and sequential. Considering restrictions on the workspace and the λ-input mode, we introduce the corresponding...
Real time recognition with cellular automata : a meaningful example
Réalisation des operations arithmétiques fondamentales avec les nombres complexes au moyen des spectres mathématiques de M. Petrovitch sur les calculatrices électroniques
Real-time and complexity problems in automata theory
Rebootable and suffix-closed -power languages
Recent results and open problems in analytic computational complexity
Recognizable filters and ideals
Recognizing HH-free, HHD-free, and Welsh-Powell opposition graphs.
Recognizing when heuristics can approximate minimum vertex covers is complete for parallel access to NP
For both the edge deletion heuristic and the maximum-degree greedy heuristic, we study the problem of recognizing those graphs for which that heuristic can approximate the size of a minimum vertex cover within a constant factor of , where is a fixed rational number. Our main results are that these problems are complete for the class of problems solvable via parallel access to . To achieve these main results, we also show that the restriction of the vertex cover problem to those graphs for which...
Recognizing when heuristics can approximate minimum vertex covers is complete for parallel access to NP
For both the edge deletion heuristic and the maximum-degree greedy heuristic, we study the problem of recognizing those graphs for which that heuristic can approximate the size of a minimum vertex cover within a constant factor of r, where r is a fixed rational number. Our main results are that these problems are complete for the class of problems solvable via parallel access to NP. To achieve these main results, we also show that the restriction of the vertex cover problem to those...
Reconnaissabilité des substitutions et complexité des suites automatiques
Reconstructibility of Boolean control networks with time delays in states
This paper deals with the reconstructibility of Boolean control networks (BCNs) with time delays in states. First, a survey on the semi-tensor product, weighted pair graph, constructed forest and finite automata is given. Second, by using the weighted pair graph, constructed forest and finite automata, an algorithm is designed to judge whether a Boolean control network with time delays in states is reconstructable or not under a mild assumption. Third, an algorithm is proposed to determine the current...
Reconstruction of complete interval tournaments. II.
Recouvrement et partition en chaînes des arêtes d'un graphe cubique
Rectilinear Shortest Paths in the Presence of Rectangular Barriers.
Recursive classification of pseudo-random sequences