text:
# Compiler and Interpreter Technology

Thursday, January 19th, 2017

NFA

Lexical AnalaysisScanner Generation
NFA machine classUsing Flex
Translation of regex into NFAWhitespace
Simulation of NFA.Strings

# 1. Lexical Analysis

#include<stdio.h> int main(int argc, char **argv) { printf("Pizza is nice, but I like %f.\n", 3.1415); return 0; }
#include<stdio.h>intmain(intargc

,char**argv){printf(

"Pizza is nice, but I like %f.\n");}
• The first step in understanding a string as a program is Lexical Analysis.
• "Lexing" splits a string into pieces called "lexemes"; the smallest logical units.
• In most programming languages these are literals, keywords, identifiers etc.
• These are "smallest units" because if we split them any further they lose their meaning.
• e.g. for is a keyword, but ffo or or are not.
• e.g. 3.145 denotes a specific number, 3.1 is a different value.
• e.g. -= is a specific operator, - is a different operation.

# 2. Lexeme Boundaries

• Lexical Analysis is performed by scanning the input string in some way.
• Hence the interchangable names lexer / scanner in most materials.
• The input is a string of symbols, the output is a string of lexemes.
• The scanner looks at each symbol in turn to make a decision.
Scanning decision
Is this symbol part of the current lexeme?
Equivalent problem
Where are the boundaries between lexemes?
• It is important to understand that these are completely equivalent phrasings of the same problem:
Boundary decision
Where is the beginning and ending of each lexeme?

# 3. Textbook Confusion

• Chapter 3 is correct but unhelpful, "road to hell is paved with good intentions"...
• It is normal for students reading this chapter to feel a little lost.
• The author's intention is roughly as follows:
• §3.3 Provide input context by introducing tokens we are familiar with.
• §3.4 Provide output context by specifying a parser to use the scanner.
• §3.4 & §3.5 Use transition diagrams to explain control flow inside the scanner.
• §3.5 Introduce Lex
• §3.6 Introduce the real theory.
• Providing context should aid learning, but forward references are awkward:
• Unfortunately the transition diagrams use explicit boundary condition.
• They check one more symbol after the lexeme to make sure it is finished.
• The real digraph formulation uses implicit boundary conditions.
• Lecture 2: slides 24-25 peek at the current symbol in the default case.

# 4. Implicit vs Explicit Boundary Conditions

• A boundary between two things implies that they are different in some way.
• We cannot split identifiers into abcdef.
• So neighbouring lexemes must have recognisable differences in start/tokens.
• When this is tricky we introduce an explicit separator to split them.
• Whitespace fulfils this role in most languages.
• We may keep the separators as lexemes (if they have some significance).
• Or just discard them if their content has no extra meaning.
• This comes up in the labs when we split bash command-lines into words.
• Insignificant whitespace appears in bash and many functional languages.
• e.g. func x y z The identifier splitting is important.
• Significant whitespace appears in python, haskell:
• The number of spaces in the indent defines nesting.

# 5. Tokens

