Radix enumeration of rational languages
We prove that the function that maps a word of a rational language onto its successor for the radix order in this language is a finite union of co-sequential functions.
Random generation for finitely ambiguous context-free languages
We prove that a word of length from a finitely ambiguous context-free language can be generated at random under uniform distribution in time by a probabilistic random access machine assuming a logarithmic cost criterion. We also show that the same problem can be solved in polynomial time for every language accepted by a polynomial time -NAuxPDA with polynomially bounded ambiguity.
Random Generation for Finitely Ambiguous Context-free Languages
We prove that a word of length n from a finitely ambiguous context-free language can be generated at random under uniform distribution in O(n2 log n) time by a probabilistic random access machine assuming a logarithmic cost criterion. We also show that the same problem can be solved in polynomial time for every language accepted by a polynomial time 1-NAuxPDA with polynomially bounded ambiguity.
Random -sat: the limiting probability for satisfiability for moderately growing .
Random Phenomena and Some Systems Generating Words
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