| |
Browse All Reviews > Theory Of Computation (F) > Mathematical Logic And Formal Languages (F.4) > Grammars And Other Rewriting Systems (F.4.2) > Decision Problems (F.4.2...)
|
|
 |
|
|
| |
|
|
| |
1-10 of 16
Reviews about "Decision Problems (F.4.2...)":
|
Date Reviewed |
| |
Decidability and independence of conjugacy problems in finitely presented monoids
Araújo J., Kinyon M., Konieczny J., Malheiro A. Theoretical Computer Science 731(C): 88-98, 2018. Type: Article
In a group, two elements a and b are conjugate if there is some g with gag-1 = b. Conjugacy is an equivalence relation and can be...
|
Jul 20 2018 |
| |
Formative processes with applications to the decision problem in set theory: II. Powerset and singleton operators, finiteness predicate
Cantone D., Ursino P. Information and Computation 237215-242, 2014. Type: Article
In an effort to marry set theory and theoretical computer science, in 1970 the Computable Set Theory project was launched to study decidable fragments of set theory. A challenging question for researchers has been finding a way to over...
|
May 27 2015 |
| |
Using grammars for pattern recognition in images: a systematic review
Pedro R., Nunes F., Machado-Lima A. ACM Computing Surveys 46(2): 1-34, 2013. Type: Article
Grammars were used in computer science from the beginning for designing compilers for the first programming language. They were later used in image generation (for example, L-systems were used to generate beautiful pictures of plants)....
|
Mar 12 2014 |
| |
 Linguistic decision making: theory and methods
Xu Z., Springer Publishing Company, Incorporated, 2013. 300 pp. Type: Book (978-3-642294-39-6)
What is “linguistic decision making” exactly?...
|
Jul 1 2013 |
| |
Practical algorithms for unsatisfiability proof and core generation in SAT solvers
Asín Achá R., Nieuwenhuis R., Oliveras A., Rodríguez-Carbonell E. AI Communications 23(2-3): 145-157, 2010. Type: Article
Boolean satisfiability (SAT), a nondeterministic polynomial-time (NP) complete problem, deals with determining whether a given set of Boolean propositions can evaluate to a true value, by choosing an appropriate assignment to their con...
|
Aug 11 2010 |
| |
Decidability of bisimulation equivalence for normed pushdown processes
Stirling C. (ed) Theoretical Computer Science 195(2): 113-131, 1998. Type: Article
The old question of when two pushdown automata (PDAs) generate the same language is undecidable. However, the question of whether two deterministic PDAs (DPDAs) generate the same language was open for a long time. Since parsers for pro...
|
May 1 1999 |
| |
Omega-termination is undecidable for totally terminating term rewriting systems
Geser A. Journal of Symbolic Computation 23(4): 399-411, 1997. Type: Article
Using a reduction from Post’s correspondence problem (PCP), Geser shows that it is undecidable whether a term rewriting system (TRS) is terminating when the ordering of terms--the reduction order--can be ind...
|
Mar 1 1998 |
| |
Some decision problems for parallel communicating grammar systems
Ţiplea F., Ene C., Ionescu C., Procopiuc O. Theoretical Computer Science 134(2): 365-385, 1994. Type: Article
The study of parallelism is handicapped by the lack of an appropriate model of parallel computation that is sufficiently powerful and general to reflect the available technology and simple enough to permit the derivation of useful prop...
|
Nov 1 1995 |
| |
Completeness of combinations of conditional constructor systems
Middeldorp A. Journal of Symbolic Computation 17(1): 3-21, 1994. Type: Article
Both completeness and semi-completeness are decomposable properties of constructor systems (also known as term rewriting systems). The principal result in this paper is that these properties are also decomposable in conditional constru...
|
Sep 1 1995 |
| |
An algorithm for finding canonical sets of ground rewrite rules in polynomial time
Gallier J., Narendran P., Plaisted D., Raatz S., Snyder W. Journal of the ACM 40(1): 1-16, 1993. Type: Article
Since every algebra of ground terms admits a total reduction ordering, Knuth-Bendix type completion procedures do not fail on input sets consisting of ground equations, and terminate with a canonical system equivalent to the input set....
|
Nov 1 1993 |
| |
|
|
| |
|
|