intmain(intargc,char**
keyword:intid:mainpopenkeyword:intid:argc...
• The lexemes recognised are split into different sets (identifiers, literals etc).
• Each set is given a label (tag), normally they are integers in a enum.
• The tagged value is called a token.
• Scanner generators place different types of values into a token (union).
• e.g In flex we can decode a literal into an integer, a double, a string...
• The idea is to do some of the decoding of the string for the parser later.
• This is needlessly overcomplicated and it breaks type safety.
• "But its always been done that way!"
• It is a permature optimisation from an era where the bandwidth between the scanner and parser was a real bottleneck that has become a standard.
• Always pass strings. Decode to values inside the parser. It just works™

# 6. Problem statement: From matching to lexing.

• Matching a regular expression against a string has two outcomes: accept / reject.
• Searching tries to match at every position: accept@0 / accept@1... / reject.
• Lexing partitions (splits) a string according to a set of regular expressions.
• So every symbol is in exactly one lexeme if the lexer succeeds.
• The process must be unambiguous (pg113), consider:
• A set of regex [0-9]+, [0-9]+\.[0-9]*, \.[0-9]+xx and x+.
• Should 3.14xx be lexed as 3.14xx or as 3.14xx ?
• Avoid ambiguity: take the longest valid lexeme left-to-right.
• This rule breaks ties: lexeme matching is greedy.
• This means that lexeme boundaries can always be implicit.
Lexing Problem Statement
Given a set of regexes and a string output an unambiguous string of tokens.

# 7. Machine class: Nondeterministic Finite Automata

• We know from the last lecture how to convert a regex into a DFA.
• We need to build a machine from a set of regexs.
• Naive approach:
• Build one DFA per regex, glue together.
• Given state unique labels.
• Accepting have token tag.
• Problem:
• Arrow labels no longer unique.
• How do we choose the next state?
• Seems like we need to know what comes after, breaks the way the tape works.

# 8. Machine class: Nondeterministic Finite Automata

• Solution: change the rules for the machine.
• Drop the requirement that arrows from a state must have unique edges.
• When we encounter multiple arrows on the same symbol - follow all of them.
• No longer have a single current active state.
• We have a set of active states.
• For each step of the machine we check if we can follow an arrow from any current state.
• §3.6.1 differs slightly.
• I am avoiding $$\epsilon$$ transition in this explanation.
• They are there to make proofs about NFA construction easier, but can be removed.
• Note: the transition function $$State \times \Sigma \rightarrow State$$ is partial.

# 9. Machine class: NFA Termination

• When multiple regular expressions match, the NFA must choose the longest.
• (the rule for avoiding ambiguity from earlier).
• How do we know when to stop?
• Consider the int/float example.
• If we encounter 3. then we do not know it is an int...
• ...until we discover it is not a float because we are stuck in state 2.
• The explanation is in § 3.8.2.
• We record the steps that the machine takes, and always run until we get stuck.
• Then we walk backwards through the trace until we find an accepting state.
• This has to be the longest, so we accept the token with that tag.
• This trace memory makes the machine more complex than the raw DFA.
• But recovering the lexeme already required trace memory.

# 10. Language class: NFA vs DFA

• It is natural to see NFA as an extension of DFA.
• Tracking multiple states at once is a form of speculation.
• Testing possible matches and discarding when impossible.
• This is equivalent to peeking forward in the stream...
• So it would seem to be a more powerful machine?
• A more powerful machine would recognise a larger language.
• But surprisingly it is not so.
• Both DFAs and NFAs recognise exactly the regular expressions.
• This is proven using "the powerset construction". §3.7.1
• The proof is constructive so it leads directly to a conversion algorithm.
• Simple intuitive explanation of the proof:
• We can combine a set of regexs using the choice operator regex1|regex2|... and the result is still a regex.

# 11. Translation:

• How to convert a set of regular expressions into an NFA.
• Could use the algorithm in § 3.7.4.
• But it looks very long and complicated...
• Luckily most of the details are concerned with correctness in corner cases.
• And the use of $$\epsilon$$-transitions to preserve structure seems redundant.
• A simpler explanation:
• Use the DFA construction table from the last lecture.
• Root every NFA on the same initial state (as on slide 7).
• Don't try and merge equivalent paths in the graph at all.
• The constructed NFA may be less efficient than § 3.7.4, but only in pathological cases.
• This is a case of something being easier in practice than in theory.

# 12. Simulation: Speculation

• I will only give a simple sketch of how to do this (inefficently).
• Mainly, because in practice we would convert it to a DFA for execution.
set<State*> now, next; void step() { next.eraseall(); for each state in now for each transition in state if symbol matches head add target state to next set consume flag if(consume) now = next; // Double-buffering return consume flag }
• If you want to see real code: lookup computing the transitive closure on a graph.

# 13. Simulation: By conversion to DFA

• The details are in § 3.7.1., the basic idea:
• Identify each set of states on the NFA that we can be in.
• Each set becomes a single state in the DFA that we build.
• Hence, "powerset construction".
• Worst case can blow up $$O(2^n)$$, but that doesn't tend to happen.
• Avoid simple merging of paths that extend language.
 NFA %3 0 0 1 1 0->1 [a,b] 2 2 0->2 b 3 3 2->3 b Bad conversion: accepts ab. %3 0 0 1 1 0->1 a,b 2 2 1->2 b Good conversion: same language. %3 0 0 1 1 0->1 a 2 1,2 0->2 b 3 3 2->3 b

# 14. Simulation: Running the DFA

• Last detail is how to execute the generated DFA.
• Multiple accepting states: one for each token.
• Need to land in the correct one, means looking ahead to decide.
• Instead execute the DFA until it rejects (no more transitions).
• Record each state reached in a list.
• On reject rewind the stream and the list looking for last accept.
• This is the longest valid match.
• If there are no accepting states in the list: reject as a syntax error.
• Otherwise, output the token and start again.
• Result is a list of tokens (maybe with an error).

Intermission

# 15. Lexer generation as compilation

• Summary of lexical analysis so far:
• Tokens are defined in a simple language (regular expressions).
• Convert definitions into an executable machine.
• Algorithm to merge separate machines into a single scanner.
• Convert scanner definition into executable code.
• Operations on the machine are tractable because the language is simple.
• It is possible to automate the steps into a tool.
• Allows creation of larger (more complex) languages.
• Interface to the tool is the language to define tokens.
• Running the tool outputs the code of a scanner.
• The tool itself is the first compiler on the course.
regular expressions -> DFAs -> NFAs -> DFA -> C

# 16. Tools: Lex / Flex

• Lex is a standard tool to generate scanners.
• In the labs we will probably use flex (exactly same format).
• Input file takes the format:
Definitions (names for regexs) %% Rules (processed by lex) %% Code (C copied directly into generated scanner)
• To build the scanner code is a two-step process:
• flex filename.lex Outputs into a file called lex.yy.c
• gcc lex.yy.c -lf Build the scanner code

# 17. A Flex example

• As a first example we create a file hex.lex, thusly:
DIG [0-9a-f] %% 0x{DIG}+ %% int main(int argc, char **argv) { yylex(); }
• Meaning should be intuitively obvious :) Just in case...
• We give a name to a regular expression (similar to a macro)
• This name is expanded within a regex to define a single token rule.
• The C program entry point just calls the lexer entry point.

# 18. Executing the example

• So now we build the scanner and test it:
flex hex.lex

gcc yy.lex.c -lfl

./a.out

No output, but prompt changes

blahBXY0xff+0x01211ffffG

Output: blahBXY+G

• If we type in other strings we can verify that hex values are deleted.
• Default input stream is stdin, processed per block.
• Control-d ends the stream and closes the scanner.
• Unprocessed characters seem to be echoed.
• Recognised tokens are consumed (discarded).
• Somewhat important to get at the tokens we want...

# 19. Retrieving the tokens

• Flex avoids defining a datatype for tokens and providing an API.
• As a code generator the output is designed to be embedded.
• Avoid the complexity of memory management, and overhead of calls.
• Insert code directly into the generated scanner.
DIG [0-9a-f] %% 0x{DIG}+ { printf("Tok: %s\n", yytext); } %% int main(int argc, char **argv) { yylex(); }

# 20. Code insertion

0x{DIG}+ { printf("Tok: %s\n", yytext); }
case 1: YY_RULE_SETUP #line 3 "hex.lex" { printf("Tok: %s\n",yytext); } YY_BREAK
• The generated code is large - 1749 lines.
• We don't need to read or understand it - generated code is ugly.
• We do need to understand how it links into the code we write.
• The fragments are being placed directly into a switch-case jump table.
• The #line macro should affect error messages.
• Instead of an API/data-structure, call arbitrary code to process tokens.

• Comments are sections of a program for the compiler to ignore.
• Each language has different styles, but they fall into two groups.
• e.g. C++ using //, in shell using #
• Problem with newline: interaction with whitespace tokens.
• Problem with escapes: continues comment past newline.
• C-style with /* ... */, html using <! .... >
• Problem with nesting:/* new comment /* old code */ stuff */
• Where does the comment end?
• In both cases the issue lies with the boundary between lexing and parsing.
• Sequences of (nesting of) tokens should lie in the parser.
• Nothing inside a comment should generate an error...

# 22. Common constructs: comments II

• There are no elegant solutions.
• There are approaches that work.
• Consume the entire comment as a single token up to the newline.
• We can consume \\n within the regex, continue to newline.
• Just ignore nesting (standard approach for C compilers).
• Accept everything, let parser handle nesting (some C++ compilers).
• Hack a counter into the lexical grammar (yay, embedded code!).
• It may seem ugly to hack into the lexer to circumvent language restrictions...
• ...but as we will see this needs to be done anyway!

# 23. Common constructs: whitespace

• It is important to recognise whitespace:
• Although it does not change the meaning of program text - ignore it.
• It does frame/surround meaningful tokens - process it.
• Identical: x+y, x +y, x\n+ y
• Different: intx, int\nx, in tx
• Normal solution: do both.
• Whitespace tokens defined in the lexical grammar.
• Separate discard channel to remove from normal output.
• Channel may be read by some tools: doxygen, literate programming, program analysis...
• This is called non-significant whitespace.

# 24. Common constructs: whitespace II

• Then there is the other kind of whitespace: significant whitespace.
• Python and Haskell are example of languages that use this.
• The indenting of each line is recognised.
• Replaces explicit block delimiters { ... }
• Scanner needs to record the indenting level of each line.
• This gets tricky... scanner is not line based, can't do:
• ^ * { emit(INDENT,strlen(yytext)); }
• Without the anchor every block of spaces becomes an INDENT
• Kind of do it with something like:
• \n * { emit(INDENT,strlen(yytext)-1); }
• But, misses the first line, not all newlines count...
• In general this is an example of context-sensitivity that does not fit.
• Real world solutions involve making ugly lexer/parser hacks.

# 25. Common constructs: strings

• Strings are the other difficult token in lexing.
• Note: whitespace, comments and strings all have variable-length.
• Should newlines be significant? c-strings vs Python.
• Escaping, quoting and all that mess.
• How should they interact with line continuations?
• Are comment characters inside strings valid?

# 26. Common constructs: the lexer hack

• So far we have seen a neat elegant theory.
• Leads to powerful automatic tools.
• There are limitations to the language power...
• ... but surely designers would work within them?
• Let's take a closer look at something in C.
• typedef unsigned long long Uint64; Uint64 x; int Uint64;
• This is called the "typedef problem" and it is normally resolved by the "lexer hack".
• Parsers are the topic next week
• Something to keep in mind is that the information they produce can be necessary in the lexer.
• This feedback loop requires tight coupling between them.

# 27. Summary

• Summary:
• We have seen the theory of how lexical analysis works.
• The differences between DFAs and NFAs, how they are constructed and used.
• We have seen a brief introduction to using flex to build scanners.
• The syntax of flex is the same as that of lex.
• There is an intro to lex in § 3.5, this applies to flex.
• These are very old tools (lex was a PhD thesis in the 70s).
• The interface has always been coroutines by code injection in C...
• The flex and bison support for C++ is becoming much more robust.
• The labs will show how to use both C / C++ for building scanners / parsers.
• There are more worked exercises in the labs to build experience of flex.
• Next week we look at parsers and building them from bison...


text:
Accelerating the pace of engineering and science

# comm.OQPSKDemodulator System object

Package: comm

Demodulate using OQPSK method

## Description

The OQPSKDemodulator object demodulates a signal that was modulated using the offset quadrature phase shift keying method. The input is a baseband representation of the modulated signal.

To demodulate a signal that was modulated using offset quadrature phase shift keying:

1. Define and set up your OQPSK demodulator object. See Construction.

2. Call step to demodulate the signal according to the properties of comm.OQPSKDemodulator. The behavior of step is specific to each object in the toolbox.

## Construction

H = comm.OQPSKDemodulator creates a demodulator System object™, H. This object demodulates the input signal using the offset quadrature phase shift keying (OQPSK) method.

H = comm.OQPSKDemodulator(Name,Value) creates an OQPSK demodulator object, H, with each specified property set to the specified value. You can specify additional name-value pair arguments in any order as (Name1,Value1,...,NameN,ValueN).

H = comm.OQPSKDemodulator(PHASE,Name,Value) creates an OQPSK demodulator object, H. This object has the PhaseOffset property set to PHASE and the other specified properties set to the specified values.

## Properties

 PhaseOffset Phase of zeroth point of constellation from $\pi }{4}$ Specify the phase offset of the zeroth point of the constellation shifted from $\pi }{4}$, in radians, as a finite, real-valued scalar. The default is 0. BitOutput Output data as bits Specify whether the output consists of groups of bits or integer values. The default is false. When you set this property to true the step method outputs a column vector of bit values. The vector length must equal to twice the number of demodulated symbols. When you set this property to false, the step method outputs a column vector. The length of this vector equals to the number of demodulated symbols that contain integer values between 0 and 3. The object produces one output demodulated symbol for each pair of input samples. OutputDataType Data type of output Specify output data type as Full precision | Smallest unsigned integer | double | single | int8 | uint8 | int16 | uint16 | int32 | uint32. The default is Full precision. When you set this property to Full precision, the step method output inherits the data type from the input. When the input is of single or double data, the step method outputs the same data type as the input. When the input data is of a fixed-point type, then the step method outputs the same data type as if you set the OutputDataType property to Smallest unsigned integer. When you set the BitOutput property to true, the logical data type becomes a valid option. When the input signal is an integer data type, you must have a Fixed-Point Designer™ user license to use this property in Smallest unsigned integer or Full precision mode.

