The Experts below are selected from a list of 312 Experts worldwide ranked by ideXlab platform
Osamu Watanabe - One of the best experts on this subject based on the ideXlab platform.
-
the difference between polynomial time many one and Truth Table reducibilities on distributional problems
Theory of Computing Systems \ Mathematical Systems Theory, 2002Co-Authors: Shin Aida, Rainer Schuler, Tatsuie Tsukiji, Osamu WatanabeAbstract:In this paper we separate many-one reducibility from Truth-Table reducibility for distributional problems in DistNP under the hypothesis that P � NP . As a first example we consider the 3-Satisfiability problem (3SAT) with two different distributions on 3CNF formulas. We show that 3SAT with a version of the standard distribution is Truth-Table reducible but not many-one reducible to 3SAT with a less redundant distribution unless P = NP . We extend this separation result and define a distributional complexity class C with the following properties: (1) C is a subclass of DistNP, this relation is proper unless P = NP. (2) C contains DistP, but it is not contained in AveP unless DistNP \subseteq AveZPP. (3) C has a ≤ p m -complete set. (4) C has a ≤ p tt -complete set that is not ≤ p m -complete unless P = NP. This shows that under the assumption that P � NP, the two completeness notions differ on some nontrivial subclass of DistNP.
-
on the difference between polynomial time many one and Truth Table reducibilities on distributional problems
Lecture Notes in Computer Science, 2001Co-Authors: Shin Aida, Rainer Schuler, Tatsuie Tsukiji, Osamu WatanabeAbstract:In this paper we separate many-one reducibility from Truth-Table reducibility for distributional problems in DistNP under the hypothesis that P ¬= NP. As a first example we consider the 3-Satisfiability problem (3SAT) with two different distributions on 3CNF formulas. We show that 3SAT using a version of the standard distribution is Truth-Table reducible but not many-one reducible to 3SAT using a less redundant distribution unless P = NP. We extend this separation result and define a distributional complexity class C with the following properties: (1) C is a subclass of DistNP, this relation is proper unless P = NP. (2) C contains DistP, but it is not contained in AveP unless DistNP C AveZPP. (3) C has a ≤ m p -complete set. (4) C has a ≤ tt p -complete set that is not ≤ m p -complete unless P = NP. This shows that under the assumption that P ¬= NP, the two completeness notions differ on some non-trivial subclass of DistNP.
-
on sets bounded Truth Table reducible to p selective sets
Theoretical Informatics and Applications, 1996Co-Authors: Thomas Thierauf, Seinosuke Toda, Osamu WatanabeAbstract:We show that if every NP set in polynomial-time bounded Truth-Table reducible to some P-selective set, then NP is contained in DTIME (2 nO(1/ √ logn) . In the proof, we implement a recursive procedure that reduces the number of nondeterministic steps of a given nondeterministic computation.
-
on sets bounded Truth Table reducible to p selective sets
Symposium on Theoretical Aspects of Computer Science, 1994Co-Authors: Thomas Thierauf, Seinosuke Toda, Osamu WatanabeAbstract:We show that if every NP set is ≤ btt P -reducible to some P-selective set, then NP is contained in DTIME(\(2^{n^{O\left( {{1 \mathord{\left/{\vphantom {1 {\sqrt {\log n} }}} \right.\kern-\nulldelimiterspace} {\sqrt {\log n} }}} \right)} }\)). The result is extended for some unbounded reducibilities such as ≤ polylog-tt P -reducibility.
-
on polynomial time one Truth Table reducibility to a sparse set
Journal of Computer and System Sciences, 1992Co-Authors: Osamu WatanabeAbstract:Abstract In this paper, we measure “intractability” of complexity classes by considering polynomial time 1-Truth-Table reducibility (in short, ≤1−ttP-reducibility) to a sparse set. We mainly investigate nondeterministic complexity classes that are defined in relation to one-way functions: UP, FewP, UBPP, and UP . We show that if UP (resp., UBPP and UP . has a polynomial time unsolvable problem, then it indeed has a problem that is “tracTable”ot only by being polynomial time unsolvable, but also by being ≤1−ttP-reducible to no sparse set. As an immediate consequence of our observation, we can also prove that if R ≠ NP (resp., P ≠ FewP and P ≠ UP ) then no NP-complete set is ≤ 1−ttP-reducible to a sparse set, and thus no NP-complete set has a p-close approximation; this provides a partial answer to a question asked by Schoning.
Walter Schaeken - One of the best experts on this subject based on the ideXlab platform.
-
Truth Table task working memory load latencies and perceived relevance
Journal of cognitive psychology, 2013Co-Authors: Aline Sevenants, Kristien Dieussaert, Walter SchaekenAbstract:The aim of the present study is to uncover the relation between cognitive ability and the answer patterns yielded by the Truth Table task. According to the Classical Mental Models Theory, people with high working memory capacity answer according to two-valued or “logical” answer patterns. The Suppositional Theory and the Revised Mental Models Theory predict that the answer patterns given by the most intelligent ones are three-valued or “defective”. Correlations are examined, and in three experiments it is tested with a dual task paradigm whether a differential working memory load alters participants' answer patterns. A positive correlation is observed between cognitive ability and three-valued answer patterns, but no effect of the working memory load manipulation is revealed. With an inspection of the classification times we shed light on the processes underlying Truth Table judgements. We conclude that the Revised Mental Models Theory provides the best account for our results.
-
is the Truth Table task mistaken
Thinking & Reasoning, 2012Co-Authors: Aline Sevenants, Kristien Dieussaert, Walter SchaekenAbstract:There is ample evidence that in classical Truth Table task experiments false antecedents are judged as “irrelevant”. Instead of interpreting this in support of a suppositional representation of conditionals, Schroyens (2010a, 2010b) attributes it to the induction problem: the impossibility of establishing the Truth of a universal claim on the basis of a single case. In the first experiment a Truth Table task with four options is administered and the correlation with intelligence is inspected. It is observed that “undetermined” is chosen in one third of the judgements and “irrelevant” in another third. A positive correlation is revealed between intelligence and the number of “irrelevant” and “undetermined” judgements. The data do not exclude that a part of the “irrelevant” judgements in classical Truth Table task experiments might be caused by the induction problem. In the second experiment participants are presented with a simplified four-option Truth Table task and asked for a justification of their judg...
-
Truth Table tasks: Irrelevance and cognitive ability
Thinking & Reasoning, 2011Co-Authors: Aline Sevenants, Kristien Dieussaert, Walter SchaekenAbstract:Two types of Truth Table task are used to examine people's mental representation of conditionals. In two within-participants experiments, participants either receive the same task-type twice (Experiment 1) or are presented successively with both a possibilities task and a Truth task (Experiment 2). Experiment 3 examines how people interpret the three-option possibilities task and whether they have a clear understanding of it. The present study aims to examine, for both task-types, how participants' cognitive ability relates to the classification of the Truth Table cases as irrelevant, and their consistency in doing so. Looking at the answer patterns, participants' cognitive ability influences their classification of the Truth Table cases: A positive correlation exists between cognitive ability and the number of false-antecedent cases classified as “irrelevant”, both in the possibilities task and the Truth task. This favours a suppositional representation of conditionals.
-
Truth Table tasks directionality and negation type
Conference Cognitive Science, 2011Co-Authors: Aline Sevenants, Kristien Dieussaert, Walter SchaekenAbstract:Truth Table Tasks: Directionality and Negation-Type Aline Sevenants (Aline.Sevenants@psy.kuleuven.be) Kristien Dieussaert (Kristien.Dieussaert@psy.kuleuven.be) Walter Schaeken (Walter.Schaeken@psy.kuleuven.be) University of Leuven, Laboratory of Experimental Psychology 102 Tiensestraat, B-3000 Leuven, Belgium Abstract was the first to introduce the ‘defective Truth Table’ (which we will call three-valued, following de Finetti, 1967, 2008; Politzer, Over & Baratgin, 2010), in which false antecedent cases (FT and FF) are considered to be irrelevant with respect to the conditional rather than making it true. The defective implication has a Truth Table of the form TFII and the defective equivalence of the form TFFI. Two types of Truth Table task are used to examine people’s mental representation of conditionals: possibilities tasks and Truth tasks. Despite their high degree of resemblance, the two task types not only differ regarding their number of answer alternatives, but also regarding their directionality: The Truth task concerns the evaluation of the given rule on the basis of situations, while the possibilities task concerns the assessment of situations with respect to the given rule. The aim of the present study is to assess whether participants’ answer patterns depend on the difference in directionality when the difference in number of answer alternatives is controlled for, by presenting both the extended possibilities task and the Truth task in both directions, i.e. from rule to situation and from situation to rule. Moreover, we make use of both implicit and explicit negations. Concerning the negation type, we find more three-valued patterns with implicit than with explicit negations. This is in line with the robust phenomenon of ‘matching bias’. It was replicated that possibilities tasks yield more two-valued answer patterns than Truth tasks, which in turn yield more three-valued patterns than possibilities tasks. No effect of task directionality was observed. The Truth Table tasks: About possibility and Truth Conditional reasoning research has been conducted largely within three main experimental paradigms: the four card selection task, the conditional inference task and the Truth Table task, the latter being the focus of the present manuscript. Throughout psychological reasoning literature, the Truth Table tasks takes two forms, know as the possibilities task and the Truth task. In the classical possibilities task, participants indicate for each of the four possible antecedent-consequent cases whether that specific combination is either possible or impossible with respect to the given rule. In the Truth task, participants are asked to evaluate for each of the four cases whether the combination makes the given rule true, false or is irrelevant with respect to the Truth of the rule. Introduction The interest in the linguistic, psychological and logical meaning of ‘if’ has provided us with a long history of research on thinking and reasoning about conditionals, designed in order to externalize people’s understanding and mental representation of conditionals. Mental models theory vs. Suppositional theory There has been substantial debate in reasoning literature concerning the processes and representations underlying people’s understanding of conditional assertions. The two main theories accounting for the mental representation of conditionals are the mental models theory (MMT) (Johnson- Laird & Byrne, 1991, 2002; Johnson-Laird, Byrne & Schaeken, 1992) and the suppositional theory (ST) (Evans, Over & Handley, 2003a; Evans & Over, 2004; Evans, Handley, Neilens & Over, 2007), making different predictions about the ‘core meaning’, the mental representation of conditionals. According to the MMT, people reason with representations resembling two-valued Truth Tables and according to the ST they reason with representations matching with three-valued Truth Tables. The starting point for much of the debate between the ST and the MMT has been the diverging results on the two kinds of Truth Table task. Classically it has been criticized that each theory makes use of that type of Truth Table task that satisfies their predictions the best: the possibilities task is used by The meaning of ‘if’ Traditionally, there are four different meanings ascribable to conditional ‘if Antecedent then Consequent’ sentences. According to standard logic, the connective ‘if’ is represented as the Truth Table for the material implication, meaning that only the TF falsifies the conditional. An alternative logical possibility for the meaning of ‘if’ is the Truth Table of the material equivalence: ‘C if and only if A’. This is the situation in which the antecedent implies the consequent and the consequent also implies the antecedent. Material implication and material equivalence are the two Truth Tables for conditionals under standard logic. Psychologically however, there is quite a lot of evidence that, next to ‘true’ or ‘false’, people make use of a third Truth value representing conditionals: ‘irrelevant’. Wason (1966)
-
Truth Table tasks the relevance of irrelevant
Thinking & Reasoning, 2008Co-Authors: Aline Sevenants, Kristien Dieussaert, Walter Schaeken, Walter Schroyens, Gery DydewalleAbstract:Two types of Truth Table tasks are used investigating mental representations of conditionals: a possibilities-based and a Truth-based one. In possibilities tasks, participants indicate whether a situation is possible or impossible according to the conditional rule. In Truth tasks participants evaluate whether a situation makes the rule true or false, or is irrelevant with respect to the Truth of the rule. Comparing the two-option version of the possibilities task with the Truth task in Experiment 1, the possibilities task yields logical answer patterns whereas the Truth task yields defective patterns. Adding the irrelevant option to the possibilities task in Experiment 2 leads to a considerable amount of defective patterns in the possibilities task, but still to more logical patterns in the possibilities task than in the Truth task. Experiment 3 shows that directionality matters since rule-to-situation tasks yield more logical answer patterns than do situation-to-rule tasks. We conclude that both task typ...
Aline Sevenants - One of the best experts on this subject based on the ideXlab platform.
-
Truth Table task working memory load latencies and perceived relevance
Journal of cognitive psychology, 2013Co-Authors: Aline Sevenants, Kristien Dieussaert, Walter SchaekenAbstract:The aim of the present study is to uncover the relation between cognitive ability and the answer patterns yielded by the Truth Table task. According to the Classical Mental Models Theory, people with high working memory capacity answer according to two-valued or “logical” answer patterns. The Suppositional Theory and the Revised Mental Models Theory predict that the answer patterns given by the most intelligent ones are three-valued or “defective”. Correlations are examined, and in three experiments it is tested with a dual task paradigm whether a differential working memory load alters participants' answer patterns. A positive correlation is observed between cognitive ability and three-valued answer patterns, but no effect of the working memory load manipulation is revealed. With an inspection of the classification times we shed light on the processes underlying Truth Table judgements. We conclude that the Revised Mental Models Theory provides the best account for our results.
-
is the Truth Table task mistaken
Thinking & Reasoning, 2012Co-Authors: Aline Sevenants, Kristien Dieussaert, Walter SchaekenAbstract:There is ample evidence that in classical Truth Table task experiments false antecedents are judged as “irrelevant”. Instead of interpreting this in support of a suppositional representation of conditionals, Schroyens (2010a, 2010b) attributes it to the induction problem: the impossibility of establishing the Truth of a universal claim on the basis of a single case. In the first experiment a Truth Table task with four options is administered and the correlation with intelligence is inspected. It is observed that “undetermined” is chosen in one third of the judgements and “irrelevant” in another third. A positive correlation is revealed between intelligence and the number of “irrelevant” and “undetermined” judgements. The data do not exclude that a part of the “irrelevant” judgements in classical Truth Table task experiments might be caused by the induction problem. In the second experiment participants are presented with a simplified four-option Truth Table task and asked for a justification of their judg...
-
Truth Table tasks: Irrelevance and cognitive ability
Thinking & Reasoning, 2011Co-Authors: Aline Sevenants, Kristien Dieussaert, Walter SchaekenAbstract:Two types of Truth Table task are used to examine people's mental representation of conditionals. In two within-participants experiments, participants either receive the same task-type twice (Experiment 1) or are presented successively with both a possibilities task and a Truth task (Experiment 2). Experiment 3 examines how people interpret the three-option possibilities task and whether they have a clear understanding of it. The present study aims to examine, for both task-types, how participants' cognitive ability relates to the classification of the Truth Table cases as irrelevant, and their consistency in doing so. Looking at the answer patterns, participants' cognitive ability influences their classification of the Truth Table cases: A positive correlation exists between cognitive ability and the number of false-antecedent cases classified as “irrelevant”, both in the possibilities task and the Truth task. This favours a suppositional representation of conditionals.
-
Truth Table tasks directionality and negation type
Conference Cognitive Science, 2011Co-Authors: Aline Sevenants, Kristien Dieussaert, Walter SchaekenAbstract:Truth Table Tasks: Directionality and Negation-Type Aline Sevenants (Aline.Sevenants@psy.kuleuven.be) Kristien Dieussaert (Kristien.Dieussaert@psy.kuleuven.be) Walter Schaeken (Walter.Schaeken@psy.kuleuven.be) University of Leuven, Laboratory of Experimental Psychology 102 Tiensestraat, B-3000 Leuven, Belgium Abstract was the first to introduce the ‘defective Truth Table’ (which we will call three-valued, following de Finetti, 1967, 2008; Politzer, Over & Baratgin, 2010), in which false antecedent cases (FT and FF) are considered to be irrelevant with respect to the conditional rather than making it true. The defective implication has a Truth Table of the form TFII and the defective equivalence of the form TFFI. Two types of Truth Table task are used to examine people’s mental representation of conditionals: possibilities tasks and Truth tasks. Despite their high degree of resemblance, the two task types not only differ regarding their number of answer alternatives, but also regarding their directionality: The Truth task concerns the evaluation of the given rule on the basis of situations, while the possibilities task concerns the assessment of situations with respect to the given rule. The aim of the present study is to assess whether participants’ answer patterns depend on the difference in directionality when the difference in number of answer alternatives is controlled for, by presenting both the extended possibilities task and the Truth task in both directions, i.e. from rule to situation and from situation to rule. Moreover, we make use of both implicit and explicit negations. Concerning the negation type, we find more three-valued patterns with implicit than with explicit negations. This is in line with the robust phenomenon of ‘matching bias’. It was replicated that possibilities tasks yield more two-valued answer patterns than Truth tasks, which in turn yield more three-valued patterns than possibilities tasks. No effect of task directionality was observed. The Truth Table tasks: About possibility and Truth Conditional reasoning research has been conducted largely within three main experimental paradigms: the four card selection task, the conditional inference task and the Truth Table task, the latter being the focus of the present manuscript. Throughout psychological reasoning literature, the Truth Table tasks takes two forms, know as the possibilities task and the Truth task. In the classical possibilities task, participants indicate for each of the four possible antecedent-consequent cases whether that specific combination is either possible or impossible with respect to the given rule. In the Truth task, participants are asked to evaluate for each of the four cases whether the combination makes the given rule true, false or is irrelevant with respect to the Truth of the rule. Introduction The interest in the linguistic, psychological and logical meaning of ‘if’ has provided us with a long history of research on thinking and reasoning about conditionals, designed in order to externalize people’s understanding and mental representation of conditionals. Mental models theory vs. Suppositional theory There has been substantial debate in reasoning literature concerning the processes and representations underlying people’s understanding of conditional assertions. The two main theories accounting for the mental representation of conditionals are the mental models theory (MMT) (Johnson- Laird & Byrne, 1991, 2002; Johnson-Laird, Byrne & Schaeken, 1992) and the suppositional theory (ST) (Evans, Over & Handley, 2003a; Evans & Over, 2004; Evans, Handley, Neilens & Over, 2007), making different predictions about the ‘core meaning’, the mental representation of conditionals. According to the MMT, people reason with representations resembling two-valued Truth Tables and according to the ST they reason with representations matching with three-valued Truth Tables. The starting point for much of the debate between the ST and the MMT has been the diverging results on the two kinds of Truth Table task. Classically it has been criticized that each theory makes use of that type of Truth Table task that satisfies their predictions the best: the possibilities task is used by The meaning of ‘if’ Traditionally, there are four different meanings ascribable to conditional ‘if Antecedent then Consequent’ sentences. According to standard logic, the connective ‘if’ is represented as the Truth Table for the material implication, meaning that only the TF falsifies the conditional. An alternative logical possibility for the meaning of ‘if’ is the Truth Table of the material equivalence: ‘C if and only if A’. This is the situation in which the antecedent implies the consequent and the consequent also implies the antecedent. Material implication and material equivalence are the two Truth Tables for conditionals under standard logic. Psychologically however, there is quite a lot of evidence that, next to ‘true’ or ‘false’, people make use of a third Truth value representing conditionals: ‘irrelevant’. Wason (1966)
-
Truth Table tasks the relevance of irrelevant
Thinking & Reasoning, 2008Co-Authors: Aline Sevenants, Kristien Dieussaert, Walter Schaeken, Walter Schroyens, Gery DydewalleAbstract:Two types of Truth Table tasks are used investigating mental representations of conditionals: a possibilities-based and a Truth-based one. In possibilities tasks, participants indicate whether a situation is possible or impossible according to the conditional rule. In Truth tasks participants evaluate whether a situation makes the rule true or false, or is irrelevant with respect to the Truth of the rule. Comparing the two-option version of the possibilities task with the Truth task in Experiment 1, the possibilities task yields logical answer patterns whereas the Truth task yields defective patterns. Adding the irrelevant option to the possibilities task in Experiment 2 leads to a considerable amount of defective patterns in the possibilities task, but still to more logical patterns in the possibilities task than in the Truth task. Experiment 3 shows that directionality matters since rule-to-situation tasks yield more logical answer patterns than do situation-to-rule tasks. We conclude that both task typ...
Louise Hay - One of the best experts on this subject based on the ideXlab platform.
-
on Truth Table reducibility to sat
Information & Computation, 1991Co-Authors: Samuel R Buss, Louise HayAbstract:We show that polynomial time Truth-Table reducibility via Boolean circuits to SAT is the same as logspace Truth-Table reducibility via Boolean formulas to SAT and the same as logspace Turing reducibility to SAT. In addition, we prove that a constant number of rounds of parallel queries to SAT is equivalent to one round of parallel queries. We give an oracle relative to which Δ2p is not equal to the class of predicates polynomial time Truth-Table reducible to SAT.
David Wilson - One of the best experts on this subject based on the ideXlab platform.
-
Truth Table invariant cylindrical algebraic decomposition
Journal of Symbolic Computation, 2016Co-Authors: Russell Bradford, James H Davenport, Matthew England, Scott Mccallum, David WilsonAbstract:When using cylindrical algebraic decomposition (CAD) to solve a problem with respect to a set of polynomials, it is likely not the signs of those polynomials that are of paramount importance but rather the Truth values of certain quantifier free formulae involving them. This observation motivates our article and definition of a Truth Table Invariant CAD (TTICAD).In ISSAC 2013 the current authors presented an algorithm that can efficiently and directly construct a TTICAD for a list of formulae in which each has an equational constraint. This was achieved by generalising McCallum's theory of reduced projection operators. In this paper we present an extended version of our theory which can be applied to an arbitrary list of formulae, achieving savings if at least one has an equational constraint. We also explain how the theory of reduced projection operators can allow for further improvements to the lifting phase of CAD algorithms, even in the context of a single equational constraint.The algorithm is implemented fully in Maple and we present both promising results from experimentation and a complexity analysis showing the benefits of our contributions.
-
dataset supporting the paper Truth Table invariant cylindrical algebraic decomposition
2015Co-Authors: Russell Bradford, James H Davenport, Matthew England, Scott Mccallum, David WilsonAbstract:The files in this data set support the following paper: ########################################################################################## Truth Table invariant cylindrical algebraic decomposition. Russel Bradford, James H. Davenport, Matthew England, Scott McCallum and David Wilson. http://opus.bath.ac.uk/38146/ ########################################################################################## Please find included the following: ############################## 1a) A Maple worksheet: Section1to7-Maple.mw 1b) A pdf printout of the worksheet: Section1to7-Maple.pdf 1c) A Maple Library file: ProjectionCAD.mpl These files concern the Maple results for the worked examples throughout Sections 1-7 of the paper. To run the Maple worksheet you will need a copy of the commercial computer algebra software Maple. This is currently available from: http://www.maplesoft.com/products/maple/ The examples were run in Maple 16 (released Spring 2012). It is likely that the same results would be obtained in Maple 17, 18, 2015 and future versions, but this cannot be guaranteed. An additional code package, developed at the University of Bath, is required. To use it we need to read the Maple Library file within Maple as follows: >>> read("ProjectionCAD.mpl"): >>> with(ProjectionCAD): More details on this Maple package are available in the technical report at http://opus.bath.ac.uk/43911/ and in the following publication: M. England, D. Wilson, R. Bradford and J.H. Davenport. Using the Regular Chains Library to build cylindrical algebraic decompositions by projecting and lifting. Proc ICMS 2014 (LNCS 8593). DOI: 10.1007/978-3-662-44199-2_69 If you do not have a copy of Maple you can still read the pdf printout of the worksheet. ############################## 2) A zipped directory WorkedExamples-Qepcad.zip This directory also concerns the worked examples from Sections 1-7 of the paper, this time when studied with Qepcad-B. Qepcad-B is a free piece of software for Linux which can be obtained from: http://www.usna.edu/CS/qepcadweb/B/QEPCAD.html All the files in the zipped directory end in either "-in.txt" or "-out.txt". The former give input for Qepcad and the latter record output. Hence readers without access to Qepcad (e.g. on a Windows system) can still observe the output in the latter files. To verify the output readers should use the following bash command to run a Qepcad input file "Ex-in.txt" and record the output in "Ex-out.txt". >>> qepcad +N500000000 +L200000 Ex-out.txt Windows users without Linux access can still read the existing output files in the folder. ############################## 3a) The text file: Section82-ExampleSet.txt 3b) A Maple worksheet: Section82-ExampleSet.mw 3b) A pdf printout of the worksheet: Section82-ExampleSet.pdf The textfile defines the example set which is the subject of the experiments in Section 8.2, whose results were summarised in Table 2. Within the file the 29 examples are defined in the following syntax: (a) First a line starting with "#" giving the full example name followed in brackets by the shortened name used in Table 2. (b) Then a second line in which the example is defined as a list of two sublists: i) The first sublist defines the polynomials used. They are sorted into further lists, one for each formulae in the example. Each of these has two entries: --- The first is either a polynomial defining an equational constraint (EC); a list of polynomials defining multiple ECs; or an empty list (signalling no ECs). --- The second is a list of any non ECs. ii) The second sublist is the variable ordering from highest (eliminate first in projection) to lowest. Note that Maple algorithms use this order by Qepcad the reverse. This is the syntax used by the TTICAD algorithm that is the subject of the paper. The text file doubles as a Maple function definition. When read into Maple the command GenerateInput is defined which can provide the input in formats suiTable for the three Maple algorithms tested. An example is given in the Maple worksheet / pdf. We note that the timings reported in the paper were from running Maple in command line mode. See also the notes for files (1) above. The same example set was tested in Qepcad. Here explicit ECs for a parent formula were entered in dynamically as products of the individual sub-formulae ECs, in cases where an explicit EC exists. See also Qepcad notes for file (2) above. Finally, the example set was also tested in Mathematica. Mathematica's CAD command does not return cell counts - these were obtained upon request to a Mathematica developer. Hence they are not recreaTable using the information here (something outside the control of the present authors). ############################## 4a) A Maple worksheet: Section83-Maple.mw 4b) A pdf printout of the worksheet: Section83-Maple.pdf This shows how the numbers in Table 3 from Maple were obtained. See also notes for files (1) above. ############################## 5a) A zipped directory Section83-Qepcad.zipped This shows how the numbers in Table 3 from Qepcad were obtained. See also notes for file (2) above.
-
problem formulation for Truth Table invariant cylindrical algebraic decomposition by incremental triangular decomposition
arXiv: Symbolic Computation, 2014Co-Authors: Matthew England, Russell Bradford, James H Davenport, Changbo Chen, Marc Moreno Maza, David WilsonAbstract:Cylindrical algebraic decompositions (CADs) are a key tool for solving problems in real algebraic geometry and beyond. We recently presented a new CAD algorithm combining two advances: Truth-Table invariance, making the CAD invariant with respect to the Truth of logical formulae rather than the signs of polynomials; and CAD construction by regular chains technology, where first a complex decomposition is constructed by refining a tree incrementally by constraint. We here consider how best to formulate problems for input to this algorithm. We focus on a choice (not relevant for other CAD algorithms) about the order in which constraints are presented. We develop new heuristics to help make this choice and thus allow the best use of the algorithm in practice. We also consider other choices of problem formulation for CAD, as discussed in CICM 2013, revisiting these in the context of the new algorithm.
-
Truth Table invariant cylindrical algebraic decomposition by regular chains
arXiv: Symbolic Computation, 2014Co-Authors: Russell Bradford, James H Davenport, Matthew England, Changbo Chen, Marc Moreno Maza, David WilsonAbstract:A new algorithm to compute cylindrical algebraic decompositions (CADs) is presented, building on two recent advances. Firstly, the output is Truth Table invariant (a TTICAD) meaning given formulae have constant Truth value on each cell of the decomposition. Secondly, the computation uses regular chains theory to first build a cylindrical decomposition of complex space (CCD) incrementally by polynomial. Significant modification of the regular chains technology was used to achieve the more sophisticated invariance criteria. Experimental results on an implementation in the RegularChains Library for Maple verify that combining these advances gives an algorithm superior to its individual components and competitive with the state of the art.
