Welcome to TiddlyWiki created by Jeremy Ruston, Copyright © 2007 UnaMesa Association
Marks papers related to Cork Constraint Computation Centre.
This tag marks Computer Science stuff.
* CSPs with one or more sets of unbounded variables.
* Layered CSPs.
* Taxonomies and hierarchies.
Data Exchange, existential fragments.
CSP + variable creation.
Open CSP?
!!Applications of PartnerUnits, what can we model with that?
!!NP-completeness of PUDP(2, 3)
No apparent correspondence with either 1-in-3SAT, NValue, or anything else.
PUDP(c, *) with $n$ vertices would solvable by dynamic programming in time $O(n^c)$ if we could determine whether a bag violates the number of partners locally.
!!Can we formalize Generative CSPs?
!!Resource Constraints (transfer report)
!!!Literature
!!!Flow networks
!!!Tractable classes of NValue
Not obvious from the GCC paper.
Papers related to Dynamic CSPs as defined in MittalFalkenhainer1990. The name is ambiguous, and GelleFaltings2003 rename such problems to Conditional CSPs.
!! Summary
*Universal and preuniversal solutions
*Cores
**Efficient for tgds in $\Sigma_{st}$ and egds in $\Sigma_t$
**Efficient for weakly acyclic tgds in $\Sigma_t$
Syntax $\forall \vec{x} \forall \vec{y}(C\vec{x}\vec{y} \rightarrow T\vec{x})$ with $C$ a conjunction of atoms and $T$ atomic.
[[Threads]]
[[ReadPaper]]
[[ResNotes]]
The writings of Edsger W. Dijkstra, availible at the [[ EWD archive | http://www.cs.utexas.edu/users/EWD/ ]].
!The complexity class $\Theta^p_2$: Recent results and applications in AI and modal logic
Paper reviews the class $\Theta^p_2$ and presents several problems that are complete for this class.
!!Basic characterization
The class $\Theta^p_2 = P^{NP}[O(\log n)]$ is the class of problems solvable in polynomial time with $O(\log n)$ calls to an NP oracle. Among others, it coincides with $L^{NP}$. It is not known whether $\Delta^2_p = \Theta^2_p$ implies $P = NP$ or even the collapse of PH.
We can characterize this class by looking at the NP oracle quieries as a DAG. Every node contains an instance of a problem in NP (a query, parametrized), and the node can be answered as soon as the nodes at the incoming edges have been answered. Using this concept, we can define the problem $DAGS(SAT)$, which asks whether we can satisfy a SAT instance that depends on other SAT instances (via special variables) with the dependencies forming a DAG. This problem is complete for $\Theta^2_p$.
Now we can define $DAGS(NP)$ as the class of problems that can be reduced to $DAGS(SAT)$ in polynomial time. These problems are precisely the problems in $\Delta^2_p$, therefore $\Delta^2_p = DAGS(NP)$.
We can also introduce a restriction on the DAGs. Let $DAGS_k(SAT)$ be the set of $DAGS(SAT)$ instances with depth at most $k$, and likewise $DAGS_k(NP)$ the instances of $DAGS(NP)$ that can be reduced to $DAGS_k(SAT)$ in polynomial time. All these problems are hard for $\Theta^2_p$, and $\bigcup_k DAGS_k(NP) = \Theta^2_p$. The width of the DAG doesn't matter as parallelism adds no computational power in this case.
We can also consider $TREES(SAT)$ as $DAGS(SAT)$ restricted to trees. This problem is complete for $\Theta^2_p$, and in fact it can be shown that $TREES(NP) = \Theta^2_p$, so we get another characterization.
!!Circuits
The paper presents a characterization of $\Theta^p_2$ via the circuit classes $AC^i$ and $NC^i$ relativized by an NP oracle. In particular,$AC^k(NP) = NC^{k+1}(NP)$ and $AC^0(NP) = \Theta^p_2 = NC^1(NP)$.
!!Complete problems
Several complete problems for $\Theta^p_2$ are presented, e.g. theory revision under a particular operator and the null value problem for disjunctive databases. Also, problems from logic programming semantics and default logic are described, as well as problems in modal logic.
Finally, the paper gives a short logical characterization of $\Theta^p_2$.
!Open constraint satisfaction
Paper deals with solving an ''open'' CSP, i.e. one where you can retrieve more values for the variables if you get stuck. More formally, we can for every variable and for every constraint invoke a "more" predicate that either returns more data (values if it's a variable, tuples if it's a constraint) or "no data". Constraints are given by the tuples they allow.
Every invocation of the "more" predicate gives rise to a new CSP, and we write $P(i) \prec P(j)$ when $P(j)$ was obtained by calling "more" on $P(i)$. The solutions grow along this order: If $P(i) \prec P(j)$, then the solutions of $P(i)$ are a subset of the ones for $P(j)$.
Another way of looking at OCSP is that we are combining several CSPs into one, where you can choose what to satisfy (we liberalize). To disjunctively combine two CSPs, we
*Take the union of their variables
*For every variable, take all the values found in either CSP
*Likewise for every constraint, take every tuple found in either CSP.
Such combination breaks pruning techniques, as we can remove values that might become allowed after combination, or remove tuples that were redundant before combination, but not after.(All this applies to OCSPs as well) To rectify this, the authors try, but fail, to define a syntactic condition for when a CSP is safe to combine.
The authors claim that constraint propagation and other interesting techniques break, and present algorithms for OCSPs. The obvious one is brute force, where we gather all information and then solve the resulting CSP.
The other tries to find variables that are part of unsolvable subproblems, and invoke "more" on these. Such variables are found by backtracking search — if we fail and have explored variables $x_1,\ldots,x_k$, then there exists an assignment to $x_1,\ldots,x_{k-1}$, but no assignment to $x_1,\ldots,x_k$; thus $x_k$ is part of every unsolvable subproblem involving these variables.
The set of unsolvable subproblems of an OCSP decreases monotonically over the $\prec$ relation (obvious), and restarting the search ought to be done by first looking at assignments with the new values (again, obvious).
The authors test their algorithms on randomly generated problems (the randomness is of unknown provenance), and find that they all perform as expected.
!Skolem machines and geometric logic
and
!Query completeness of Skolem machine computations
Two papers that present the notion of a Skolem machine, and show soundness and completeness of this computational framework wrt. coherent logic (CL). A skolem machine is similar to Warren's abstract machine (WAM) for prolog, but uses CL formulae as rules. The machine can be seen as a representation of the ground CL calculus.
As we are doing query answering, we need to tweak the notions of soundness and completeness. First, a query has the form $\exists \vec{x}(C_1 \vee \ldots \vee C_n)$ with every C an atomic conjunction. Given a query Q and a set of rules R, we have soundness if, when the machine halts successfully with each tape satisfying $C_i$ for some $i$, then $R \models Q$. Completeness is of course the converse.
A skolem machine decomposes (rewrites) nicely into prolog, with good efficiency.
/***
|''Name:''|ForEachTiddlerPlugin|
|''Version:''|1.0.8 (2007-04-12)|
|''Source:''|http://tiddlywiki.abego-software.de/#ForEachTiddlerPlugin|
|''Author:''|UdoBorkowski (ub [at] abego-software [dot] de)|
|''Licence:''|[[BSD open source license (abego Software)|http://www.abego-software.de/legal/apl-v10.html]]|
|''Copyright:''|© 2005-2007 [[abego Software|http://www.abego-software.de]]|
|''TiddlyWiki:''|1.2.38+, 2.0|
|''Browser:''|Firefox 1.0.4+; Firefox 1.5; InternetExplorer 6.0|
!Description
Create customizable lists, tables etc. for your selections of tiddlers. Specify the tiddlers to include and their order through a powerful language.
''Syntax:''
|>|{{{<<}}}''forEachTiddler'' [''in'' //tiddlyWikiPath//] [''where'' //whereCondition//] [''sortBy'' //sortExpression// [''ascending'' //or// ''descending'']] [''script'' //scriptText//] [//action// [//actionParameters//]]{{{>>}}}|
|//tiddlyWikiPath//|The filepath to the TiddlyWiki the macro should work on. When missing the current TiddlyWiki is used.|
|//whereCondition//|(quoted) JavaScript boolean expression. May refer to the build-in variables {{{tiddler}}} and {{{context}}}.|
|//sortExpression//|(quoted) JavaScript expression returning "comparable" objects (using '{{{<}}}','{{{>}}}','{{{==}}}'. May refer to the build-in variables {{{tiddler}}} and {{{context}}}.|
|//scriptText//|(quoted) JavaScript text. Typically defines JavaScript functions that are called by the various JavaScript expressions (whereClause, sortClause, action arguments,...)|
|//action//|The action that should be performed on every selected tiddler, in the given order. By default the actions [[addToList|AddToListAction]] and [[write|WriteAction]] are supported. When no action is specified [[addToList|AddToListAction]] is used.|
|//actionParameters//|(action specific) parameters the action may refer while processing the tiddlers (see action descriptions for details). <<tiddler [[JavaScript in actionParameters]]>>|
|>|~~Syntax formatting: Keywords in ''bold'', optional parts in [...]. 'or' means that exactly one of the two alternatives must exist.~~|
See details see [[ForEachTiddlerMacro]] and [[ForEachTiddlerExamples]].
!Revision history
* v1.0.8 (2007-04-12)
** Adapted to latest TiddlyWiki 2.2 Beta importTiddlyWiki API (introduced with changeset 2004). TiddlyWiki 2.2 Beta builds prior to changeset 2004 are no longer supported (but TiddlyWiki 2.1 and earlier, of cause)
* v1.0.7 (2007-03-28)
** Also support "pre" formatted TiddlyWikis (introduced with TW 2.2) (when using "in" clause to work on external tiddlers)
* v1.0.6 (2006-09-16)
** Context provides "viewerTiddler", i.e. the tiddler used to view the macro. Most times this is equal to the "inTiddler", but when using the "tiddler" macro both may be different.
** Support "begin", "end" and "none" expressions in "write" action
* v1.0.5 (2006-02-05)
** Pass tiddler containing the macro with wikify, context object also holds reference to tiddler containing the macro ("inTiddler"). Thanks to SimonBaird.
** Support Firefox 1.5.0.1
** Internal
*** Make "JSLint" conform
*** "Only install once"
* v1.0.4 (2006-01-06)
** Support TiddlyWiki 2.0
* v1.0.3 (2005-12-22)
** Features:
*** Write output to a file supports multi-byte environments (Thanks to Bram Chen)
*** Provide API to access the forEachTiddler functionality directly through JavaScript (see getTiddlers and performMacro)
** Enhancements:
*** Improved error messages on InternetExplorer.
* v1.0.2 (2005-12-10)
** Features:
*** context object also holds reference to store (TiddlyWiki)
** Fixed Bugs:
*** ForEachTiddler 1.0.1 has broken support on win32 Opera 8.51 (Thanks to BrunoSabin for reporting)
* v1.0.1 (2005-12-08)
** Features:
*** Access tiddlers stored in separated TiddlyWikis through the "in" option. I.e. you are no longer limited to only work on the "current TiddlyWiki".
*** Write output to an external file using the "toFile" option of the "write" action. With this option you may write your customized tiddler exports.
*** Use the "script" section to define "helper" JavaScript functions etc. to be used in the various JavaScript expressions (whereClause, sortClause, action arguments,...).
*** Access and store context information for the current forEachTiddler invocation (through the build-in "context" object) .
*** Improved script evaluation (for where/sort clause and write scripts).
* v1.0.0 (2005-11-20)
** initial version
!Code
***/
//{{{
//============================================================================
//============================================================================
// ForEachTiddlerPlugin
//============================================================================
//============================================================================
// Only install once
if (!version.extensions.ForEachTiddlerPlugin) {
if (!window.abego) window.abego = {};
version.extensions.ForEachTiddlerPlugin = {
major: 1, minor: 0, revision: 8,
date: new Date(2007,3,12),
source: "http://tiddlywiki.abego-software.de/#ForEachTiddlerPlugin",
licence: "[[BSD open source license (abego Software)|http://www.abego-software.de/legal/apl-v10.html]]",
copyright: "Copyright (c) abego Software GmbH, 2005-2007 (www.abego-software.de)"
};
// For backward compatibility with TW 1.2.x
//
if (!TiddlyWiki.prototype.forEachTiddler) {
TiddlyWiki.prototype.forEachTiddler = function(callback) {
for(var t in this.tiddlers) {
callback.call(this,t,this.tiddlers[t]);
}
};
}
//============================================================================
// forEachTiddler Macro
//============================================================================
version.extensions.forEachTiddler = {
major: 1, minor: 0, revision: 8, date: new Date(2007,3,12), provider: "http://tiddlywiki.abego-software.de"};
// ---------------------------------------------------------------------------
// Configurations and constants
// ---------------------------------------------------------------------------
config.macros.forEachTiddler = {
// Standard Properties
label: "forEachTiddler",
prompt: "Perform actions on a (sorted) selection of tiddlers",
// actions
actions: {
addToList: {},
write: {}
}
};
// ---------------------------------------------------------------------------
// The forEachTiddler Macro Handler
// ---------------------------------------------------------------------------
config.macros.forEachTiddler.getContainingTiddler = function(e) {
while(e && !hasClass(e,"tiddler"))
e = e.parentNode;
var title = e ? e.getAttribute("tiddler") : null;
return title ? store.getTiddler(title) : null;
};
config.macros.forEachTiddler.handler = function(place,macroName,params,wikifier,paramString,tiddler) {
// config.macros.forEachTiddler.traceMacroCall(place,macroName,params,wikifier,paramString,tiddler);
if (!tiddler) tiddler = config.macros.forEachTiddler.getContainingTiddler(place);
// --- Parsing ------------------------------------------
var i = 0; // index running over the params
// Parse the "in" clause
var tiddlyWikiPath = undefined;
if ((i < params.length) && params[i] == "in") {
i++;
if (i >= params.length) {
this.handleError(place, "TiddlyWiki path expected behind 'in'.");
return;
}
tiddlyWikiPath = this.paramEncode((i < params.length) ? params[i] : "");
i++;
}
// Parse the where clause
var whereClause ="true";
if ((i < params.length) && params[i] == "where") {
i++;
whereClause = this.paramEncode((i < params.length) ? params[i] : "");
i++;
}
// Parse the sort stuff
var sortClause = null;
var sortAscending = true;
if ((i < params.length) && params[i] == "sortBy") {
i++;
if (i >= params.length) {
this.handleError(place, "sortClause missing behind 'sortBy'.");
return;
}
sortClause = this.paramEncode(params[i]);
i++;
if ((i < params.length) && (params[i] == "ascending" || params[i] == "descending")) {
sortAscending = params[i] == "ascending";
i++;
}
}
// Parse the script
var scriptText = null;
if ((i < params.length) && params[i] == "script") {
i++;
scriptText = this.paramEncode((i < params.length) ? params[i] : "");
i++;
}
// Parse the action.
// When we are already at the end use the default action
var actionName = "addToList";
if (i < params.length) {
if (!config.macros.forEachTiddler.actions[params[i]]) {
this.handleError(place, "Unknown action '"+params[i]+"'.");
return;
} else {
actionName = params[i];
i++;
}
}
// Get the action parameter
// (the parsing is done inside the individual action implementation.)
var actionParameter = params.slice(i);
// --- Processing ------------------------------------------
try {
this.performMacro({
place: place,
inTiddler: tiddler,
whereClause: whereClause,
sortClause: sortClause,
sortAscending: sortAscending,
actionName: actionName,
actionParameter: actionParameter,
scriptText: scriptText,
tiddlyWikiPath: tiddlyWikiPath});
} catch (e) {
this.handleError(place, e);
}
};
// Returns an object with properties "tiddlers" and "context".
// tiddlers holds the (sorted) tiddlers selected by the parameter,
// context the context of the execution of the macro.
//
// The action is not yet performed.
//
// @parameter see performMacro
//
config.macros.forEachTiddler.getTiddlersAndContext = function(parameter) {
var context = config.macros.forEachTiddler.createContext(parameter.place, parameter.whereClause, parameter.sortClause, parameter.sortAscending, parameter.actionName, parameter.actionParameter, parameter.scriptText, parameter.tiddlyWikiPath, parameter.inTiddler);
var tiddlyWiki = parameter.tiddlyWikiPath ? this.loadTiddlyWiki(parameter.tiddlyWikiPath) : store;
context["tiddlyWiki"] = tiddlyWiki;
// Get the tiddlers, as defined by the whereClause
var tiddlers = this.findTiddlers(parameter.whereClause, context, tiddlyWiki);
context["tiddlers"] = tiddlers;
// Sort the tiddlers, when sorting is required.
if (parameter.sortClause) {
this.sortTiddlers(tiddlers, parameter.sortClause, parameter.sortAscending, context);
}
return {tiddlers: tiddlers, context: context};
};
// Returns the (sorted) tiddlers selected by the parameter.
//
// The action is not yet performed.
//
// @parameter see performMacro
//
config.macros.forEachTiddler.getTiddlers = function(parameter) {
return this.getTiddlersAndContext(parameter).tiddlers;
};
// Performs the macros with the given parameter.
//
// @param parameter holds the parameter of the macro as separate properties.
// The following properties are supported:
//
// place
// whereClause
// sortClause
// sortAscending
// actionName
// actionParameter
// scriptText
// tiddlyWikiPath
//
// All properties are optional.
// For most actions the place property must be defined.
//
config.macros.forEachTiddler.performMacro = function(parameter) {
var tiddlersAndContext = this.getTiddlersAndContext(parameter);
// Perform the action
var actionName = parameter.actionName ? parameter.actionName : "addToList";
var action = config.macros.forEachTiddler.actions[actionName];
if (!action) {
this.handleError(parameter.place, "Unknown action '"+actionName+"'.");
return;
}
var actionHandler = action.handler;
actionHandler(parameter.place, tiddlersAndContext.tiddlers, parameter.actionParameter, tiddlersAndContext.context);
};
// ---------------------------------------------------------------------------
// The actions
// ---------------------------------------------------------------------------
// Internal.
//
// --- The addToList Action -----------------------------------------------
//
config.macros.forEachTiddler.actions.addToList.handler = function(place, tiddlers, parameter, context) {
// Parse the parameter
var p = 0;
// Check for extra parameters
if (parameter.length > p) {
config.macros.forEachTiddler.createExtraParameterErrorElement(place, "addToList", parameter, p);
return;
}
// Perform the action.
var list = document.createElement("ul");
place.appendChild(list);
for (var i = 0; i < tiddlers.length; i++) {
var tiddler = tiddlers[i];
var listItem = document.createElement("li");
list.appendChild(listItem);
createTiddlyLink(listItem, tiddler.title, true);
}
};
abego.parseNamedParameter = function(name, parameter, i) {
var beginExpression = null;
if ((i < parameter.length) && parameter[i] == name) {
i++;
if (i >= parameter.length) {
throw "Missing text behind '%0'".format([name]);
}
return config.macros.forEachTiddler.paramEncode(parameter[i]);
}
return null;
}
// Internal.
//
// --- The write Action ---------------------------------------------------
//
config.macros.forEachTiddler.actions.write.handler = function(place, tiddlers, parameter, context) {
// Parse the parameter
var p = 0;
if (p >= parameter.length) {
this.handleError(place, "Missing expression behind 'write'.");
return;
}
var textExpression = config.macros.forEachTiddler.paramEncode(parameter[p]);
p++;
// Parse the "begin" option
var beginExpression = abego.parseNamedParameter("begin", parameter, p);
if (beginExpression !== null)
p += 2;
var endExpression = abego.parseNamedParameter("end", parameter, p);
if (endExpression !== null)
p += 2;
var noneExpression = abego.parseNamedParameter("none", parameter, p);
if (noneExpression !== null)
p += 2;
// Parse the "toFile" option
var filename = null;
var lineSeparator = undefined;
if ((p < parameter.length) && parameter[p] == "toFile") {
p++;
if (p >= parameter.length) {
this.handleError(place, "Filename expected behind 'toFile' of 'write' action.");
return;
}
filename = config.macros.forEachTiddler.getLocalPath(config.macros.forEachTiddler.paramEncode(parameter[p]));
p++;
if ((p < parameter.length) && parameter[p] == "withLineSeparator") {
p++;
if (p >= parameter.length) {
this.handleError(place, "Line separator text expected behind 'withLineSeparator' of 'write' action.");
return;
}
lineSeparator = config.macros.forEachTiddler.paramEncode(parameter[p]);
p++;
}
}
// Check for extra parameters
if (parameter.length > p) {
config.macros.forEachTiddler.createExtraParameterErrorElement(place, "write", parameter, p);
return;
}
// Perform the action.
var func = config.macros.forEachTiddler.getEvalTiddlerFunction(textExpression, context);
var count = tiddlers.length;
var text = "";
if (count > 0 && beginExpression)
text += config.macros.forEachTiddler.getEvalTiddlerFunction(beginExpression, context)(undefined, context, count, undefined);
for (var i = 0; i < count; i++) {
var tiddler = tiddlers[i];
text += func(tiddler, context, count, i);
}
if (count > 0 && endExpression)
text += config.macros.forEachTiddler.getEvalTiddlerFunction(endExpression, context)(undefined, context, count, undefined);
if (count == 0 && noneExpression)
text += config.macros.forEachTiddler.getEvalTiddlerFunction(noneExpression, context)(undefined, context, count, undefined);
if (filename) {
if (lineSeparator !== undefined) {
lineSeparator = lineSeparator.replace(/\\n/mg, "\n").replace(/\\r/mg, "\r");
text = text.replace(/\n/mg,lineSeparator);
}
saveFile(filename, convertUnicodeToUTF8(text));
} else {
var wrapper = createTiddlyElement(place, "span");
wikify(text, wrapper, null/* highlightRegExp */, context.inTiddler);
}
};
// ---------------------------------------------------------------------------
// Helpers
// ---------------------------------------------------------------------------
// Internal.
//
config.macros.forEachTiddler.createContext = function(placeParam, whereClauseParam, sortClauseParam, sortAscendingParam, actionNameParam, actionParameterParam, scriptText, tiddlyWikiPathParam, inTiddlerParam) {
return {
place : placeParam,
whereClause : whereClauseParam,
sortClause : sortClauseParam,
sortAscending : sortAscendingParam,
script : scriptText,
actionName : actionNameParam,
actionParameter : actionParameterParam,
tiddlyWikiPath : tiddlyWikiPathParam,
inTiddler : inTiddlerParam, // the tiddler containing the <<forEachTiddler ...>> macro call.
viewerTiddler : config.macros.forEachTiddler.getContainingTiddler(placeParam) // the tiddler showing the forEachTiddler result
};
};
// Internal.
//
// Returns a TiddlyWiki with the tiddlers loaded from the TiddlyWiki of
// the given path.
//
config.macros.forEachTiddler.loadTiddlyWiki = function(path, idPrefix) {
if (!idPrefix) {
idPrefix = "store";
}
var lenPrefix = idPrefix.length;
// Read the content of the given file
var content = loadFile(this.getLocalPath(path));
if(content === null) {
throw "TiddlyWiki '"+path+"' not found.";
}
var tiddlyWiki = new TiddlyWiki();
// Starting with TW 2.2 there is a helper function to import the tiddlers
if (tiddlyWiki.importTiddlyWiki) {
if (!tiddlyWiki.importTiddlyWiki(content))
throw "File '"+path+"' is not a TiddlyWiki.";
tiddlyWiki.dirty = false;
return tiddlyWiki;
}
// The legacy code, for TW < 2.2
// Locate the storeArea div's
var posOpeningDiv = content.indexOf(startSaveArea);
var posClosingDiv = content.lastIndexOf(endSaveArea);
if((posOpeningDiv == -1) || (posClosingDiv == -1)) {
throw "File '"+path+"' is not a TiddlyWiki.";
}
var storageText = content.substr(posOpeningDiv + startSaveArea.length, posClosingDiv);
// Create a "div" element that contains the storage text
var myStorageDiv = document.createElement("div");
myStorageDiv.innerHTML = storageText;
myStorageDiv.normalize();
// Create all tiddlers in a new TiddlyWiki
// (following code is modified copy of TiddlyWiki.prototype.loadFromDiv)
var store = myStorageDiv.childNodes;
for(var t = 0; t < store.length; t++) {
var e = store[t];
var title = null;
if(e.getAttribute)
title = e.getAttribute("tiddler");
if(!title && e.id && e.id.substr(0,lenPrefix) == idPrefix)
title = e.id.substr(lenPrefix);
if(title && title !== "") {
var tiddler = tiddlyWiki.createTiddler(title);
tiddler.loadFromDiv(e,title);
}
}
tiddlyWiki.dirty = false;
return tiddlyWiki;
};
// Internal.
//
// Returns a function that has a function body returning the given javaScriptExpression.
// The function has the parameters:
//
// (tiddler, context, count, index)
//
config.macros.forEachTiddler.getEvalTiddlerFunction = function (javaScriptExpression, context) {
var script = context["script"];
var functionText = "var theFunction = function(tiddler, context, count, index) { return "+javaScriptExpression+"}";
var fullText = (script ? script+";" : "")+functionText+";theFunction;";
return eval(fullText);
};
// Internal.
//
config.macros.forEachTiddler.findTiddlers = function(whereClause, context, tiddlyWiki) {
var result = [];
var func = config.macros.forEachTiddler.getEvalTiddlerFunction(whereClause, context);
tiddlyWiki.forEachTiddler(function(title,tiddler) {
if (func(tiddler, context, undefined, undefined)) {
result.push(tiddler);
}
});
return result;
};
// Internal.
//
config.macros.forEachTiddler.createExtraParameterErrorElement = function(place, actionName, parameter, firstUnusedIndex) {
var message = "Extra parameter behind '"+actionName+"':";
for (var i = firstUnusedIndex; i < parameter.length; i++) {
message += " "+parameter[i];
}
this.handleError(place, message);
};
// Internal.
//
config.macros.forEachTiddler.sortAscending = function(tiddlerA, tiddlerB) {
var result =
(tiddlerA.forEachTiddlerSortValue == tiddlerB.forEachTiddlerSortValue)
? 0
: (tiddlerA.forEachTiddlerSortValue < tiddlerB.forEachTiddlerSortValue)
? -1
: +1;
return result;
};
// Internal.
//
config.macros.forEachTiddler.sortDescending = function(tiddlerA, tiddlerB) {
var result =
(tiddlerA.forEachTiddlerSortValue == tiddlerB.forEachTiddlerSortValue)
? 0
: (tiddlerA.forEachTiddlerSortValue < tiddlerB.forEachTiddlerSortValue)
? +1
: -1;
return result;
};
// Internal.
//
config.macros.forEachTiddler.sortTiddlers = function(tiddlers, sortClause, ascending, context) {
// To avoid evaluating the sortClause whenever two items are compared
// we pre-calculate the sortValue for every item in the array and store it in a
// temporary property ("forEachTiddlerSortValue") of the tiddlers.
var func = config.macros.forEachTiddler.getEvalTiddlerFunction(sortClause, context);
var count = tiddlers.length;
var i;
for (i = 0; i < count; i++) {
var tiddler = tiddlers[i];
tiddler.forEachTiddlerSortValue = func(tiddler,context, undefined, undefined);
}
// Do the sorting
tiddlers.sort(ascending ? this.sortAscending : this.sortDescending);
// Delete the temporary property that holds the sortValue.
for (i = 0; i < tiddlers.length; i++) {
delete tiddlers[i].forEachTiddlerSortValue;
}
};
// Internal.
//
config.macros.forEachTiddler.trace = function(message) {
displayMessage(message);
};
// Internal.
//
config.macros.forEachTiddler.traceMacroCall = function(place,macroName,params) {
var message ="<<"+macroName;
for (var i = 0; i < params.length; i++) {
message += " "+params[i];
}
message += ">>";
displayMessage(message);
};
// Internal.
//
// Creates an element that holds an error message
//
config.macros.forEachTiddler.createErrorElement = function(place, exception) {
var message = (exception.description) ? exception.description : exception.toString();
return createTiddlyElement(place,"span",null,"forEachTiddlerError","<<forEachTiddler ...>>: "+message);
};
// Internal.
//
// @param place [may be null]
//
config.macros.forEachTiddler.handleError = function(place, exception) {
if (place) {
this.createErrorElement(place, exception);
} else {
throw exception;
}
};
// Internal.
//
// Encodes the given string.
//
// Replaces
// "$))" to ">>"
// "$)" to ">"
//
config.macros.forEachTiddler.paramEncode = function(s) {
var reGTGT = new RegExp("\\$\\)\\)","mg");
var reGT = new RegExp("\\$\\)","mg");
return s.replace(reGTGT, ">>").replace(reGT, ">");
};
// Internal.
//
// Returns the given original path (that is a file path, starting with "file:")
// as a path to a local file, in the systems native file format.
//
// Location information in the originalPath (i.e. the "#" and stuff following)
// is stripped.
//
config.macros.forEachTiddler.getLocalPath = function(originalPath) {
// Remove any location part of the URL
var hashPos = originalPath.indexOf("#");
if(hashPos != -1)
originalPath = originalPath.substr(0,hashPos);
// Convert to a native file format assuming
// "file:///x:/path/path/path..." - pc local file --> "x:\path\path\path..."
// "file://///server/share/path/path/path..." - FireFox pc network file --> "\\server\share\path\path\path..."
// "file:///path/path/path..." - mac/unix local file --> "/path/path/path..."
// "file://server/share/path/path/path..." - pc network file --> "\\server\share\path\path\path..."
var localPath;
if(originalPath.charAt(9) == ":") // pc local file
localPath = unescape(originalPath.substr(8)).replace(new RegExp("/","g"),"\\");
else if(originalPath.indexOf("file://///") === 0) // FireFox pc network file
localPath = "\\\\" + unescape(originalPath.substr(10)).replace(new RegExp("/","g"),"\\");
else if(originalPath.indexOf("file:///") === 0) // mac/unix local file
localPath = unescape(originalPath.substr(7));
else if(originalPath.indexOf("file:/") === 0) // mac/unix local file
localPath = unescape(originalPath.substr(5));
else // pc network file
localPath = "\\\\" + unescape(originalPath.substr(7)).replace(new RegExp("/","g"),"\\");
return localPath;
};
// ---------------------------------------------------------------------------
// Stylesheet Extensions (may be overridden by local StyleSheet)
// ---------------------------------------------------------------------------
//
setStylesheet(
".forEachTiddlerError{color: #ffffff;background-color: #880000;}",
"forEachTiddler");
//============================================================================
// End of forEachTiddler Macro
//============================================================================
//============================================================================
// String.startsWith Function
//============================================================================
//
// Returns true if the string starts with the given prefix, false otherwise.
//
version.extensions["String.startsWith"] = {major: 1, minor: 0, revision: 0, date: new Date(2005,11,20), provider: "http://tiddlywiki.abego-software.de"};
//
String.prototype.startsWith = function(prefix) {
var n = prefix.length;
return (this.length >= n) && (this.slice(0, n) == prefix);
};
//============================================================================
// String.endsWith Function
//============================================================================
//
// Returns true if the string ends with the given suffix, false otherwise.
//
version.extensions["String.endsWith"] = {major: 1, minor: 0, revision: 0, date: new Date(2005,11,20), provider: "http://tiddlywiki.abego-software.de"};
//
String.prototype.endsWith = function(suffix) {
var n = suffix.length;
return (this.length >= n) && (this.right(n) == suffix);
};
//============================================================================
// String.contains Function
//============================================================================
//
// Returns true when the string contains the given substring, false otherwise.
//
version.extensions["String.contains"] = {major: 1, minor: 0, revision: 0, date: new Date(2005,11,20), provider: "http://tiddlywiki.abego-software.de"};
//
String.prototype.contains = function(substring) {
return this.indexOf(substring) >= 0;
};
//============================================================================
// Array.indexOf Function
//============================================================================
//
// Returns the index of the first occurance of the given item in the array or
// -1 when no such item exists.
//
// @param item [may be null]
//
version.extensions["Array.indexOf"] = {major: 1, minor: 0, revision: 0, date: new Date(2005,11,20), provider: "http://tiddlywiki.abego-software.de"};
//
Array.prototype.indexOf = function(item) {
for (var i = 0; i < this.length; i++) {
if (this[i] == item) {
return i;
}
}
return -1;
};
//============================================================================
// Array.contains Function
//============================================================================
//
// Returns true when the array contains the given item, otherwise false.
//
// @param item [may be null]
//
version.extensions["Array.contains"] = {major: 1, minor: 0, revision: 0, date: new Date(2005,11,20), provider: "http://tiddlywiki.abego-software.de"};
//
Array.prototype.contains = function(item) {
return (this.indexOf(item) >= 0);
};
//============================================================================
// Array.containsAny Function
//============================================================================
//
// Returns true when the array contains at least one of the elements
// of the item. Otherwise (or when items contains no elements) false is returned.
//
version.extensions["Array.containsAny"] = {major: 1, minor: 0, revision: 0, date: new Date(2005,11,20), provider: "http://tiddlywiki.abego-software.de"};
//
Array.prototype.containsAny = function(items) {
for(var i = 0; i < items.length; i++) {
if (this.contains(items[i])) {
return true;
}
}
return false;
};
//============================================================================
// Array.containsAll Function
//============================================================================
//
// Returns true when the array contains all the items, otherwise false.
//
// When items is null false is returned (even if the array contains a null).
//
// @param items [may be null]
//
version.extensions["Array.containsAll"] = {major: 1, minor: 0, revision: 0, date: new Date(2005,11,20), provider: "http://tiddlywiki.abego-software.de"};
//
Array.prototype.containsAll = function(items) {
for(var i = 0; i < items.length; i++) {
if (!this.contains(items[i])) {
return false;
}
}
return true;
};
} // of "install only once"
// Used Globals (for JSLint) ==============
// ... DOM
/*global document */
// ... TiddlyWiki Core
/*global convertUnicodeToUTF8, createTiddlyElement, createTiddlyLink,
displayMessage, endSaveArea, hasClass, loadFile, saveFile,
startSaveArea, store, wikify */
//}}}
/***
!Licence and Copyright
Copyright (c) abego Software ~GmbH, 2005 ([[www.abego-software.de|http://www.abego-software.de]])
Redistribution and use in source and binary forms, with or without modification,
are permitted provided that the following conditions are met:
Redistributions of source code must retain the above copyright notice, this
list of conditions and the following disclaimer.
Redistributions in binary form must reproduce the above copyright notice, this
list of conditions and the following disclaimer in the documentation and/or other
materials provided with the distribution.
Neither the name of abego Software nor the names of its contributors may be
used to endorse or promote products derived from this software without specific
prior written permission.
THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY
EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT
SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH
DAMAGE.
***/
GCC as SAT via direct encoding?
Positive hyperres. derives new forbidden tuples. They are forbidden by a set of constraints.
!Solving mixed and conditional constraint satisfaction problems
Paper sets up a framework for handling DCSPs with both discrete and numerical variables; the authors name such problems Mixed Conditional CSPs. I, in turn, like the name DCSPs, so the topic of this paper are MDCSPs.
The definition of a Mixed DCSP mirrors that of a DCSP, except that we allow constraints to include numeric variables. A solution satisfies all constraints; a ''minimal'' solution is subset minimal.
The authors discuss the algorithm for solving DCSPs from MittalFalkenhainer1990, which backtracks to the next value of a variable. The concept of "next value" doesn't quite work for numerical variables with real domains, so the algorithm doesn't really fit.
Instead, the authors propose an algorithm that reduces an MDCSP to a set of mixed CSPs by analyzing the activation constraints for interdependence. A dependency digraph is constructed, starting from the initial variables, and cycles are lumped together to create a DAG. This DAG can be used to find a good order in which activation constraints are to be applied. For every activation constraint $C \Rightarrow_{RV} X$, we generate two sub-CSPs,
*one where $C$ must be satisfied and $X$ exists, and
*one where $\neg C$ must be satisfied and $X$ does not exist.
This is more complicated if several constraints formed a cycle (and are in one supernode) in our graph, but this only makes for fewer branches, not more.
We end up with a set of mixed CSPs such that every minimal solution to the original MDCSP is a solution to one of them. The time to generate all the CSPs is, not surprisingly, $O(2^{|C^A|})$ where $C^A$ are the activation constraints, ''even if there aren't any numeric variables''.
On the bright side, this allows the authors to leverage the full power of methods for dealing with numeric constraints. The rest of the paper presents a new way of enforcing consistency on mixed CSPs, i.e dealing with numeric constraints. They test their algorithm on some real-world problems, but point out that consistent evaluation is hard due to the lack of a standard definition of numeric constraints.
!Conditional constraint satisfaction: Logical foundations and complexity
Paper presents a logical characterization of DCSPs (CCSPs). The authors show how their formalism subsumes previous work, discuss the complexity of reasoning in it, and identify tractable problems.
The formalism presented is $\exists FO_{\rightarrow, \wedge, +}$, a fragment of FOL where sentences have the form $\exists\vec{v}(A_1 \wedge \cdots \wedge A_n \rightarrow \exists\vec{w}.B)$. (The paper gives a slightly different definition, but they should be equivalent.) Given a set $\phi$ of such rules and a database $D$ of facts that define the relations in $\phi$ (our constraints), the CCSP $(\phi, D)$ is to find a partial assignment $\theta$ such that $D \models \theta(\phi)$. In this setting, if an atom $A$ contains a variable not assigned by $\theta$ then $\theta(A) = \bot$, hence partial assignments are fine, and we can choose not to assign a variable on the left-hand side of an implication. We cannot, however, do the same with a right-hand side.
The authors then compare this formalism to standard DCSPs (MittalFalkenhainer1990) and $\exists FO_{\vee, \wedge, +}$. For DCSPs, the authors sketch a proof that their formalism is equivalent to DCSPs, by reductions in both directions. As for $\exists FO_{\wedge, +}$, the authors show that their formalism is more expressive, as $\rightarrow$ cannot be encoded using conjunction, since conjunction is monotonic (adding conjunctions can only forbid things, never allow them).
Turning to complexity, three problems are identified for a CCSP $(\psi, D)$ (aside from satisfiability, which is NP-complete),
*Checking, if $\theta$ a solution to $(\psi, D)$?
*Relevance, is a variable $x$ part of some solution for $(\psi, D)$?
*Necessity, is $x$ part of every solution for $(\psi, D)$?
and considered under different orderings of solutions, namely
*Subset minimality,
*Minimum cardinality, and
*Weighted cardinality, where every variable has a weight and we minimize the sum.
Results are given in a table, ranging from $P$ to $\Sigma_2P$, but mostly $NP$-complete or co-$NP$-complete.
Satisfiability remains NP-hard even if we restrict ourselves to acyclic instances, i.e instances with acyclic primal graphs. This is proven by reducing exact cover by 3-sets. Therefore, the authors define the notion of an ''implication graph'' to capture a tractable class of satisfiability problems in $\exists FO_{\rightarrow, \wedge, +}$. This graph charts activation dependencies between the variables as well as regular ones, and we can look at the treewidth of it. The authors prove that if the treewidth of this graph is bounded by a constant, satisfiability is in the class LOGCFL, hence tractable and highly parallelizable.
Labelling vertices of a tree with numbers 1 to n such that the absolute difference on the edges is 0 to n-1 and no repeats.
!Complete problems for deterministic polynomial time
Paper shows that several interesting problems are complete for $P$, in particular unit resolution (UNIT).
UNIT is proven to be in $P$ by exhibiting an algorithm that runs in time $|S|^2$ for a set of clauses $S$. The authors then prove that UNIT is complete for $P$ by exhibiting a logspace reduction from any language $L \in P$ by encoding any TM that decides $L$ in polynomial time as a HORNSAT problem. As we well know now (but didn't then), HORNSAT is decidable by unit resolution.
The authors then prove six other problems complete for $P$. The interesting (but obvious) bit for me is that HORNSAT is sufficient to characterize deterministic TMs, while SAT suffices for non-deterministic TMs. In other words, every DTM can be encoded as HORNSAT, and every NDTM as SAT. The intuitive explanation is that DTMs have transition functions, while NDTMs have transition relations.
!Symmetry breaking in a rack configuration problem
Paper introduces techniques for breaking symmetry in a simple configuration problem (the rack configuration problem). The problem is modeled as a classic CSP, as the number of components needed is known in advance. The authors discuss different ways of modeling this problem as a CSP, and how well these models allow for symmetry breaking.
Three different models are presented, namely the ''primal'', the ''dual'', and a third one that integrates the two. The primal model has simpler constraints, while the dual model breaks more of the symmetries. However, the overhead incurred by the extra constraints makes the dual model useful only when the symmetry breaking vastly reduces the search space.
The integrated model seems to perform better than both of these.
!!Bulatov and Marx
What happens if we have two CC constraints?
!!Hybrid
Not much known, acc. to Standa.
/***
|''Name:''|LoadRemoteFileThroughProxy (previous LoadRemoteFileHijack)|
|''Description:''|When the TiddlyWiki file is located on the web (view over http) the content of [[SiteProxy]] tiddler is added in front of the file url. If [[SiteProxy]] does not exist "/proxy/" is added. |
|''Version:''|1.1.0|
|''Date:''|mar 17, 2007|
|''Source:''|http://tiddlywiki.bidix.info/#LoadRemoteFileHijack|
|''Author:''|BidiX (BidiX (at) bidix (dot) info)|
|''License:''|[[BSD open source license|http://tiddlywiki.bidix.info/#%5B%5BBSD%20open%20source%20license%5D%5D ]]|
|''~CoreVersion:''|2.2.0|
***/
//{{{
version.extensions.LoadRemoteFileThroughProxy = {
major: 1, minor: 1, revision: 0,
date: new Date("mar 17, 2007"),
source: "http://tiddlywiki.bidix.info/#LoadRemoteFileThroughProxy"};
if (!window.bidix) window.bidix = {}; // bidix namespace
if (!bidix.core) bidix.core = {};
bidix.core.loadRemoteFile = loadRemoteFile;
loadRemoteFile = function(url,callback,params)
{
if ((document.location.toString().substr(0,4) == "http") && (url.substr(0,4) == "http")){
url = store.getTiddlerText("SiteProxy", "/proxy/") + url;
}
return bidix.core.loadRemoteFile(url,callback,params);
}
//}}}
What happens if $S$ and $T$ are instances over the same schema?
#Start with an instance $S$ containing key components (component = tuple)
#Chase $S$ with the contraints on the components in $S$ to obtain $S'$
#Loop
Termination is automatic, we obtain a univ. instance or a core. We can instantiate the labelled nulls postfactum (Assuming everything that shares attributes has a common ancestor, this is linear)
!!!Problems
Numeric constraints
Has-part relations (a part may not be part of many things)
!Dynamic constraint satisfaction problems
Paper introduces DCSPs — CSPs where the variables that must be assigned a solution can change, e.g. configuration problems. Traditionally, this was done by having a CSP solver and a mechanism for creating new variables; however, the authors claim this separation is suboptimal.
The motivation for their approach is to model the configuration task as defined in MittalFrayman1982. Thus, a variable can be //active// or //inactive//, and since this may change, we record this. There's a set of initial variables, and they are always active. Thus, a DCSP that does not activate any variables reduces to a CSP with the initial variables as variables.
To use the new notion, the authors let constraints be of two types: compatibility constraints (the normal CSP type) and activity constraints (these control the activity of variables). Normal constraints now depend on activity — if any of the constrained variables are inactive, the constraint is satisfied. As for activity, the authors find four types of such constraints to be useful, namely
*Require Variable (RV), "if predicate $P$ holds, then variable $k$ must be active"
*Always Require Variable (ARV), "if variables $\vec{v}$ are active, then variable $k$ must be". ARV constraints can be used to specify the initial variables (leave $\vec{v}$ empty).
*Require Not (RN), "if predicate $P$ holds, then variable $k$ must be inactive", i.e the opposite of RV.
*Always Require Not (ARN), the opposite of ARV analogous to RN.
The authors introduce a logical language for expressing these constraints. Also, ARV and ARN can be seen as abbreviations for RV and RN with big disjunctions on the left-hand side.
Thus, a DCSP has a set of variables (all specified up front, even the inactive ones), a set of constraints of both types, and domain for every variable. A solution is a set of (variable, value) pairs that satisfies all constraints ''such that no subset satisfies the constraints''. This optimization criterion is not sufficient for unique solutions. Also, we could drop it.
The rest of the paper is spent on discussing applications (configuration, compositional modeling) and their implementation of a system for the latter. The algorithm is backtracking (with no surprises). The discussion section says two interesting things,
*Since we have two types of constraints, we can tune performance for them separately, and
*Initially, the constraint graph for a DCSP is sparse, since most variables are inactive. New connections appear when we satisfy constraints, so we should be able to control this.
!Towards a generic model of configuration tasks
Lays the groundwork for configuration. Given
*a set of components described by a set of properties, ports for connecting them to other components, constraints at each port that describe the components that can be connected at this port, and other structural constraints,
*some description of the desired configuration, and
*possibly some way of ranking solutions,
build a configuration, that is, a set of components and a description of the connections between them.
With a loose definition of components and ports, the naive complexity with $N$ components and $p$ ports per component is $O(\sqrt{(pn)!})$. If we have a bound $s$ on the size of our solutions, we can get complexity $O(nk^sp^s)$. To cope with this, they introduce two assumptions, namely
*that we configure according to architectures, that is, functions we need, and
*that such functions have sets of key components that provide them.
With these restrictions a big configuration problem can fall apart into chunks that have few or no connections between them. The functional decomposition can be separate from the catalog, this means that we can use it to guide the search.
They describe two methods for solving: generate-and-test (obvious), and a top-down approach where you take a function, select a key component, then work from it, backtracking as needed. Problems as usual, thrashing and doing work twice.
Bigger problems are posed by re-usable components (some are, some aren't — a slot cannot be used for two different cards, but a fan can well cool two processors), and multi-function components. if a component provides several functions, we'd like to notice that.
If $P \not= NP$, does there exist a problem $S$ strictly in $NP$ such that $S$ is not $NP$-complete? If yes, I will be surprised. Consequences if yes?
Similarly for other classes, do they have problems with strict membership but without hardness?
Update: Largely unanswerable, as we don't have any separation results for $P$ or $NP$, or indeed anywhere else.
!Global constraints
There are global constraints that can be solved in polynomial time. There are NP-complete problems where all constraints are polynomially solvable.
!GCC
GCC generalizes ALLDIFF, by giving every value card. set $\{1\}$.
Does GCC also generalize NVALUE, and if yes, how?
PartnerUnits can be modeled with GCC constraints only using auxiliary variables $PU_{ij}$ for the partners.
!Strong statements
Ordinary constraints can be handled just fine.
Activation constraints can be efficiently encoded into whatever, via activation variables.
Global constraints, in particular numeric ones, seem to be interesting.
Can we have local numeric constraints?
A numeric constraint over variables $\{x_1,\ldots,x_n\}$ is a function $f$ of arity $n$, and a constant $c$. The constraint is $f(x_1,\ldots,x_n) \leq c$. More generally, I care about $\{<, =\}$.
What if we are given two functions, and ask that $f(\vec{x}) \leq g(\vec{y})$? In particular, what can we restrict $\vec{y}$ to?
This is not soft/valued CSP, since we are assigning costs not to constraints, but to tuples of values.
!Research directions
!!Number of solutions
!!Orderings and symmetry breaking
!!CSPs as homomorphism problems
Many conf. problems are modular, or seem modular, but are not in any easy sense. Each condition can be seen as a separate homomorphism (this applies to all CSPs), but we need to satisfy them simultaneously. When can we compose two separate homomorphisms into one that satisfies both simultaneously, without hard computational work?
Several things are related to this: k-consistency, hypertrees.
!!Assorted
If we view partnerunits as a CSP, it's bags to vertices, and the constraints are global. Is it possible to recast the problem so that the constraints become ordinary, and if not, why not? Is it at all possible to have non-global cardinality constraints?
This tag marks problems that I consider open, i.e. problems I don't know solutions to.
It is known that there exist $P$-complete problems, and they have upper bounds.
It is also know that for any $k$, there exist problems in $P$ with complexity $\Omega(n^k)$. ([[Time Hierarchy Theorem | http://en.wikipedia.org/wiki/Time_hierarchy_theorem]])
These two statements, however, combine rather poorly, as they mean that there are problems in $P$ with lower bounds that are ''greater'' than the upper bounds of $P$-hard problems. Does this immediatly kill the isomorphy of reductions?
Let $n^k$ be the lowest upper bound for any $P$-complete problem, and let $Q$ be the problem with this bound. For any other problem in $P$ there exists a reduction to $Q$, in particular for problems with lower bounds above $n^k$. These reductions must gobble up the difference in the running time. In other words, not all reductions are made equal.
What does the notion of hardness for $P$ mean given this?
!Bare SAT
Same as DLV, slightly better in some cases. Linear counting better for SAT, worse for UNSAT.
20 20 20 5 4 0.5 is blazing fast.
30 30 30 5 6 0.5 is also.
30 30 30 5 5 0.5 is usually fast, within 2 minutes.
10 10 10 2 3 1 is timeout
10 10 10 2 3 0.5 is timeout
10 10 10 2 4 0.5 is instant
!Symmetry breaking
Symmetry breaking vastly improves UNSAT, but slows down SAT considerably. Is this due to few instances having few solutions? (We are either UNSAT or k-SAT for large k)
10 10 10 2 3 0.5 is UNSAT, but hard for both. However, symmetry breaking solved it in 1200s while ordinary timed out after 1800s.
10 10 10 2 3 1 is instant
50 50 50 50 0 1 is SAT, both find solutions very quickly even if 50 solutions reduce to only one with symmetry breaking.
30 30 30 5 6 0.5 is SAT timeout
30 30 30 5 5 0.5 is timeout
20 20 20 5 4 0.5 times out
!Pete's triangle
Unfortunately we have z*d by u matrix, where u = max(z, d), so this is not as good as it looked: We only cut our variables by 1/4.
!Triangle plus lexorder w/o ordinary symbreak
Hum-di-dum
10 10 10 2 3 0.5 is timeout
10 10 10 2 4 0.5 is fast (SAT)
10 10 10 2 3 1 times out same as without symbreak.
20 20 20 5 4 0.5 is instant! (SAT)
30 30 30 5 6 0.5 (SAT) is quick
30 30 30 5 5 0.5 is fast
30 30 30 5 6 1 is fast
30 30 30 5 5 1 is fast
20 20 20 2 3 1 is timeout
In other words, we are back to instant SAT, slow UNSAT. Same as no symbreak. :(
!Triangle plus lexorder plus ordinary symbreak
La-di-da
10 10 10 2 3 0.5 is timeout sometimes, and solution within one minute sometimes.
10 10 10 2 4 0.5 is fast.
10 10 10 2 3 1 is instant
20 20 20 5 4 0.5 is instant
30 30 30 5 6 0.5 is timeout
30 30 30 5 5 0.5 is timeout
30 30 30 5 6 1 is timeout
30 30 30 5 5 1 is fast
20 20 20 2 3 1 is fast (UNSAT)
!Inadmissible versions
!!Strong symmetry breaking
Strong symmetry breaking depends on ordering! And greatly improves UNSAT and SAT!
40 40 40 4 9 1 (SAT) takes a few seconds
40 40 40 4 8 1 (UNSAT) takes long
NOT ADMISSIBLE!
!!Compromise strong
A compromise between the two that does not depend on ordering works better.
10 10 10 2 3 0.5 is fast regardless, for example.
20 20 20 5 4 0.5 is slow, even if it's SAT, same as for the non-compromise valid symbreak, but faster than the non-compromise.
In other words, compromise works best so far, but can still be made to thrash. However, SAT and UNSAT seem to be more balanced: We thrash on SAT only when the non-symbreak one does as well. For UNSAT, however, we keep our improvements and improve still further.
COMPROMISE LOSES OPTIMALITY!
AND ALSO ADMISSIBILITY!
!!Admissible symbreak with bagsize:
10 10 10 2 3 0.5 is now very quick. (UNSAT)
10 10 10 2 4 0.5 is slow (SAT)
20 20 20 5 4 0.5 times out (SAT)
Doing edges "properly" instead of as-needed seems to slow things down, not worth trying for the non-symbreak versions.
NOT ADMISSIBLE!!!
The optimization version is NP-complete. Reduction from [[bin packing|http://en.wikipedia.org/wiki/Bin_packing]]. We are given a set $S$ of even natural numbers, an even natural number $V$, and a natural number $b$ (for the general version, double every size, as well as the bin size). We need to assign the elements of $S$ to $b$ bags $B_1, \ldots , B_b$ such that for every $i$, $\Sigma(B_i) \leq V$.
We reduce this to PartnerUnits by making a biclique for every $s \in S$ (since $s$ is even, this works the obvious way), setting the size of every unit to $V$, and the number of partners to $0$, and ask whether there exists a solution with $b$ units. It exists if and only if there exists a solution to the bin packing instance we were given. This depends on bin packing being NP-complete with the numbers coded in unary, which it is.
/***
|''Name:''|PasswordOptionPlugin|
|''Description:''|Extends TiddlyWiki options with non encrypted password option.|
|''Version:''|1.0.2|
|''Date:''|Apr 19, 2007|
|''Source:''|http://tiddlywiki.bidix.info/#PasswordOptionPlugin|
|''Author:''|BidiX (BidiX (at) bidix (dot) info)|
|''License:''|[[BSD open source license|http://tiddlywiki.bidix.info/#%5B%5BBSD%20open%20source%20license%5D%5D ]]|
|''~CoreVersion:''|2.2.0 (Beta 5)|
***/
//{{{
version.extensions.PasswordOptionPlugin = {
major: 1, minor: 0, revision: 2,
date: new Date("Apr 19, 2007"),
source: 'http://tiddlywiki.bidix.info/#PasswordOptionPlugin',
author: 'BidiX (BidiX (at) bidix (dot) info',
license: '[[BSD open source license|http://tiddlywiki.bidix.info/#%5B%5BBSD%20open%20source%20license%5D%5D]]',
coreVersion: '2.2.0 (Beta 5)'
};
config.macros.option.passwordCheckboxLabel = "Save this password on this computer";
config.macros.option.passwordInputType = "password"; // password | text
setStylesheet(".pasOptionInput {width: 11em;}\n","passwordInputTypeStyle");
merge(config.macros.option.types, {
'pas': {
elementType: "input",
valueField: "value",
eventName: "onkeyup",
className: "pasOptionInput",
typeValue: config.macros.option.passwordInputType,
create: function(place,type,opt,className,desc) {
// password field
config.macros.option.genericCreate(place,'pas',opt,className,desc);
// checkbox linked with this password "save this password on this computer"
config.macros.option.genericCreate(place,'chk','chk'+opt,className,desc);
// text savePasswordCheckboxLabel
place.appendChild(document.createTextNode(config.macros.option.passwordCheckboxLabel));
},
onChange: config.macros.option.genericOnChange
}
});
merge(config.optionHandlers['chk'], {
get: function(name) {
// is there an option linked with this chk ?
var opt = name.substr(3);
if (config.options[opt])
saveOptionCookie(opt);
return config.options[name] ? "true" : "false";
}
});
merge(config.optionHandlers, {
'pas': {
get: function(name) {
if (config.options["chk"+name]) {
return encodeCookie(config.options[name].toString());
} else {
return "";
}
},
set: function(name,value) {config.options[name] = decodeCookie(value);}
}
});
// need to reload options to load passwordOptions
loadOptionsCookie();
/*
if (!config.options['pasPassword'])
config.options['pasPassword'] = '';
merge(config.optionsDesc,{
pasPassword: "Test password"
});
*/
//}}}
/***
|Name|Plugin: Scientific Notation|
|Created by|BobMcElrath|
|Email|my first name at my last name dot org|
|Location|http://bob.mcelrath.org/tiddlyjsmath-2.0.3.html|
|Version|1.0|
|Requires|[[TiddlyWiki|http://www.tiddlywiki.com]] ≥ 2.0.3, [[jsMath|http://www.math.union.edu/~dpvc/jsMath/]] ≥ 3.0, [[Plugin: jsMath]]|
!Description
This plugin will render numbers expressed in scientific notation, such as {{{3.5483e12}}} using the jsMath plugin to display it in an intuitive way such as 3.5483e12. You may customize the number of significant figures displayed, as well as "normalize" numbers so that {{{47392.387e9}}} is displayed as 47392.387e9.
!Installation
Install the Requirements, above, add this tiddler to your tiddlywiki, and give it the {{{systemConfig}}} tag.
!History
* 1-Feb-06, version 1.0, Initial release
!Code
***/
//{{{
config.formatters.push({
name: "scientificNotation",
match: "\\b[0-9]+\\.[0-9]+[eE][+-]?[0-9]+\\b",
element: "span",
className: "math",
normalize: true, // set to 'true' to convert numbers to X.XXX \times 10^{y}
sigfigs: 3, // with this many digits in the mantissa
handler: function(w) {
var snRegExp = new RegExp("\\b([0-9]+(?:\\.[0-9]+)?)[eE]([-0-9+]+)\\b");
var mymatch = snRegExp.exec(w.matchText);
var mantissa = mymatch[1];
var exponent = parseInt(mymatch[2]);
// normalize the number.
if(this.normalize) {
mantissa = parseFloat(mantissa);
while(mantissa > 10.0) {
mantissa = mantissa / 10.0;
exponent++;
}
while(mantissa < 1.0) {
mantissa = mantissa * 10.0;
exponent--;
}
var sigfigsleft = this.sigfigs;
mantissa = parseInt(mantissa) + "." + (Math.round(Math.pow(10,this.sigfigs-1)*mantissa)+"").substr(1,this.sigfigs-1);
}
var e = document.createElement(this.element);
e.className = this.className;
if(exponent == 0) {
e.appendChild(document.createTextNode(mantissa));
} else {
e.appendChild(document.createTextNode(mantissa + "\\times 10^{" + exponent + "}"));
}
w.output.appendChild(e);
}
});
//}}}
/***
|Name|Plugin: arXiv Links|
|Created by|BobMcElrath|
|Email|my first name at my last name dot org|
|Location|http://bob.mcelrath.org/tiddlyjsmath-2.0.3.html|
|Version|1.0|
|Requires|[[TiddlyWiki|http://www.tiddlywiki.com]] ≥ 2.0.3|
!Description
This formatting plugin will render links to the [[arXiv|http://www.arxiv.org]] preprint system. If you type a paper reference such as hep-ph/0509024, it will be rendered as an external link to the abstract of that paper.
!Installation
Add this tiddler to your tiddlywiki, and give it the {{{systemConfig}}} tag.
!History
* 1-Feb-06, version 1.0, Initial release
!Code
***/
//{{{
config.formatters.push({
name: "arXivLinks",
match: "\\b(?:astro-ph|cond-mat|hep-ph|hep-th|hep-lat|gr-qc|nucl-ex|nucl-th|quant-ph|(?:cs|math|nlin|physics|q-bio)(?:\\.[A-Z]{2})?)/[0-9]{7}\\b",
element: "a",
handler: function(w) {
var e = createExternalLink(w.output, "http://arxiv.org/abs/"+w.matchText);
e.target = "_blank"; // open in new window
w.outputText(e,w.matchStart,w.nextMatch);
}
});
//}}}
/***
|Name|Plugin: jsMath|
|Created by|BobMcElrath|
|Email|my first name at my last name dot org|
|Location|http://bob.mcelrath.org/tiddlyjsmath.html|
|Version|1.5.1|
|Requires|[[TiddlyWiki|http://www.tiddlywiki.com]] ≥ 2.0.3, [[jsMath|http://www.math.union.edu/~dpvc/jsMath/]] ≥ 3.0|
!Description
LaTeX is the world standard for specifying, typesetting, and communicating mathematics among scientists, engineers, and mathematicians. For more information about LaTeX itself, visit the [[LaTeX Project|http://www.latex-project.org/]]. This plugin typesets math using [[jsMath|http://www.math.union.edu/~dpvc/jsMath/]], which is an implementation of the TeX math rules and typesetting in javascript, for your browser. Notice the small button in the lower right corner which opens its control panel.
!Installation
In addition to this plugin, you must also [[install jsMath|http://www.math.union.edu/~dpvc/jsMath/download/jsMath.html]] on the same server as your TiddlyWiki html file. If you're using TiddlyWiki without a web server, then the jsMath directory must be placed in the same location as the TiddlyWiki html file.
I also recommend modifying your StyleSheet use serif fonts that are slightly larger than normal, so that the math matches surrounding text, and \\small fonts are not unreadable (as in exponents and subscripts).
{{{
.viewer {
line-height: 125%;
font-family: serif;
font-size: 12pt;
}
}}}
If you had used a previous version of [[Plugin: jsMath]], it is no longer necessary to edit the main tiddlywiki.html file to add the jsMath <script> tag. [[Plugin: jsMath]] now uses ajax to load jsMath.
!History
* 11-Nov-05, version 1.0, Initial release
* 22-Jan-06, version 1.1, updated for ~TW2.0, tested with jsMath 3.1, editing tiddlywiki.html by hand is no longer necessary.
* 24-Jan-06, version 1.2, fixes for Safari, Konqueror
* 27-Jan-06, version 1.3, improved error handling, detect if ajax was already defined (used by ZiddlyWiki)
* 12-Jul-06, version 1.4, fixed problem with not finding image fonts
* 26-Feb-07, version 1.5, fixed problem with Mozilla "unterminated character class".
* 27-Feb-07, version 1.5.1, Runs compatibly with TW 2.1.0+, by Bram Chen
!Examples
|!Source|!Output|h
|{{{The variable $x$ is real.}}}|The variable $x$ is real.|
|{{{The variable \(y\) is complex.}}}|The variable \(y\) is complex.|
|{{{This \[\int_a^b x = \frac{1}{2}(b^2-a^2)\] is an easy integral.}}}|This \[\int_a^b x = \frac{1}{2}(b^2-a^2)\] is an easy integral.|
|{{{This $$\int_a^b \sin x = -(\cos b - \cos a)$$ is another easy integral.}}}|This $$\int_a^b \sin x = -(\cos b - \cos a)$$ is another easy integral.|
|{{{Block formatted equations may also use the 'equation' environment \begin{equation} \int \tan x = -\ln \cos x \end{equation} }}}|Block formatted equations may also use the 'equation' environment \begin{equation} \int \tan x = -\ln \cos x \end{equation}|
|{{{Equation arrays are also supported \begin{eqnarray} a &=& b \\ c &=& d \end{eqnarray} }}}|Equation arrays are also supported \begin{eqnarray} a &=& b \\ c &=& d \end{eqnarray} |
|{{{I spent \$7.38 on lunch.}}}|I spent \$7.38 on lunch.|
|{{{I had to insert a backslash (\\) into my document}}}|I had to insert a backslash (\\) into my document|
!Code
***/
//{{{
// AJAX code adapted from http://timmorgan.org/mini
// This is already loaded by ziddlywiki...
if(typeof(window["ajax"]) == "undefined") {
ajax = {
x: function(){try{return new ActiveXObject('Msxml2.XMLHTTP')}catch(e){try{return new ActiveXObject('Microsoft.XMLHTTP')}catch(e){return new XMLHttpRequest()}}},
gets: function(url){var x=ajax.x();x.open('GET',url,false);x.send(null);return x.responseText}
}
}
// Load jsMath
jsMath = {
Setup: {inited: 1}, // don't run jsMath.Setup.Body() yet
Autoload: {root: new String(document.location).replace(/[^\/]*$/,'jsMath/')} // URL to jsMath directory, change if necessary
};
var jsMathstr;
try {
jsMathstr = ajax.gets(jsMath.Autoload.root+"jsMath.js");
} catch(e) {
alert("jsMath was not found: you must place the 'jsMath' directory in the same place as this file. "
+"The error was:\n"+e.name+": "+e.message);
throw(e); // abort eval
}
try {
window.eval(jsMathstr);
} catch(e) {
alert("jsMath failed to load. The error was:\n"+e.name + ": " + e.message + " on line " + e.lineNumber);
}
jsMath.Setup.inited=0; // allow jsMath.Setup.Body() to run again
// Define wikifers for latex
config.formatterHelpers.mathFormatHelper = function(w) {
var e = document.createElement(this.element);
e.className = this.className;
var endRegExp = new RegExp(this.terminator, "mg");
endRegExp.lastIndex = w.matchStart+w.matchLength;
var matched = endRegExp.exec(w.source);
if(matched) {
var txt = w.source.substr(w.matchStart+w.matchLength,
matched.index-w.matchStart-w.matchLength);
if(this.keepdelim) {
txt = w.source.substr(w.matchStart, matched.index+matched[0].length-w.matchStart);
}
e.appendChild(document.createTextNode(txt));
w.output.appendChild(e);
w.nextMatch = endRegExp.lastIndex;
}
}
config.formatters.push({
name: "displayMath1",
match: "\\\$\\\$",
terminator: "\\\$\\\$\\n?", // 2.0 compatability
termRegExp: "\\\$\\\$\\n?",
element: "div",
className: "math",
handler: config.formatterHelpers.mathFormatHelper
});
config.formatters.push({
name: "inlineMath1",
match: "\\\$",
terminator: "\\\$", // 2.0 compatability
termRegExp: "\\\$",
element: "span",
className: "math",
handler: config.formatterHelpers.mathFormatHelper
});
var backslashformatters = new Array(0);
backslashformatters.push({
name: "inlineMath2",
match: "\\\\\\\(",
terminator: "\\\\\\\)", // 2.0 compatability
termRegExp: "\\\\\\\)",
element: "span",
className: "math",
handler: config.formatterHelpers.mathFormatHelper
});
backslashformatters.push({
name: "displayMath2",
match: "\\\\\\\[",
terminator: "\\\\\\\]\\n?", // 2.0 compatability
termRegExp: "\\\\\\\]\\n?",
element: "div",
className: "math",
handler: config.formatterHelpers.mathFormatHelper
});
backslashformatters.push({
name: "displayMath3",
match: "\\\\begin\\{equation\\}",
terminator: "\\\\end\\{equation\\}\\n?", // 2.0 compatability
termRegExp: "\\\\end\\{equation\\}\\n?",
element: "div",
className: "math",
handler: config.formatterHelpers.mathFormatHelper
});
// These can be nested. e.g. \begin{equation} \begin{array}{ccc} \begin{array}{ccc} ...
backslashformatters.push({
name: "displayMath4",
match: "\\\\begin\\{eqnarray\\}",
terminator: "\\\\end\\{eqnarray\\}\\n?", // 2.0 compatability
termRegExp: "\\\\end\\{eqnarray\\}\\n?",
element: "div",
className: "math",
keepdelim: true,
handler: config.formatterHelpers.mathFormatHelper
});
// The escape must come between backslash formatters and regular ones.
// So any latex-like \commands must be added to the beginning of
// backslashformatters here.
backslashformatters.push({
name: "escape",
match: "\\\\.",
handler: function(w) {
w.output.appendChild(document.createTextNode(w.source.substr(w.matchStart+1,1)));
w.nextMatch = w.matchStart+2;
}
});
config.formatters=backslashformatters.concat(config.formatters);
window.wikify = function(source,output,highlightRegExp,tiddler)
{
if(source && source != "") {
if(version.major == 2 && version.minor > 0) {
var wikifier = new Wikifier(source,getParser(tiddler),highlightRegExp,tiddler);
wikifier.subWikifyUnterm(output);
} else {
var wikifier = new Wikifier(source,formatter,highlightRegExp,tiddler);
wikifier.subWikify(output,null);
}
jsMath.ProcessBeforeShowing();
}
}
//}}}
Term from [[EWD1300 | http://www.cs.utexas.edu/users/EWD/transcriptions/EWD13xx/EWD1300.html ]]. Can be restated as do not, ever, teach magic, as in, explain what happens. Conveying a notion of "magic" makes students think it's all difficult and beyond their abilities.
Illustrative quote:
<<<
As time went by, we accepted as challenges to avoid pulling rabbits out of the magician's hat. There is a mathematical style in which proofs are presented as strings of unmotivated tricks that miraculously do the job, but we found greater intellectual satisfaction in showing how each next step in the argument, if not actually forced, is at least something sweetly reasonable to try. Another reason for avoiding rabbits as much as possible was that we did not want to teach proofs, we wanted to teach proof design. Eventually, expelling rabbits became another joy of my professional life.
<<<
Jefferson and Green
GAC:
Constant number of cycles, or of communicating vertices.
Standa: Constant number of vertices in nontrivial overlap, instead of single vertices?
<<<
That is, the study of crack-pots, a.k.a. kooks, cranks, flakes, "authors of particularly unsolicited manuscripts", and the like. For obvious reasons, this is the golden age of psychoceramics, when a million mutant flowers bloom, and a thousand sherds of thought contend.
<<<
C. R. Shalizi, [[ Notebooks | http://www.cscs.umich.edu/~crshalizi/notabene/psychoceramics.html ]]
This tiddlywiki is an open notebook for [[Evgenij Thorstensen|http://folk.uio.no/evgenit]] of [[OUCS|http://www.comlab.ox.ac.uk]]. The most useful thing it contains are summaries of papers I have read, tagged by ReadPaper.
Marks papers I have read. Each tiddler tagged should have a short summary of the paper. The papers are alphabetic by first author.
The context is in consistency techniques, for example for ConstraintSatisfaction.
MYCIN extension: We want to ensure consistency of $\forall$-statements. When a new piece of information comes in, we recalculate all $\forall$-statements affected. However, these may in turn be premises to other statements (via rules), so those have to be recalculated, and we quickly end up in a RecursiveMess, especially if stuff doesn't follow patterns.
ArcConsistency is the same: To ensure consistency for arc $(V_i, V_j)$, we remove all values in $V_i$ for which there are ''no values'' in $V_j$. However, for any $x$ this may turn the arc $(x, V_i)$ inconsistent, so we quickly end up in a RecursiveMess.
Research notes. Will usually be quite unintelligible for other people.
CSP modulo Theories
Clause learning for CSP, adding constraints.
Microstructures
!Configuration as composite constraint satisfaction
Paper presents the Compositional CSP formalism, to be used for configuration. This formalism subsumes several previous extensions to classical CSPs, namely Meta CSPs, Hierarchical CSPs, and the [[DCSP]] formalism.
A compositional CSP is, like the classic version, defined by a tripled $\langle V, C, D \rangle$. However, the domains of the variables are allowed to contain entire subproblems (other compositional CSPs). If such a value is assigned to a variable $v$, the problem is modified by
*adding the new variables (but removing $v$),
*adding the new domains for the new variables, and
*adding the new constraints, in particular replacing the constraints that mention $v$ by constraints that mention the new variables.
The chief advantage of this is that existing search and filtering algorithms can easily be adapted (to backtrack over a removed variable). Also, the fact that variables are replaced during the search keeps the problem from explosive growth.
This allows you to model an artifact to be configured directly from the catalog (every abstract component is a compositional CSP, and ports are variables that have components as values). Contrast this with the [[DCSP]] formalism, where the catalog must be translated into rules.
Finally, given a taxonomy and a single constraint listing all allowed tuples of leaf values, we can generate constraints over the abstract variables, so-called implied constraints. This allows us to reason at local levels (thus pruning the search space early) even if we didn't have explicit constraints on every abstract level to begin with.
!Optimization methods for constraint resource problems
Paper presents a system for solving the following problem: Given a set of producers and consumers of resources, as well as a cumulative expression of consumption denoting ''cost'', find a set of producers with minimal cost so that all resources are balanced.
The problem is modeled as a composite CSP (SabinFreuder1996), and the authors discuss their implementation of it using an arc consistency algorithm. They model connections as ports with cardinality and type. Ports are bidirectional: if A and B are connected, A has a port that accepts type B components, and B a port that accepts type A objects. Furthermore, ports allow cumulative constraints that range over components connected to the port.
The domain of a port variable can be infinite, and this is solved by wildcards like in Mailharro et al. Bidirectionality allows more pruning, as a connection must satisfy constraints at both ends.
Using this model, the resource problem can be treated with a Branch and Bound technique. We maintain an upper and a lower bound for the cost, where the upper bound is the best solution seen so far, and the lower bound is current partial cost + the sum of resources consumed but not yet allocated. These bounds are represented as constraints.
Finally, we need to represent the global balancing constraints. To do this, the authors use a ''metaport'' that allows us to quantify over all the objects of a given type present in the system. A balancing constraint (power consumed is less than or equal to power produced) becomes a cumulative constraint over two metaports.
Finally, the authors avoid equivalent partial solutions by introducing a notion of ''interchangeability'' for components of a type. Here, we can get great benefits from a taxonomy of abstract types, as interchangeability can be true at one level of abstraction (cards consuming power) and false at another (subtypes of cards consuming additional resources).
The authors also test their implementation on random data and present the results.
!Constraint-based modeling: From diagnosis and configuration to network management
Paper presents a prototype system for automatic diagnosis of computer network services. The system models parts of the problem as a CSP (looking for partial assignments, since a fault means unsatisfiability) and parts as a [[DCSP]].
We read papers so you don't have to
!A fixpoint definition of dynamic constraint satisfaction
Paper deals with complexity and extensions of DCSPs. For complexity, two problems are set out, namely
*Given a DCSP, does it have a solution? (DCSP-D)
*Given a DCSP and a set of requirements, is there a solution that satisfies the requirements (DCSP-RD)?
The requirements can not simply be part of the DCSP, as that may permit solutions that were previously disallowed, i.e there's no solution to requirements, but there is a solution to the DCSP obtained by treating requirements as constraints. This seems to be due to the subset minimality condition on DCSP solutions.
For extensions, the authors want to allow ''generalized activity constraints'' (GAC), i.e activity constraints with disjunctions on the right-hand side. This disjunction is parametrized by two numbers, and written as $i\{v_1|\ldots|v_n\}j$, meaning that the number of active variables among $v_1,\ldots,v_n$ must be between $i$ and $j$. Also, the left-hand side atoms mean "active and satisfied", while negated atoms mean "not active or not satisfied". The motivation for this is found in configuration, where several components may provide some function. The authors prove that DCSP-RD is $\Sigma_2P$-hard if GACs are allowed; this is due to the subset minimality condition.
The authors would thus like to replace subset minimality by something more tractable, a desire further supported by their observation that simulating DCSPs by CSPs is not ''modular'', as small changes in the DCSP (e.g. making a variable initial) mean complicated changes in the resulting CSP. In particular, we need to both add and remove e.g. allowed tuples, domain values, etc. to realize simple changes. The authors thus conclude that CSP $\subset$ DCSP — this is again due to the subset minimality condition.
Subset minimality of solutions is replaced by the requirement that a solution be the least fixpoint of an operator $T$ on an assignment. This operator picks out from an assignment all variables that are justified by the activation constraints wrt. some other assignment (hence the fixpoint). The main point is that a GAC justifies every variable on the right-hand side, even if a subset of them would suffice. Hence, this condition is weaker than subset minimality if GACs are present, but coincides with it for standard DCSPs.
As for complexity, the authors show that both DCSP-D and DCSP-RD are NP-complete for the fixpoint version, since CSP is NP-hard and a special case. Since the regular versions of DCSP-D and DCSP-RD are special cases without GACs, and clearly in NP, it follows that they are NP-complete as well.
The authors discuss two implementations, one based on the algorithm in MittalFalkenhainer1990 and one based on mapping DCSPs to propositional logic programs (SoininenNiemela1999).
.viewer {
line-height: 125%;
font-size: 12pt;
}
body {
font-family: univers, arial, helvetica, sans-serif;
}
h1 {
font-size: 115%;
width:50%;
}
h2 {
font-size: 110%;
width:50%;
text-indent: 5px;
}
h3 {
font-size: 105%;
width:50%;
text-indent: 10px;
}
/***
Description: Contains the stuff you need to use Tiddlyspot
Note, you also need UploadPlugin, PasswordOptionPlugin and LoadRemoteFileThroughProxy
from http://tiddlywiki.bidix.info for a complete working Tiddlyspot site.
***/
//{{{
// edit this if you are migrating sites or retrofitting an existing TW
config.tiddlyspotSiteId = 'evgenit';
// make it so you can by default see edit controls via http
config.options.chkHttpReadOnly = false;
window.readOnly = false; // make sure of it (for tw 2.2)
window.showBackstage = true; // show backstage too
// disable autosave in d3
if (window.location.protocol != "file:")
config.options.chkGTDLazyAutoSave = false;
// tweak shadow tiddlers to add upload button, password entry box etc
with (config.shadowTiddlers) {
SiteUrl = 'http://'+config.tiddlyspotSiteId+'.tiddlyspot.com';
SideBarOptions = SideBarOptions.replace(/(<<saveChanges>>)/,"$1<<tiddler TspotSidebar>>");
OptionsPanel = OptionsPanel.replace(/^/,"<<tiddler TspotOptions>>");
DefaultTiddlers = DefaultTiddlers.replace(/^/,"[[WelcomeToTiddlyspot]] ");
MainMenu = MainMenu.replace(/^/,"[[WelcomeToTiddlyspot]] ");
}
// create some shadow tiddler content
merge(config.shadowTiddlers,{
'WelcomeToTiddlyspot':[
"This document is a ~TiddlyWiki from tiddlyspot.com. A ~TiddlyWiki is an electronic notebook that is great for managing todo lists, personal information, and all sorts of things.",
"",
"@@font-weight:bold;font-size:1.3em;color:#444; //What now?// @@ Before you can save any changes, you need to enter your password in the form below. Then configure privacy and other site settings at your [[control panel|http://" + config.tiddlyspotSiteId + ".tiddlyspot.com/controlpanel]] (your control panel username is //" + config.tiddlyspotSiteId + "//).",
"<<tiddler TspotControls>>",
"See also GettingStarted.",
"",
"@@font-weight:bold;font-size:1.3em;color:#444; //Working online// @@ You can edit this ~TiddlyWiki right now, and save your changes using the \"save to web\" button in the column on the right.",
"",
"@@font-weight:bold;font-size:1.3em;color:#444; //Working offline// @@ A fully functioning copy of this ~TiddlyWiki can be saved onto your hard drive or USB stick. You can make changes and save them locally without being connected to the Internet. When you're ready to sync up again, just click \"upload\" and your ~TiddlyWiki will be saved back to tiddlyspot.com.",
"",
"@@font-weight:bold;font-size:1.3em;color:#444; //Help!// @@ Find out more about ~TiddlyWiki at [[TiddlyWiki.com|http://tiddlywiki.com]]. Also visit [[TiddlyWiki.org|http://tiddlywiki.org]] for documentation on learning and using ~TiddlyWiki. New users are especially welcome on the [[TiddlyWiki mailing list|http://groups.google.com/group/TiddlyWiki]], which is an excellent place to ask questions and get help. If you have a tiddlyspot related problem email [[tiddlyspot support|mailto:support@tiddlyspot.com]].",
"",
"@@font-weight:bold;font-size:1.3em;color:#444; //Enjoy :)// @@ We hope you like using your tiddlyspot.com site. Please email [[feedback@tiddlyspot.com|mailto:feedback@tiddlyspot.com]] with any comments or suggestions."
].join("\n"),
'TspotControls':[
"| tiddlyspot password:|<<option pasUploadPassword>>|",
"| site management:|<<upload http://" + config.tiddlyspotSiteId + ".tiddlyspot.com/store.cgi index.html . . " + config.tiddlyspotSiteId + ">>//(requires tiddlyspot password)//<br>[[control panel|http://" + config.tiddlyspotSiteId + ".tiddlyspot.com/controlpanel]], [[download (go offline)|http://" + config.tiddlyspotSiteId + ".tiddlyspot.com/download]]|",
"| links:|[[tiddlyspot.com|http://tiddlyspot.com/]], [[FAQs|http://faq.tiddlyspot.com/]], [[blog|http://tiddlyspot.blogspot.com/]], email [[support|mailto:support@tiddlyspot.com]] & [[feedback|mailto:feedback@tiddlyspot.com]], [[donate|http://tiddlyspot.com/?page=donate]]|"
].join("\n"),
'TspotSidebar':[
"<<upload http://" + config.tiddlyspotSiteId + ".tiddlyspot.com/store.cgi index.html . . " + config.tiddlyspotSiteId + ">><html><a href='http://" + config.tiddlyspotSiteId + ".tiddlyspot.com/download' class='button'>download</a></html>"
].join("\n"),
'TspotOptions':[
"tiddlyspot password:",
"<<option pasUploadPassword>>",
""
].join("\n")
});
//}}}
| !date | !user | !location | !storeUrl | !uploadDir | !toFilename | !backupdir | !origin |
| 02/08/2010 18:32:27 | EvgenijThorstensen | [[/|http://evgenit.tiddlyspot.com/]] | [[store.cgi|http://evgenit.tiddlyspot.com/store.cgi]] | . | [[index.html | http://evgenit.tiddlyspot.com/index.html]] | . |
| 04/08/2010 17:30:09 | EvgenijThorstensen | [[/|http://evgenit.tiddlyspot.com/]] | [[store.cgi|http://evgenit.tiddlyspot.com/store.cgi]] | . | [[index.html | http://evgenit.tiddlyspot.com/index.html]] | . |
| 12/09/2010 16:40:18 | EvgenijThorstensen | [[/|http://evgenit.tiddlyspot.com/]] | [[store.cgi|http://evgenit.tiddlyspot.com/store.cgi]] | . | [[index.html | http://evgenit.tiddlyspot.com/index.html]] | . | ok |
| 12/09/2010 17:05:39 | EvgenijThorstensen | [[/|http://evgenit.tiddlyspot.com/]] | [[store.cgi|http://evgenit.tiddlyspot.com/store.cgi]] | . | [[index.html | http://evgenit.tiddlyspot.com/index.html]] | . |
| 15/10/2010 17:40:01 | EvgenijThorstensen | [[/|http://evgenit.tiddlyspot.com/]] | [[store.cgi|http://evgenit.tiddlyspot.com/store.cgi]] | . | [[index.html | http://evgenit.tiddlyspot.com/index.html]] | . | ok |
| 15/10/2010 17:40:28 | EvgenijThorstensen | [[/|http://evgenit.tiddlyspot.com/]] | [[store.cgi|http://evgenit.tiddlyspot.com/store.cgi]] | . | [[index.html | http://evgenit.tiddlyspot.com/index.html]] | . |
| 15/10/2010 17:43:27 | EvgenijThorstensen | [[/|http://evgenit.tiddlyspot.com/]] | [[store.cgi|http://evgenit.tiddlyspot.com/store.cgi]] | . | [[index.html | http://evgenit.tiddlyspot.com/index.html]] | . |
| 18/10/2010 17:49:50 | EvgenijThorstensen | [[/|http://evgenit.tiddlyspot.com/]] | [[store.cgi|http://evgenit.tiddlyspot.com/store.cgi]] | . | [[index.html | http://evgenit.tiddlyspot.com/index.html]] | . | ok |
| 18/10/2010 18:02:24 | EvgenijThorstensen | [[/|http://evgenit.tiddlyspot.com/]] | [[store.cgi|http://evgenit.tiddlyspot.com/store.cgi]] | . | [[index.html | http://evgenit.tiddlyspot.com/index.html]] | . |
| 18/01/2011 15:02:10 | EvgenijThorstensen | [[/|http://evgenit.tiddlyspot.com/]] | [[store.cgi|http://evgenit.tiddlyspot.com/store.cgi]] | . | [[index.html | http://evgenit.tiddlyspot.com/index.html]] | . |
/***
|''Name:''|UploadPlugin|
|''Description:''|Save to web a TiddlyWiki|
|''Version:''|4.1.3|
|''Date:''|Feb 24, 2008|
|''Source:''|http://tiddlywiki.bidix.info/#UploadPlugin|
|''Documentation:''|http://tiddlywiki.bidix.info/#UploadPluginDoc|
|''Author:''|BidiX (BidiX (at) bidix (dot) info)|
|''License:''|[[BSD open source license|http://tiddlywiki.bidix.info/#%5B%5BBSD%20open%20source%20license%5D%5D ]]|
|''~CoreVersion:''|2.2.0|
|''Requires:''|PasswordOptionPlugin|
***/
//{{{
version.extensions.UploadPlugin = {
major: 4, minor: 1, revision: 3,
date: new Date("Feb 24, 2008"),
source: 'http://tiddlywiki.bidix.info/#UploadPlugin',
author: 'BidiX (BidiX (at) bidix (dot) info',
coreVersion: '2.2.0'
};
//
// Environment
//
if (!window.bidix) window.bidix = {}; // bidix namespace
bidix.debugMode = false; // true to activate both in Plugin and UploadService
//
// Upload Macro
//
config.macros.upload = {
// default values
defaultBackupDir: '', //no backup
defaultStoreScript: "store.php",
defaultToFilename: "index.html",
defaultUploadDir: ".",
authenticateUser: true // UploadService Authenticate User
};
config.macros.upload.label = {
promptOption: "Save and Upload this TiddlyWiki with UploadOptions",
promptParamMacro: "Save and Upload this TiddlyWiki in %0",
saveLabel: "save to web",
saveToDisk: "save to disk",
uploadLabel: "upload"
};
config.macros.upload.messages = {
noStoreUrl: "No store URL in parmeters or options",
usernameOrPasswordMissing: "Username or password missing"
};
config.macros.upload.handler = function(place,macroName,params) {
if (readOnly)
return;
var label;
if (document.location.toString().substr(0,4) == "http")
label = this.label.saveLabel;
else
label = this.label.uploadLabel;
var prompt;
if (params[0]) {
prompt = this.label.promptParamMacro.toString().format([this.destFile(params[0],
(params[1] ? params[1]:bidix.basename(window.location.toString())), params[3])]);
} else {
prompt = this.label.promptOption;
}
createTiddlyButton(place, label, prompt, function() {config.macros.upload.action(params);}, null, null, this.accessKey);
};
config.macros.upload.action = function(params)
{
// for missing macro parameter set value from options
if (!params) params = {};
var storeUrl = params[0] ? params[0] : config.options.txtUploadStoreUrl;
var toFilename = params[1] ? params[1] : config.options.txtUploadFilename;
var backupDir = params[2] ? params[2] : config.options.txtUploadBackupDir;
var uploadDir = params[3] ? params[3] : config.options.txtUploadDir;
var username = params[4] ? params[4] : config.options.txtUploadUserName;
var password = config.options.pasUploadPassword; // for security reason no password as macro parameter
// for still missing parameter set default value
if ((!storeUrl) && (document.location.toString().substr(0,4) == "http"))
storeUrl = bidix.dirname(document.location.toString())+'/'+config.macros.upload.defaultStoreScript;
if (storeUrl.substr(0,4) != "http")
storeUrl = bidix.dirname(document.location.toString()) +'/'+ storeUrl;
if (!toFilename)
toFilename = bidix.basename(window.location.toString());
if (!toFilename)
toFilename = config.macros.upload.defaultToFilename;
if (!uploadDir)
uploadDir = config.macros.upload.defaultUploadDir;
if (!backupDir)
backupDir = config.macros.upload.defaultBackupDir;
// report error if still missing
if (!storeUrl) {
alert(config.macros.upload.messages.noStoreUrl);
clearMessage();
return false;
}
if (config.macros.upload.authenticateUser && (!username || !password)) {
alert(config.macros.upload.messages.usernameOrPasswordMissing);
clearMessage();
return false;
}
bidix.upload.uploadChanges(false,null,storeUrl, toFilename, uploadDir, backupDir, username, password);
return false;
};
config.macros.upload.destFile = function(storeUrl, toFilename, uploadDir)
{
if (!storeUrl)
return null;
var dest = bidix.dirname(storeUrl);
if (uploadDir && uploadDir != '.')
dest = dest + '/' + uploadDir;
dest = dest + '/' + toFilename;
return dest;
};
//
// uploadOptions Macro
//
config.macros.uploadOptions = {
handler: function(place,macroName,params) {
var wizard = new Wizard();
wizard.createWizard(place,this.wizardTitle);
wizard.addStep(this.step1Title,this.step1Html);
var markList = wizard.getElement("markList");
var listWrapper = document.createElement("div");
markList.parentNode.insertBefore(listWrapper,markList);
wizard.setValue("listWrapper",listWrapper);
this.refreshOptions(listWrapper,false);
var uploadCaption;
if (document.location.toString().substr(0,4) == "http")
uploadCaption = config.macros.upload.label.saveLabel;
else
uploadCaption = config.macros.upload.label.uploadLabel;
wizard.setButtons([
{caption: uploadCaption, tooltip: config.macros.upload.label.promptOption,
onClick: config.macros.upload.action},
{caption: this.cancelButton, tooltip: this.cancelButtonPrompt, onClick: this.onCancel}
]);
},
options: [
"txtUploadUserName",
"pasUploadPassword",
"txtUploadStoreUrl",
"txtUploadDir",
"txtUploadFilename",
"txtUploadBackupDir",
"chkUploadLog",
"txtUploadLogMaxLine"
],
refreshOptions: function(listWrapper) {
var opts = [];
for(i=0; i<this.options.length; i++) {
var opt = {};
opts.push();
opt.option = "";
n = this.options[i];
opt.name = n;
opt.lowlight = !config.optionsDesc[n];
opt.description = opt.lowlight ? this.unknownDescription : config.optionsDesc[n];
opts.push(opt);
}
var listview = ListView.create(listWrapper,opts,this.listViewTemplate);
for(n=0; n<opts.length; n++) {
var type = opts[n].name.substr(0,3);
var h = config.macros.option.types[type];
if (h && h.create) {
h.create(opts[n].colElements['option'],type,opts[n].name,opts[n].name,"no");
}
}
},
onCancel: function(e)
{
backstage.switchTab(null);
return false;
},
wizardTitle: "Upload with options",
step1Title: "These options are saved in cookies in your browser",
step1Html: "<input type='hidden' name='markList'></input><br>",
cancelButton: "Cancel",
cancelButtonPrompt: "Cancel prompt",
listViewTemplate: {
columns: [
{name: 'Description', field: 'description', title: "Description", type: 'WikiText'},
{name: 'Option', field: 'option', title: "Option", type: 'String'},
{name: 'Name', field: 'name', title: "Name", type: 'String'}
],
rowClasses: [
{className: 'lowlight', field: 'lowlight'}
]}
};
//
// upload functions
//
if (!bidix.upload) bidix.upload = {};
if (!bidix.upload.messages) bidix.upload.messages = {
//from saving
invalidFileError: "The original file '%0' does not appear to be a valid TiddlyWiki",
backupSaved: "Backup saved",
backupFailed: "Failed to upload backup file",
rssSaved: "RSS feed uploaded",
rssFailed: "Failed to upload RSS feed file",
emptySaved: "Empty template uploaded",
emptyFailed: "Failed to upload empty template file",
mainSaved: "Main TiddlyWiki file uploaded",
mainFailed: "Failed to upload main TiddlyWiki file. Your changes have not been saved",
//specific upload
loadOriginalHttpPostError: "Can't get original file",
aboutToSaveOnHttpPost: 'About to upload on %0 ...',
storePhpNotFound: "The store script '%0' was not found."
};
bidix.upload.uploadChanges = function(onlyIfDirty,tiddlers,storeUrl,toFilename,uploadDir,backupDir,username,password)
{
var callback = function(status,uploadParams,original,url,xhr) {
if (!status) {
displayMessage(bidix.upload.messages.loadOriginalHttpPostError);
return;
}
if (bidix.debugMode)
alert(original.substr(0,500)+"\n...");
// Locate the storeArea div's
var posDiv = locateStoreArea(original);
if((posDiv[0] == -1) || (posDiv[1] == -1)) {
alert(config.messages.invalidFileError.format([localPath]));
return;
}
bidix.upload.uploadRss(uploadParams,original,posDiv);
};
if(onlyIfDirty && !store.isDirty())
return;
clearMessage();
// save on localdisk ?
if (document.location.toString().substr(0,4) == "file") {
var path = document.location.toString();
var localPath = getLocalPath(path);
saveChanges();
}
// get original
var uploadParams = new Array(storeUrl,toFilename,uploadDir,backupDir,username,password);
var originalPath = document.location.toString();
// If url is a directory : add index.html
if (originalPath.charAt(originalPath.length-1) == "/")
originalPath = originalPath + "index.html";
var dest = config.macros.upload.destFile(storeUrl,toFilename,uploadDir);
var log = new bidix.UploadLog();
log.startUpload(storeUrl, dest, uploadDir, backupDir);
displayMessage(bidix.upload.messages.aboutToSaveOnHttpPost.format([dest]));
if (bidix.debugMode)
alert("about to execute Http - GET on "+originalPath);
var r = doHttp("GET",originalPath,null,null,username,password,callback,uploadParams,null);
if (typeof r == "string")
displayMessage(r);
return r;
};
bidix.upload.uploadRss = function(uploadParams,original,posDiv)
{
var callback = function(status,params,responseText,url,xhr) {
if(status) {
var destfile = responseText.substring(responseText.indexOf("destfile:")+9,responseText.indexOf("\n", responseText.indexOf("destfile:")));
displayMessage(bidix.upload.messages.rssSaved,bidix.dirname(url)+'/'+destfile);
bidix.upload.uploadMain(params[0],params[1],params[2]);
} else {
displayMessage(bidix.upload.messages.rssFailed);
}
};
// do uploadRss
if(config.options.chkGenerateAnRssFeed) {
var rssPath = uploadParams[1].substr(0,uploadParams[1].lastIndexOf(".")) + ".xml";
var rssUploadParams = new Array(uploadParams[0],rssPath,uploadParams[2],'',uploadParams[4],uploadParams[5]);
var rssString = generateRss();
// no UnicodeToUTF8 conversion needed when location is "file" !!!
if (document.location.toString().substr(0,4) != "file")
rssString = convertUnicodeToUTF8(rssString);
bidix.upload.httpUpload(rssUploadParams,rssString,callback,Array(uploadParams,original,posDiv));
} else {
bidix.upload.uploadMain(uploadParams,original,posDiv);
}
};
bidix.upload.uploadMain = function(uploadParams,original,posDiv)
{
var callback = function(status,params,responseText,url,xhr) {
var log = new bidix.UploadLog();
if(status) {
// if backupDir specified
if ((params[3]) && (responseText.indexOf("backupfile:") > -1)) {
var backupfile = responseText.substring(responseText.indexOf("backupfile:")+11,responseText.indexOf("\n", responseText.indexOf("backupfile:")));
displayMessage(bidix.upload.messages.backupSaved,bidix.dirname(url)+'/'+backupfile);
}
var destfile = responseText.substring(responseText.indexOf("destfile:")+9,responseText.indexOf("\n", responseText.indexOf("destfile:")));
displayMessage(bidix.upload.messages.mainSaved,bidix.dirname(url)+'/'+destfile);
store.setDirty(false);
log.endUpload("ok");
} else {
alert(bidix.upload.messages.mainFailed);
displayMessage(bidix.upload.messages.mainFailed);
log.endUpload("failed");
}
};
// do uploadMain
var revised = bidix.upload.updateOriginal(original,posDiv);
bidix.upload.httpUpload(uploadParams,revised,callback,uploadParams);
};
bidix.upload.httpUpload = function(uploadParams,data,callback,params)
{
var localCallback = function(status,params,responseText,url,xhr) {
url = (url.indexOf("nocache=") < 0 ? url : url.substring(0,url.indexOf("nocache=")-1));
if (xhr.status == 404)
alert(bidix.upload.messages.storePhpNotFound.format([url]));
if ((bidix.debugMode) || (responseText.indexOf("Debug mode") >= 0 )) {
alert(responseText);
if (responseText.indexOf("Debug mode") >= 0 )
responseText = responseText.substring(responseText.indexOf("\n\n")+2);
} else if (responseText.charAt(0) != '0')
alert(responseText);
if (responseText.charAt(0) != '0')
status = null;
callback(status,params,responseText,url,xhr);
};
// do httpUpload
var boundary = "---------------------------"+"AaB03x";
var uploadFormName = "UploadPlugin";
// compose headers data
var sheader = "";
sheader += "--" + boundary + "\r\nContent-disposition: form-data; name=\"";
sheader += uploadFormName +"\"\r\n\r\n";
sheader += "backupDir="+uploadParams[3] +
";user=" + uploadParams[4] +
";password=" + uploadParams[5] +
";uploaddir=" + uploadParams[2];
if (bidix.debugMode)
sheader += ";debug=1";
sheader += ";;\r\n";
sheader += "\r\n" + "--" + boundary + "\r\n";
sheader += "Content-disposition: form-data; name=\"userfile\"; filename=\""+uploadParams[1]+"\"\r\n";
sheader += "Content-Type: text/html;charset=UTF-8" + "\r\n";
sheader += "Content-Length: " + data.length + "\r\n\r\n";
// compose trailer data
var strailer = new String();
strailer = "\r\n--" + boundary + "--\r\n";
data = sheader + data + strailer;
if (bidix.debugMode) alert("about to execute Http - POST on "+uploadParams[0]+"\n with \n"+data.substr(0,500)+ " ... ");
var r = doHttp("POST",uploadParams[0],data,"multipart/form-data; ;charset=UTF-8; boundary="+boundary,uploadParams[4],uploadParams[5],localCallback,params,null);
if (typeof r == "string")
displayMessage(r);
return r;
};
// same as Saving's updateOriginal but without convertUnicodeToUTF8 calls
bidix.upload.updateOriginal = function(original, posDiv)
{
if (!posDiv)
posDiv = locateStoreArea(original);
if((posDiv[0] == -1) || (posDiv[1] == -1)) {
alert(config.messages.invalidFileError.format([localPath]));
return;
}
var revised = original.substr(0,posDiv[0] + startSaveArea.length) + "\n" +
store.allTiddlersAsHtml() + "\n" +
original.substr(posDiv[1]);
var newSiteTitle = getPageTitle().htmlEncode();
revised = revised.replaceChunk("<title"+">","</title"+">"," " + newSiteTitle + " ");
revised = updateMarkupBlock(revised,"PRE-HEAD","MarkupPreHead");
revised = updateMarkupBlock(revised,"POST-HEAD","MarkupPostHead");
revised = updateMarkupBlock(revised,"PRE-BODY","MarkupPreBody");
revised = updateMarkupBlock(revised,"POST-SCRIPT","MarkupPostBody");
return revised;
};
//
// UploadLog
//
// config.options.chkUploadLog :
// false : no logging
// true : logging
// config.options.txtUploadLogMaxLine :
// -1 : no limit
// 0 : no Log lines but UploadLog is still in place
// n : the last n lines are only kept
// NaN : no limit (-1)
bidix.UploadLog = function() {
if (!config.options.chkUploadLog)
return; // this.tiddler = null
this.tiddler = store.getTiddler("UploadLog");
if (!this.tiddler) {
this.tiddler = new Tiddler();
this.tiddler.title = "UploadLog";
this.tiddler.text = "| !date | !user | !location | !storeUrl | !uploadDir | !toFilename | !backupdir | !origin |";
this.tiddler.created = new Date();
this.tiddler.modifier = config.options.txtUserName;
this.tiddler.modified = new Date();
store.addTiddler(this.tiddler);
}
return this;
};
bidix.UploadLog.prototype.addText = function(text) {
if (!this.tiddler)
return;
// retrieve maxLine when we need it
var maxLine = parseInt(config.options.txtUploadLogMaxLine,10);
if (isNaN(maxLine))
maxLine = -1;
// add text
if (maxLine != 0)
this.tiddler.text = this.tiddler.text + text;
// Trunck to maxLine
if (maxLine >= 0) {
var textArray = this.tiddler.text.split('\n');
if (textArray.length > maxLine + 1)
textArray.splice(1,textArray.length-1-maxLine);
this.tiddler.text = textArray.join('\n');
}
// update tiddler fields
this.tiddler.modifier = config.options.txtUserName;
this.tiddler.modified = new Date();
store.addTiddler(this.tiddler);
// refresh and notifiy for immediate update
story.refreshTiddler(this.tiddler.title);
store.notify(this.tiddler.title, true);
};
bidix.UploadLog.prototype.startUpload = function(storeUrl, toFilename, uploadDir, backupDir) {
if (!this.tiddler)
return;
var now = new Date();
var text = "\n| ";
var filename = bidix.basename(document.location.toString());
if (!filename) filename = '/';
text += now.formatString("0DD/0MM/YYYY 0hh:0mm:0ss") +" | ";
text += config.options.txtUserName + " | ";
text += "[["+filename+"|"+location + "]] |";
text += " [[" + bidix.basename(storeUrl) + "|" + storeUrl + "]] | ";
text += uploadDir + " | ";
text += "[[" + bidix.basename(toFilename) + " | " +toFilename + "]] | ";
text += backupDir + " |";
this.addText(text);
};
bidix.UploadLog.prototype.endUpload = function(status) {
if (!this.tiddler)
return;
this.addText(" "+status+" |");
};
//
// Utilities
//
bidix.checkPlugin = function(plugin, major, minor, revision) {
var ext = version.extensions[plugin];
if (!
(ext &&
((ext.major > major) ||
((ext.major == major) && (ext.minor > minor)) ||
((ext.major == major) && (ext.minor == minor) && (ext.revision >= revision))))) {
// write error in PluginManager
if (pluginInfo)
pluginInfo.log.push("Requires " + plugin + " " + major + "." + minor + "." + revision);
eval(plugin); // generate an error : "Error: ReferenceError: xxxx is not defined"
}
};
bidix.dirname = function(filePath) {
if (!filePath)
return;
var lastpos;
if ((lastpos = filePath.lastIndexOf("/")) != -1) {
return filePath.substring(0, lastpos);
} else {
return filePath.substring(0, filePath.lastIndexOf("\\"));
}
};
bidix.basename = function(filePath) {
if (!filePath)
return;
var lastpos;
if ((lastpos = filePath.lastIndexOf("#")) != -1)
filePath = filePath.substring(0, lastpos);
if ((lastpos = filePath.lastIndexOf("/")) != -1) {
return filePath.substring(lastpos + 1);
} else
return filePath.substring(filePath.lastIndexOf("\\")+1);
};
bidix.initOption = function(name,value) {
if (!config.options[name])
config.options[name] = value;
};
//
// Initializations
//
// require PasswordOptionPlugin 1.0.1 or better
bidix.checkPlugin("PasswordOptionPlugin", 1, 0, 1);
// styleSheet
setStylesheet('.txtUploadStoreUrl, .txtUploadBackupDir, .txtUploadDir {width: 22em;}',"uploadPluginStyles");
//optionsDesc
merge(config.optionsDesc,{
txtUploadStoreUrl: "Url of the UploadService script (default: store.php)",
txtUploadFilename: "Filename of the uploaded file (default: in index.html)",
txtUploadDir: "Relative Directory where to store the file (default: . (downloadService directory))",
txtUploadBackupDir: "Relative Directory where to backup the file. If empty no backup. (default: ''(empty))",
txtUploadUserName: "Upload Username",
pasUploadPassword: "Upload Password",
chkUploadLog: "do Logging in UploadLog (default: true)",
txtUploadLogMaxLine: "Maximum of lines in UploadLog (default: 10)"
});
// Options Initializations
bidix.initOption('txtUploadStoreUrl','');
bidix.initOption('txtUploadFilename','');
bidix.initOption('txtUploadDir','');
bidix.initOption('txtUploadBackupDir','');
bidix.initOption('txtUploadUserName','');
bidix.initOption('pasUploadPassword','');
bidix.initOption('chkUploadLog',true);
bidix.initOption('txtUploadLogMaxLine','10');
// Backstage
merge(config.tasks,{
uploadOptions: {text: "upload", tooltip: "Change UploadOptions and Upload", content: '<<uploadOptions>>'}
});
config.backstageTasks.push("uploadOptions");
//}}}
!Constraint solving in uncertain and dynamic environments: A survey
Paper surveys frameworks and methods for solving constraint satisfaction problems that change underway or contain uncertainties.
The authors identify four kind of requirements that crop up in uncertain environments, namely the need
*to limit successive online problem solving,
*to limit the changes in the solutions produced,
*to limit the resources necessary for online solving, and
*to keep producing consistent and optimal solutions.
All these are not present in every type of uncertain CSP, and they may conflict.
Several things are presented: Various frameworks for modeling uncertainty , and two classes of methods, ''reactive'' and ''proactive'', for solving problems with uncertainty.
!!Frameworks
These frameworks model problems where possible changes are known, but may or may not occur. One such framework is the Dynamic CSP framework, different from the DCSP framework of MittalFalkenhainer1990. Here we deal with a sequence of CSPs, for example in time, where we can add and remove constraints from each successive CSP. This is also not the same as OCSP, where constraints are relaxed as new values are gathered from multiple sources.
Another type of frameworks deal with uncertainties in the real-world information we have. One is Mixed CSPs, where we allow ''uncontrollable variables'' that we may not assign. A typical problem this framework tries to solve is to find an assignment to variables we can assign that is consistent with any assignment to the uncontrollable variables.
A similar problem is handled by Probabilistic CSPs, where each constraint has a probability associated with it, and models the likelihood of that constraint being imposed. This can be seen as a case of Valued CSPs. Likewise, Stochastic CSPs deal with probability distributions over the values of variables. Finally, Branching CSPs try to maximize utility of the assignment as new variables arrive.
!!Reactive methods
These methods solve problems where no knowledge of possible changes is assumed. The aim is to re-use as much as possible of previous solutions and failed attempts. This falls into two broad classes, consistency and inconsistency information. The former is preserved under relaxation, while the latter is preserved by problem restriction. The authors discuss various methods for both cases and their combination.
!!Proactive methods
These methods try to use all available information about future changes to find either ''robust'' or ''flexible'' solutions. A robust solution is designed to stay valid as long as possible as changes happen, while a flexible solution is designed to be easily changeable to accommodate new changes. The authors discuss various methods that handle this.
Finally, the authors conclude the paper with an outline of possible research directions and provide a wealth of references.
This document is a ~TiddlyWiki from tiddlyspot.com. A ~TiddlyWiki is an electronic notebook that is great for managing todo lists, personal information, and all sorts of things.
@@font-weight:bold;font-size:1.3em;color:#444; //What now?// @@ Before you can save any changes, you need to enter your password in the form below. Then configure privacy and other site settings at your [[control panel|http://evgenit.tiddlyspot.com/controlpanel]] (your control panel username is //evgenit//).
<<tiddler TspotControls>>
See also GettingStarted.
@@font-weight:bold;font-size:1.3em;color:#444; //Working online// @@ You can edit this ~TiddlyWiki right now, and save your changes using the "save to web" button in the column on the right.
@@font-weight:bold;font-size:1.3em;color:#444; //Working offline// @@ A fully functioning copy of this ~TiddlyWiki can be saved onto your hard drive or USB stick. You can make changes and save them locally without being connected to the Internet. When you're ready to sync up again, just click "upload" and your ~TiddlyWiki will be saved back to tiddlyspot.com.
@@font-weight:bold;font-size:1.3em;color:#444; //Help!// @@ Find out more about ~TiddlyWiki at [[TiddlyWiki.com|http://tiddlywiki.com]]. Also visit [[TiddlyWiki.org|http://tiddlywiki.org]] for documentation on learning and using ~TiddlyWiki. New users are especially welcome on the [[TiddlyWiki mailing list|http://groups.google.com/group/TiddlyWiki]], which is an excellent place to ask questions and get help. If you have a tiddlyspot related problem email [[tiddlyspot support|mailto:support@tiddlyspot.com]].
@@font-weight:bold;font-size:1.3em;color:#444; //Enjoy :)// @@ We hope you like using your tiddlyspot.com site. Please email [[feedback@tiddlyspot.com|mailto:feedback@tiddlyspot.com]] with any comments or suggestions.
"X with no surprises": The standard, obvious, or simple way of doing X.
The plural of "anecdote", to be distinguished from real data.
Interesting terms and concepts.