## Methods

 clone Create OQPSK demodulator object with same property values constellation Calculate or plot ideal signal constellation getNumInputs Number of expected inputs to step method getNumOutputs Number of outputs from step method isLocked Locked status for input attributes and nontunable properties release Allow property value and input characteristics changes reset Reset demodulator state step Demodulate using OQPSK method

## Examples

Modulate and demodulate a signal using OQPSK modulation with a constellation with pi/8 radians of phase offset.

```    hMod = comm.OQPSKModulator(pi/8);
hAWGN = comm.AWGNChannel('NoiseMethod', ...
'Signal to noise ratio (SNR)','SNR',6);
hDemod = comm.OQPSKDemodulator(pi/8);
% Create an error rate calculator, account for the one symbol delay
for counter = 1:100
% Transmit a 50-symbol frame
data = randi([0 3],50,1);
modSignal = step(hMod, data);
noisySignal = step(hAWGN, modSignal);

format: plain


text:
# Help Finishing Proof Involving Collinearity and Cyclic Quads

Problem: Let $D$, $E$ and $F$ be the points of tangency between the incircle of triangle $ABC$ and the sides $BC, CA,$ and $AB$. Let $M$ and $N$ be the feet of the perpendiculars from $B$ onto $CI$, and from $C$ onto $BI$, respectively. Prove that the points $M, D, E,$ and $N$ are collinear.

So Far I have:

Since $BMDI$ is a cyclic quadrilateral this implies that $\angle BMI = 90^\circ = \angle BDI$.

We know that $\angle MDI + \angle MBI = 180^\circ$. Denote $\angle MDB = \theta$. Then $\angle MBI = 90^\circ - \theta$.

If we can only prove: $\angle MDI + \angle IDE = 180^\circ$, then we can prove $M, D, E$ are collinear. (and then use a similar method to prove $D, E, N$ collinear).

$\triangle BDI \equiv \triangle BFI$ by HL so $\angle DBI = 90^\circ - \theta - \beta = \angle FBI$ ($\beta = \angle MBD$) and $\angle DIB = \angle FIB = \theta + \beta$.

Any help on what I should do next is appreciated]1

It is enough to prove that $M,D,E$ are collinear. After that we can use the same idea and get that $D,E,N$ are also collinear and then $M,D,E,N$ are collinear.

First of al we have that $BIDM$ is cyclic because $\angle BMI=\angle BDI (=90°)$, so $$\angle MDI=180°-\angle MBI.\quad (*)$$

We then need to prove that $\angle IDE=\angle MBI$.

$1)$ By sum of angle in $\Delta BIC$ we get $\angle BIC=180°-\frac{\angle ABC+ \angle ACB}{2}=90°+\frac{\angle BAC}{2}$. But we also have that, by exterior angle theorem at $\Delta BMI$, $\angle BIC=90°+\angle MBI$, so $$\angle MBI=\frac{\angle BAC}{2}$$.

$2)$ In the quadrilateral $ADIE$ we get $\angle DIE=180°-\angle BAC$ and from the isosceles triangle $IDE$ we get $$\angle IDE=\frac{1}{2}(180°-\angle DIE)=\frac{\angle BAC}{2}$$.

And then, from $(1)$ and $(2)$ we get $\angle IDE=\angle MBI$ and backing to $(*)$ we get:

$$\angle MDI+\angle IDE=180°-\angle MBI+\angle MBI=180°$$

so, $M,D,E$ are collinear.

• How did you determine that $\angle BIC - 180^\circ - \displaystyle\frac{\angle ABC + \angle ACB}{2}$ @Arnaldo May 17 '17 at 16:48
• @rover2: sum of angles in $\Delta BIC$ May 17 '17 at 16:51
• so due to the fact that $\triangle BDI \equiv \triangle BFI$ implying that $\angle DBI = \angle FBI$ that means that $\angle FBI = \frac{1}{2} \angle ABC$ right? May 17 '17 at 16:59
• @ you are right! May 17 '17 at 17:03
• @Sorfosh: Ok, sorry. It is because $\angle ADI +\angle AEI=90°+90°=180°$ May 17 '17 at 22:55


text:
# Metric Spaces of Continuous Function

Let X be a metric space defined as such: $$X = f : [0,1] \to \Re : f \,\text{ is continuous}$$ $$d(f,g) = sup_{x\in[0,1]} | f(x) - g(x)|$$

I need to show:
a) The neighborhood, $N_r (0)$, is uncountably infinite.
b) Let E = { $f \in X : f(0) = 0$}. Prove or disprove E is bounded
c)Prove X is not complete (I can't comment, but yes I need to prove it is not complete)

I am not looking for someone to solve the problem for me, Just to point me in the right direction. I think this is saying that X is a metric space of function (?). I don't believe I've run into this before and don't know how to approach this. Any help would be greatly appreciated.

-
$X$ is complete. Surely whoever gave you this problem made a typo. –  David Mitra Jan 14 '13 at 1:01
add comment

## 1 Answer

You need to think abstractly so as not to get confused with the fact that the points in the metric space you consider are themselves functions. You can still think metrically about this situation since the metric defines the distance between such functions and the axioms of a metric space are satisfied.

To solve this problem you need to make sure you understand what each and every term means and then translate it to the problem at hand. So, for instance, the neighborhood $N_r(0)$ means (I'm guessing here) the set $\{f\in X \mid d(f,0) < r \}$. So, for the case at hand, $0$ probably means the constantly $0$ function. Further, $d(f,0)$ is, by definition, $\sup_x|f(x)|$. So, $N_r(0)=\{f\in X\mid \sup_x |f(x)|<r\}$.

For every $0<\epsilon <r$ the function $f(x)=\epsilon$ thus satisfies that $f(x)\in N_r(0)$ and there are uncountably many such functions. Similarly, you proceed with the other items (at least those that are correct).

-
add comment


text:
# Linear time algorithm for finding $k$ shortest paths from $s$ to $t$

Definition. Given a graph $G=(V,E)$ and two vertices $s$ and $t$, the $k$-shortest-paths problem is finding the $k$ shortest simple paths between $s$ and $t$ in $G$.

Note that the length of these paths is not necessarily equal, and vertices $s$ and $t$ are necessarily $k$-connected. I was wondering if there is a linear time (in terms of $n$ and $m$) algorithm for this problem.

I have looked at a few papers in the literature, such as "A New Implementation Of Yen's Ranking Loopless Paths Algorithm" but the time complexity is really high $O(Kn(m+nlogn))$. Also, the other paper by Epstein "Finding the k shortest paths" presents an algorithm that finds the $k$ shortest paths that are not necessarily simple paths with running time $O(n+m+k)$.

Is there a linear-time algorithm for the $k$-simple-shortest-paths problem?

• @D.W. Eppstein's algorithm finds paths which are not necessarily simple. OP wants a similar algorithm, possibly in the same running time, that finds the $k$ shortest simple paths. Yen's ranking algorithm is too slow for that. – Yuval Filmus Jul 6 '16 at 6:38

First of all, the answer that applies here was already given by Raphael in the comments to the question: "Given that we don't even know how to find one simple shortest path in linear time, I doubt it." In the following, thus, I will assume you are interested in knowing about the best available algorithms in the current state of the art. In the following, I describe the best worst-case bound (to the best of my knowledge) but also an algorithm that might run in linear time in some specific cases.

But before describing the latest developments in the state of the art, I wanted to emphasize the importance of simple paths in this specific problem. As a matter of fact, many people overlooks the importance of this requirement and some do not even understand it at first glance.

When computing the shortest path from a start vertex to a goal vertex, the optimal path is necessarily simple, i.e., it does not repeat any vertices. However, when computing $k$ optimal paths, the second, third, ... best paths might not be simple. To prove it, I provide here an example that has been slightly adapted from Hershberger, Maxel & Suri, 2007:

The Figure shows a digraph whose optimal solution (from the source vertex $s$ to the goal vertex $t$) is the path $\pi_1 : \langle s, A, B, C, D, t\rangle$ with a cost equal to 5. If paths are not required to be simple, then the second and third optimal paths are $\pi_2 : \langle s, A, B, C, D, C, D, t\rangle$ and $\pi_3 : \langle s, A, B, A, B, C, D, t\rangle$ both with a cost equal to 7. However, if paths are required to be simple, then the second and third optimal paths would be $\pi_2 : \langle s, F, t\rangle$ and $\pi_3 : \langle s, G, t\rangle$ with costs 10 and 11, respectively.

Given a graph $G(V, E)$ where $V$ is the set of vertices and $\langle u, v\rangle\in E, u, v\in V$ if there is an edge between vertices $u$ and $v$, the current state of the art for this problem to the best of my knowledge is described below:

The first significant improvement to solve the $k$ optimal paths problem is Eppstein's algorithm (Eppstein, 1998) which runs in $O(|E|+|V|\log |V|+k)$. However, this algorithm requires the graph to be given explicitly. $K^*$ alleviates this requirement while maintaining the low complexity (Aljazzar & Leue, 2011) and, additionally, enables the application of admissible heuristics. In both cases, the output computed by these algorithms are not necessarily simple paths.

In case that paths are required to be simple, the best results is due to Yen (Yen, 1971, 1972), generalized later by Lawler (Lawler, 1972), which using modern data structures can be implemented in $O(k|V|(|E|+|V|\log |V|))$ worst-case time. In the case of undirected graphs, Katoh, Ibaraki and Mine (Katoh, Ibaraki & Mine, 1982) improve Yen's algorithm to $O(k(|E|+|V|\log |V|))$ time. While Yen's asymptotic worst-case bound for enumerating $k$ simple shortest paths in a directed graph remains unbeaten (again, to the best of my knowledge!), several attempts have been done to outperform it in practice.

One of such works is due to John Hershberger et al., who introduced a replacement paths algorithm which is known to fail scarcely. As a result, their algorithm delivers a speedup that grows linearly with the average number of edges in the $k$ shortest paths but, for some cases (as random graphs), this speedup is minimized.

Hope this helps,

Bibliography

Aljazzar, H. & Leue, S. (2011). $K^*$: A heuristic search algorithm for finding the $k$ shortest paths. Artificial Intelligence, 175(18), 2129-2154.

Eppstein, D. (1998). Finding the $k$ shortest paths. SIAM Journal on Computing, 28(2), 652-673.

Hershberger, J., Maxel, M. & Suri, S. (2007). Finding the $k$ shortest simple paths: A new algorithm and its implementation. ACM Transactions on Algorithms, 3(4), 45-46

Katoh, N., Ibaraki, T. & Mine, H. (1982). An efficient algorithm for $k$ shortest simple paths. Networks, 12, 411-427.

Lawler, E. L. (1972). A procedure for computing the $k$ best solutions to discrete optimization problems and its application to the shortest path problem. Management Science, 18, 401-405.

Yen, J.Y. (1971). Finding the $k$ shortest loopless paths in a network. Management Sciences, 17, 712-716.

Yen, J.Y. (1972). Another algorithm for finding the $k$ shortest loopless network paths. Proceedings of 41st Management Operations Research Society of America, 20.

• Thanks, this actually works in $O(n+m)$ in unweighted graphs. In fact, a more recent paper (mentioned in the question) made me think that its running time must be better than Kotah's; it gave me a wrong impression. – orezvani Jul 6 '16 at 11:48
• Happy to hear you like it @kezzos – Carlos Linares López Jan 31 '18 at 8:55


text:
# Schreiber Anyonic topological order in TED K-theory (Rev #11, changes)

Showing changes from revision #10 to #11: Added | Removed | Changed

An article that we are finalizing:

• Hisham Sati, $\;$ Urs Schreiber:

\linebreak

Anyonic topological order in TED K-theory

\linebreak

on extending the K-theory classification of topological phases to anyonic topological order.

Abstract. While the classification of non-interacting crycrystalline topological insulator phases by equivariant K-theory has become widely accepted, its generalization to anyonic interacting phases – hence to phases with topologically ordered ground states supporting topological braid quantum gates – has remained wide open.

On the contrary, the success of K-theory with classifying non-interacting topological phases seems to have tacitly been perceived as precluding a K-theoretic classification of interacting topological order; and instead a mix of other proposals has been explored. However, only K-theory connects closely to the actual physics of valence electrons; and self-consistency demands that any other proposal must connect to K-theory.

Here we provide a detailed argument for the classification of symmetry protected/enhanced $\mathfrak{su}(2)$-anyonic topological order, specifically in interacting 2d semi-metals, by the twisted equivariant differential (TED) K-theory of configuration spaces of points in the complement of nodal points inside the crystal’s Brillouin torus orbi-orientifold.

We argue, in particular, that:

1. topological 2d semi-metal$\;$phases modulo global mass terms are classified by the flat differential twisted equivariant K-theory of the complement of the nodal points;

2. $n$-electron interacting phases are classified by the K-theory of configuration spaces of $n$ points in the Brillouin torus;

3. the somewhat neglected twisting of equivariant K-theory by “inner local systems” reflects the effective "fictitious" gauge interaction of Chen, Wilczeck, Witten & Halperin (1989), which turns fermions into anyonic quanta;

4. the induced $\mathfrak{su}(2)$-anyonic topological order is reflected in the twisted Chern classes of the interacting valence bundle over configuration space, constituting the hypergeometric integral construction of monodromy braid representations.

A tight dictionary relates these arguments to those for classifying defect brane charges in string theory $[$SS22-Any$]$, which we expect to be the images of momentum-space $\mathfrak{su}(2)$-anyons under a non-perturbative version of the AdS/CMT correspondence.

\linebreak

Related articles

\linebreak

\linebreak

Revision on June 29, 2022 at 02:41:53 by Urs Schreiber. See the history of this page for a list of all contributions to it.


text:
# How to change bibliography font size in Latex

Few conferences allow to use separate font size for bibliography. Here is how you can set a different font size for Reference section alone. Place following command before bibliography section:

\def\bibfont{\footnotesize}

You should make sure that you use appropriate command in place of footnotesize e.g., small, large. For example if size of the body text is set to 10pt then footnotesize size will be 8pt. More information about the footnotesize size can be found here.


text:
# Detect if an input has text in it using CSS — on a page I am visiting and do not control?

10/14 07:17

### 问题：

Is there a way to detect whether or not an input has text in it via CSS?有没有办法通过 CSS 检测输入是否包含文本？ I've tried using the :empty pseudo-class, and I've tried using [value=""] , neither of which worked.我试过使用:empty伪类，也试过使用[value=""] ，但都没有奏效。 I can't seem to find a single solution to this.我似乎无法找到解决此问题的单一解决方案。

I imagine this must be possible, considering we have pseudo-classes for :checked , and :indeterminate , both of which are kind of similar thing.我想这一定是可能的，考虑到我们有:checked:indeterminate伪类，两者都是类似的东西。

Please note: I'm doing this for a "Stylish" style , which can't utilize JavaScript.请注意：我这样做是为了“时尚”风格，它不能使用 JavaScript。

Also note, that Stylish is used, client-side, on pages that the user does not control.另请注意，在用户无法控制的页面上使用 Stylish，客户端。

0
0 收藏

0 评论
0 收藏
0


text:
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.

While looking at X validated questions, I came upon this comment that simulating a uniform distribution on a d-dimensional unit sphere does not proceed from generating angles at random on (0,2π) and computing spherical coordinates… Which I must confess would have been my initial suggestion! This is obvious, nonetheless, when computing the Jacobian of the spherical coordinate transform, which involves powers of the sines of the angles, in a decreasing sequence from d-1 to zero. This means that the angles should be simulated according to their respective sine-power densities. However, except for the d=3 case, where simulating from the density sin(φ) is straightforward by inverse cdf, i.e. φ=acos(1-2u), the cdfs for the higher powers are combinations of sines and cosines, and as such are not easily inverted. Take for instance the eighth power:

F⁸(φ)=(840 φ – 672 sin(2 φ) + 168 sin(4 φ) – 32 sin(6 φ) + 3 sin(8 φ))/3072

While the densities are bounded by sin(φ), up to a constant, and hence an accept-reject can be easily derived, the efficiency decreases with the dimension according to the respective ratio of the Wallis’ integrals, unsurprisingly. A quick check for d=4 shows that the Normal simulation+projection-by-division-by-its-norm is faster.

Puzzling a bit further about this while running, I wondered at the simultaneous simulations from sin(φ), sin(φ)², sin(φ)³, &tc., but cannot see a faster way to recycle simulations from sin(φ). Points (φ,u) located in-between two adjacent power curves are acceptable simulations from the corresponding upper curve but they need be augmented by points (φ,u) under the lower curve to constitute a representative sample. In the end, this amounts to multiplying simulations from the highest power density as many times as there are powers. No gain in sight… Sigh!

However, a few days later, while enjoying the sunset over Mont Blanc(!), I figured out that there exists a direct and efficient way to simulate from these powers of the sine function. Indeed, when looking at the density of cos(φ), it happens to be the signed root of a Beta(½,(d-1)/2), which avoids the accept-reject step. Presumably this is well-known, but I have not seen this proposal associated with the uniform distribution on the sphere.


text:
# Example 11 : Preconditioning

For a detailed discussion on preconditioning in MOOSE, see Preconditioning System.

To summarize, an accurate and complete preconditioning matrix can be important for an efficient Preconditioned Jacobian-Free Newton-Krylove (PJFNK) solve. It's absolutely essential for solve_type = NEWTON. MOOSE has ultiple options for buiding the preconditioning matrix :

• (Default) Block Diagonal Preconditioning

• Single Matrix Preconditioner (SMP)

• Finite Difference Preconditioner (FDP)

• Physics Based Preconditioner (PBP)

Block diagonal preconditioning uses kernels' and integrated boundary conditions' computeQpJacobian methods to build a block diagonal matrix. It will not account for variable coupling. This is the default if a user does not specify a [Preconditiong] block in their input file.

The Single Matrix Preconditioner builds its matrix using kernels' and integrated BCs' computeQpJacobian and computeQpOffDiagJacobian methods, the latter of which is responsible for the contributions of coupled variables. A good, simple example of a computeQpOffDiagJacobian method is in CoupledForce. CoupledForce contributes a waek-form residual equal to

To determine the corresponding off-diagonal Jacobian contribution, one must take the deriative:

To make use of user-specified computeQpOffDiagJacobian methods, one should specify in his/her input file:

[Preconditioning]
[./smp]
type = SMP
full = true
[../]
[]

The user may also choose to omit certain off-diagonal entries from their SMP matrix; this is outlined in the detailed Preconditioning article.

To build a preconditioning matrix through finite differencing of the residuals, the user can specify in his/her input file:

[Preconditioning]
[./fdp]
type = FDP
full = true
[../]
[]

This will create a near-perfect preconditioning matrix; however, it is extremely slow and will only work in serial. FDP should only be used for debugging purposes.

default.i

smp.i

fdp.i

CoupledForce.h


text:
# How to expand control sequence in argument of a macro

Consider the following:

\def\foo#1#2 {%
\if#1a%
\message{#2}
\fi}
\def\x{abc}
\edef\y{\foo\x}
\y

The result: ! Argument of \foo has an extra }.

The expected result: bc

TeX doesn't expand tokens when it's absorbing arguments to a macro. So \foo finds } when still looking for its second argument after having decided that \x is the first one.

If your aim is to have the second argument to \foo delimited by a space you should do

\def\foo#1#2 {%
\if#1a%
\message{#2}
\fi}
\def\x{abc }
\edef\y{\expandafter\foo\x}
\y

so that \x is expanded before \foo starts looking for its arguments.

The macro \y will expand to \message{bc}. Note the trailing space in the replacement text for \x.

The delimiter you chose is not the best one in this particular occasion. A different strategy is to use a “reserved” token:

\def\foo#1#2\foo{%
\if#1a%
\message{#2}
\fi}
\def\x{abc}
\edef\y{\expandafter\foo\x\foo}
\y

I used \foo because it's unlikely that it appears in the argument to itself.

• Is it possible not to use any delimiter at all, but instead just to take the whole expansion of \x ? Can we do without adding space to \def\x ? What if \def\x{abc } will be \edef\x{\fontname\font} - I don't want this to contain any additional delimiter data. Simply leaving the space out produces just b, but I need bc. – Igor Liferenko Jul 3 '15 at 23:17
• @IgorLiferenko An argument is either delimited or undelimited. You can't have both for the same parameter. – egreg Jul 4 '15 at 6:53
• @IgorLiferenko Maybe you need something like \def\foo#1{\expandafter\fooA#1\fooA} \def\fooA#1#2\fooA{...}. Then you can use \foo\x and \x includes "pure data" without delimiter. – wipet Jul 16 '15 at 19:05


text:
Opened 9 years ago

Closed 9 years ago

# [with patch, positive review] corrections for tut.tex

Reported by: Owned by: mabshoff tba major sage-2.10 documentation

### Description

Minh Nguyen send the following patch

--- sage-2.8.15/devel/doc-main/tut/tut.tex      2007-12-14
13:05:11.000000000 +1100
+++ sage-2.8.16/devel/doc-main/tut/tut.tex      2007-12-20
15:17:58.000000000 +1100
@@ -191,7 +191,7 @@
\ref{sec:compile}), and
\item
{\bf Scripts:}
-by writing a write stand-alone Python scripts that use the \sage library
+by writing stand-alone Python scripts that use the \sage library
(see Section~\ref{sec:standalone}).
\end{itemize}%two are needed for some weird reason

@@ -403,7 +403,7 @@

Semicolons are not needed at the ends of lines; a line is
in most cases ended by a newline.   However, you can put multiple
-statements on one line separate by semicolons:
+statements on one line separated by semicolons:
\begin{verbatim}
sage: a = 5; b = a + 3; c = b^2; c
64
@@ -694,7 +694,7 @@
integer literals beginning with a 0 as octal numbers.

The field of $p$-adic numbers is implemented as well:
-Note that once $p$-adic field is created, you can not
+Note that once a $p$-adic field is created, you can not
change its precision.

\begin{verbatim}
@@ -706,7 +706,7 @@
10*11^-2 + 5*11^-1 + 4 + 2*11 + O(11^18)
\end{verbatim}

-Much work has been done implementing rings of integers in p-adic
+Much work has been done implementing rings of integers in $p$-adic
fields or number fields other than $\Q$. The interested reader is
invited to ask the experts on the mailing for further details.

@@ -761,8 +761,8 @@
Univariate Polynomial Ring in x over Rational Field

-This creates a polynomial ring and tells \SAGE to use (the string) x'' and
-the interderminant when printing to the screen. The symbol $x$ is not yet
+This creates a polynomial ring and tells \SAGE to use (the string) x'' as
+the indeterminate when printing to the screen. The symbol $x$ is not yet
known to \sage, so you cannot use it to enter a polynomial (such as $x^2+1$)
belonging to $R$.

@@ -1486,7 +1486,7 @@
\langle (1,2,3)(4,5), (3,4) \rangle
\end{verbatim}

-You can also obtain the character table latex format in \sage:
+You can also obtain the character table \LaTeX format in \sage:

\begin{verbatim}
sage: G = PermutationGroup([[(1,2),(3,4)], [(1,2,3)]])
@@ -1789,7 +1789,7 @@
sage: p = polygon(L, rgbcolor=(1/8,3/4,1/2))
sage: p.save()
\end{verbatim}
-Type \code{p.show(axes=false)} to see this without any ases.
+Type \code{p.show(axes=false)} to see this without any axes.

A blue figure 8:

@@ -1899,7 +1899,7 @@
2 (x - 1)   2 (x + 1)
\end{verbatim}

-To compute the laplace transform of $t^2e^t - \sin(t)$:
+To compute the Laplace transform of $t^2e^t - \sin(t)$:

\begin{verbatim}
sage: s = var("s")
@@ -1916,7 +1916,7 @@
\index{Laplace transform solution of DEs}

In this section, we provide a few details which are useful to teaching a lower
-level ordinary differential equatoins course using \SAGE.
+level ordinary differential equations course using \SAGE.

The displacement from equilibrium (respectively)
for a coupled spring attached to a wall on the left
@@ -2674,7 +2674,7 @@
a trivial command in the system, in order to start up the
server for that program.  The most relavant time is the wall time.
However, if there is a significant difference between the
-wall time and the cpu time then this may indicate
+wall time and the CPU time then this may indicate
a performance issue worth looking into.

%skip
@@ -2722,7 +2722,7 @@
\index{error mesaages in SAGE}

When something goes wrong, you will usually see a Python
-exception''.  Python even tries to suggest what it is that it that
+exception''.  Python even tries to suggest what
raised the exception.  Often you see the name of the exception, e.g.,
{\tt NameError} or \code{ValueError} (see the Python Reference Manual
\cite{Py} for a complete list of exceptions).  For example,
@@ -2912,7 +2912,7 @@
return self.ambient_vector_space()(v)
\end{verbatim}
The \code{coordinate_vector} function coerces its
-input into the ambient space, which has the affect of
+input into the ambient space, which has the effect of
computing the vector of coefficients of $v$ in terms
of $V$.  The space~$V$ is already ambient since it's
just $\Q^3$.  There is also a \code{coordinate_vector}
@@ -3105,7 +3105,7 @@
you've defined in the current session as a dictionary in the given
\code{sessionname}.  (In the rare case when a variable does not support saving,
it is simply not saved to the dictionary.)  The resulting file
-is an \code{.sobj} file and can be loading just like any other
+is an \code{.sobj} file and can be loaded just like any other
object that was saved.   When you load the objects saved in a session,
you get a dictionary whose keys are the variables names and whose
values are the objects.
@@ -3176,7 +3176,7 @@
by William Stein, SAGE seminar, 6-9-2006 (notes by D. Joyner).

-The SAGE notebook is run by typing
+The \SAGE notebook is run by typing

%skip
\begin{verbatim}
@@ -3237,8 +3237,8 @@
using the add" link in the left-hand panel.

Your worksheet can be emailed to someone
-else, how can open it up in their copy of
-SAGE. The entire worksheet can now be executed.
+else, who can open it up in their copy of
+\SAGE. The entire worksheet can now be executed.

How does the notebook interface work?

@@ -3266,7 +3266,7 @@
----------------------                    .
\end{verbatim}

-For help on a SAGE command, \code{cmd}, in the notebook
+For help on a \SAGE command, \code{cmd}, in the notebook
browser box, type \code{cmd?} and now hit \verb+<esc>+ (not
\verb+<shift-enter>+).

@@ -3332,17 +3332,17 @@
program, since it {\em is} running that program.  In particular, you can
load complicated PARI programs and run them.
In contrast, the PARI interface (via the C library) is much more restrictive;
-first not all member functions have been implemented.  Second; a lot of code,
+first not all member functions have been implemented.  Second, a lot of code,
e.g., involving numerical integration, won't work via the PARI interface.
That said, the PARI interface can be significantly faster and more robust
-then the GP one.
+than the GP one.

\note{If the GP interface runs out of memory evaluating a given input
line, it will silently and automatically double the stack size and
retry that input line.  Thus your computation won't crash if you didn't
correctly anticipate the amount of memory that would be needed.  This
is a nice trick the usual GP interpreter doesn't seem to provide.  Regarding
-the PARI C-library interface, it immediately copies each created
+the PARI C library interface, it immediately copies each created
object off of the PARI stack, hence the stack never grows.  However,
each object must not exceed 100MB in size, or the stack will overflow
when the object is being created.  This extra copying does impose
@@ -3709,7 +3709,7 @@
Note that \sage will recompile \code{factorial.spyx} if you quit and
restart \sage.  The compiled shared object library is stored under
\code{\$HOME/.sage/temp/hostname/pid/spyx}. These files are deleted -when you exist \sage. +when you exit \sage. {\em NO} \sage preparsing is applied to spyx files, e.g., \code{1/3} will result in 0 in a spyx file instead of the rational @@ -3964,7 +3964,7 @@ \index{sequence!creating a} Sequences are a third list-oriented \SAGE type. Unlike lists and tuples, -Sequence is not built--in Python type. By default, a sequence is +sequence is not a built-in Python type. By default, a sequence is mutable, but using the \code{Sequence} class method \code{set_immutable}, it can be set to be immutable, as the following example illustrates. All elements of a sequence have a common parent, @@ -4050,7 +4050,7 @@ sage: d.items() [(1, 5), ('sage', 17), (Integer Ring, Finite Field of size 7)] \end{verbatim} -A common idiom is to iterate through the pairs of in a +A common idiom is to iterate through the pairs in a dictionary: \begin{verbatim} sage: d = {2:4, 3:9, 4:16} @@ -4216,9 +4216,9 @@ \end{verbatim} Of course this is not an efficient implementation of the Legendre symbol! It is meant to illustrate -various aspects of Python/SAGE programming. +various aspects of Python/\SAGE programming. The function \code{kronecker}, which comes with -SAGE, computes the Legendre symbol efficiently +\SAGE, computes the Legendre symbol efficiently via a C-library call to PARI. \index{<=}\index{>=} @@ -4269,7 +4269,7 @@ In the following two lines the first equality is \code{False} because there is no {\em canonical} morphism$\Q\to \F_5$, hence no canonical way to compare the$1$in$\F_5$to the$1 \in \Q$. In contrast, -there is a canonical map$\Z \to \F_5$, hence the second comparison is True. +there is a canonical map$\Z \to \F_5\$, hence the second comparison
is \code{True}.
Note also that the order doesn't matter.
\begin{verbatim}
sage: GF(5)(1) == QQ(1); QQ(1) == GF(5)(1)
@@ -4643,7 +4643,7 @@
still obey the standard Python rules when writing packages that will
be imported into \SAGE.

-\note{To install a random Python library that you find on the internet,
+\note{To install a random Python library that you find on the Internet,
Very often this means typing \code{sage -python setup.py install}.}

### comment:1 Changed 9 years ago by mabshoff

• Summary changed from corrections for tut.tex to [with proto patch] corrections for tut.tex

### comment:2 Changed 9 years ago by mabshoff

• Summary changed from [with proto patch] corrections for tut.tex to [with patch] corrections for tut.tex

### comment:3 Changed 9 years ago by mabshoff

• Resolution set to fixed
• Status changed from new to closed

Merged in Sage 2.10.alpha3

### comment:4 Changed 9 years ago by was

• Summary changed from [with patch] corrections for tut.tex to [with patch, positive review] corrections for tut.tex

All the suggested changes in this patch look good to me.

Note: See TracTickets for help on using tickets.


text:
Published on Mon Apr 14 2014

### Hybrid Conditional Gradient - Smoothing Algorithms with Applications to Sparse and Low Rank Regularization

, ,

A hybrid conditional gradient - smoothing algorithm (HCGS) for convex optimization problems. HCGS extends conditional gradient method to cases with multiple nonsmooth terms. The algorithm borrows techniques from smoothing proximal methods.

0
0
0
###### Abstract

We study a hybrid conditional gradient - smoothing algorithm (HCGS) for solving composite convex optimization problems which contain several terms over a bounded set. Examples of these include regularization problems with several norms as penalties and a norm constraint. HCGS extends conditional gradient methods to cases with multiple nonsmooth terms, in which standard conditional gradient methods may be difficult to apply. The HCGS algorithm borrows techniques from smoothing proximal methods and requires first-order computations (subgradients and proximity operations). Unlike proximal methods, HCGS benefits from the advantages of conditional gradient methods, which render it more efficient on certain large scale optimization problems. We demonstrate these advantages with simulations on two matrix optimization problems: regularization of matrices with combined $\ell_1$ and trace norm penalties; and a convex relaxation of sparse PCA.


text:
Article Contents
Article Contents

# A Liouville-type theorem for some Weingarten hypersurfaces

• We consider the entire graph $G$ of a globally Lipschitz continuous function $u$ over $R^N$ with $N \ge 2$, and consider a class of some Weingarten hypersurfaces in $R^{N+1}$. It is shown that, if $u$ solves in the viscosity sense in $R^N$ the fully nonlinear elliptic equation of a Weingarten hypersurface belonging to this class, then $u$ is an affine function and $G$ is a hyperplane. This result is regarded as a Liouville-type theorem for a class of fully nonlinear elliptic equations. The special case for some Monge-Ampère-type equation is related to the previous result of Magnanini and Sakaguchi which gave some characterizations of the hyperplane by making use of stationary isothermic surfaces.
Mathematics Subject Classification: Primary: 35J60, 53A07; Secondary: 35J15.

 Citation:

•  [1] O. Alvarez, J.-M. Lasry and P.-L. Lions, Convex viscosity solutions and state constraints, J. Math. Pures Appl., 76 (1997), 265-288.doi: doi:10.1016/S0021-7824(97)89952-7. [2] B. Andrews, Pinching estimates and motion of hypersurfaces by curvature functions, J. Reine Angew. Math., 608 (2007), 17-33.doi: doi:10.1515/CRELLE.2007.051. [3] L. Caffarelli, P. Guan and X.-N. Ma, A constant rank theorem for solutions of fully nonlinear elliptic equations, Comm. Pure Appl. Math., 60 (2007), 1769-1791.doi: doi:10.1002/cpa.20197. [4] M. G. Crandall, H. Ishii and P.-L. Lions, User's guide to viscosity solutions of second order partial differential equations, Bull. Amer. Math. Soc., 27 (1992), 1-67.doi: doi:10.1090/S0273-0979-1992-00266-5. [5] Y. Giga and M. Ohnuma, On strong comparison principle for semicontinuous viscosity solutions of some nonlinear elliptic equations, Int. J. Pure Appl. Math., 22 (2005), 165-184. [6] D. Gilbarg and N. S. Trudinger, "Elliptic Partial Differential Equations of Second Order," 2nd edition, Springer-Verlag, Berlin, Heidelberg, New York, 1983. [7] H. Ishii and P.-L. Lions, Viscosity solutions of fully nonlinear second-order elliptic partial differential equation, J. Differential Equations, 83 (1990), 26-78.doi: doi:10.1016/0022-0396(90)90068-Z. [8] R. Jensen, The maximum principle for viscosity solutions of fully nonlinear second order partial differential equations, Arch. Rational Mech. Anal., 101 (1988), 1-27.doi: doi:10.1007/BF00281780. [9] G. M. Lieberman, "Second Order Parabolic Differential Equations," World Scientific, 1996. [10] R. Magnanini and S. Sakaguchi, Stationary isothermic surfaces and some characterizations of the hyperplane in the $N$-dimensional Euclidean space, J. Differential Equations, 248 (2010), 1112-1119.doi: doi:10.1016/j.jde.2009.11.017. [11] J. Moser, On Harnack's theorem for elliptic differential equations, Comm. Pure Appl. Math., 14 (1961), 577-591.doi: doi:10.1002/cpa.3160140329. [12] N. S. Trudinger, The Dirichlet problem for the prescribed curvature equations, Arch. Rational Mech. Anal., 111 (1990), 153-179.doi: doi:10.1007/BF00375406. [13] J. I. E. Urbas, On the existence of nonclassical solutions for two classes of fully nonlinear elliptic equations, Indiana Univ. Math. J., 39 (1990), 355-382.doi: doi:10.1512/iumj.1990.39.39020.