Search Results
| Search type | Search syntax |
|---|---|
| Tags | [tag] |
| Exact | "words here" |
| Author |
user:1234 user:me (yours) |
| Score |
score:3 (3+) score:0 (none) |
| Answers |
answers:3 (3+) answers:0 (none) isaccepted:yes hasaccepted:no inquestion:1234 |
| Views | views:250 |
| Code | code:"if (foo != bar)" |
| Sections |
title:apples body:"apples oranges" |
| URL | url:"*.example.com" |
| Saves | in:saves |
| Status |
closed:yes duplicate:no migrated:no wiki:no |
| Types |
is:question is:answer |
| Exclude |
-[tag] -apples |
| For more details on advanced search visit our help page | |
Results tagged with reference-request
Search options questions only
not deleted
user 8953
Reference-request is used when the author needs to know about work related to the question.
10
votes
1
answer
257
views
Succinctness of regular expressions with empty word
Consider regular expressions on some alphabet $\Sigma$, without the empty word: $$e,f:=a\in\Sigma\mid e\cdot f \mid e+f\mid e^+$$
These $\varepsilon$⁻free expressions can define all regular languages …
- 9,018
1
vote
0
answers
96
views
Induced subgraphs with interface
I am interested in hypergraphs with interfaces, I'll call them simply "graphs" in the following.
Formally, a graph of sort $k$ is a tuple $(V,E,i)$ with $E\subseteq V^+$ is the set of edges, each edge …
- 9,018
9
votes
2
answers
299
views
Understanding graph minor theorem
This question is two-fold, and is mainly reference-oriented:
Is there somewhere where the main intuitions for proving graph minor theorem are given, without going too much into the details? I know t …
- 9,018
8
votes
1
answer
191
views
Word equations with integer parameters
This is mainly a reference request.
Let us define a parameterized expression on a finite alphabet $\Sigma$ as follows:
$$e,e':= w\mid w^i \mid e\cdot e'$$
Where $w\in\Sigma^+$ is a word, and $i$ is an …
- 9,018
5
votes
0
answers
95
views
Complexity of inclusion of transfinite expressions
Transfinite expressions on an alphabet $\Sigma$ are generated by the grammar :
$$e,f:= a\in\Sigma\mid e\cdot f\mid e+f\mid e^*\mid e^\omega.$$
They describe languages of transfinite words, i.e. words …
- 9,018
14
votes
1
answer
2k
views
Distance between regular languages
I want to define a notion of "closeness" between two regular languages of finite words in $\Sigma^*$ (and/or infinite words in $\Sigma^\omega$). The basic idea is that we want two languages to be clos …
- 9,018
24
votes
5
answers
5k
views
EXPSPACE-complete problems
I am currently trying to find EXPSPACE-complete problems
(mainly to find inspiration for a reduction), and
I am surprised by the small number of results coming up.
So far, I found these, and I have …
- 9,018
6
votes
1
answer
203
views
On bandwidth of graphs
I am trying to find references on algorithms for graphs of bounded bandwidth, in the same way as it is done with treewidth for instance.
I could only find research related to computing the bandwidth, …
- 9,018
4
votes
0
answers
58
views
Reference for cost of translating between regular language formalisms
It is well-known that regular languages can be defined equivalently via many formalisms, among which regular expressions, NFAs, finite monoids, Monadic Second-Order logic (MSO).
The cost (say in size …
- 9,018
11
votes
3
answers
940
views
Implementation of surreal numbers for games
There is a very nice construction by Conway of surreal numbers. They are "numbers" that contain both real numbers and ordinals, are totally ordered, and have all the properties of a field (except they …
- 9,018