|
Browse All Reviews > Theory Of Computation (F) > Mathematical Logic And Formal Languages (F.4) > Formal Languages (F.4.3) > Decision Problems (F.4.3...)
|
|
|
|
|
|
|
|
|
1-10 of 13
Reviews about "Decision Problems (F.4.3...)":
|
Date Reviewed |
|
Randomness and elements of decision theory applied to signals Borda M., Terebes R., Malutan R., Ilea I., Cislariu M., Miclea A., Barburiceanu S., Springer International Publishing, Cham, Switzerland, 2021. 259 pp. Type: Book (978-3-030903-13-8) Communication and image processing systems are commonly modeled using random processes and are of immense interest in electronics engineering. This short volume attempts to provide an introduction to various topics related to this subject....
|
Sep 21 2023 |
|
Deciding polynomial-transcendental problems McCallum S., Weispfenning V. Journal of Symbolic Computation 47(1): 16-31, 2012. Type: Article
The theory of quantifier elimination over real closed fields goes back to Tarski [1], though practical methods had to wait for Collins in 1975 [2]. Given a formula Q1x1, ..., ...
|
May 14 2013 |
|
A new class of algebraic series having a decidable equivalence problem Honkala J. Fundamenta Informaticae 53(3,4): 315-320, 2002. Type: Article
This paper extends the fact that it is decidable whether r = s for two given algebraic series r , s over a computable field E and on the same alphabet
|
Nov 26 2003 |
|
On codes with a finite deciphering delay: constructing uncompletable words Néraud J., Selmi C. Theoretical Computer Science 255(1-2): 151-162, 2001. Type: Article
The problem of constructing a witness to the non-completeness of a given code is considered. The paper focuses on finite codes that have finite deciphering delay, and presents an algorithm that, given such a code, constructs an uncompl...
|
Apr 23 2002 |
|
On the combinatorial and algebraic complexity of quantifier elimination Basu S., Roy M. Journal of the ACM 43(6): 1002-1045, 1996. Type: Article
The problem of quantifier elimination for first-order formulas over real closed fields has applications in areas such as control theory and control system design. Consequently, this long, dense paper deserves a wider readership than it...
|
Jul 1 1997 |
|
Transducers and the decidability of independence in free monoids Jürgensen H., Salomaa K., Yu S. (ed) Theoretical Computer Science 134(1): 107-117, 1994. Type: Article
For many classes of codes, or of languages related to codes, it is decidable whether a given regular language belongs to the class. However, the proofs depend on special properties of each class, and the ideas cannot be used in other c...
|
Nov 1 1995 |
|
On D0L systems with immigration Honkala J. Theoretical Computer Science 120(2): 229-245, 1993. Type: Article
The kind of L system treated in this routine paper was introduced by Honkala and Salomaa. A D0L system with immigration, or ImD0L system, is a triple G = ( &Sgr; , h , B ) where &Sgr; is an alphabet,
|
Oct 1 1994 |
|
A regularity test for dual bordered OS systems Bucher W. Acta Informatica 23(3): 245-253, 1986. Type: Article
The structural properties of a context-free language induced by the structural properties of its derivation rules are of interest in formal language theory. The open problem approached in this paper concerns the regularity of a context...
|
Jul 1 1987 |
|
Polynomial-time algorithm for the orbit problem Kannan R., Lipton R. Journal of the ACM 33(4): 808-821, 1986. Type: Article
A is an n × n array; x and y are n × 1. The orbit problem is as follows: Decide if there is a nonneg...
|
Jul 1 1987 |
|
An algorithm to decide whether a rational subset of k is recognizable Gohon P. Theoretical Computer Science 41(1): 51-59, 1985. Type: Article
Ginsburg and Spanier [1] proved that it is decidable whether a rational subset of &NN; k, with k ≥ 2, is recognizable. Their proof is based on the decidability of Presburger a...
|
Jul 1 1987 |
|
|
|
|
|
|