Theoretical Computer Science Stack Exchange

0

votes

0

answers

5

views

An efficient Beta-Equivalence algorithm?

lambda-calculus typed-lambda-calculus

asked 1 hour ago user1636815 1

0

votes

0

answers

5

views

Constructing FOL formula for which counting is easy?

counting-complexity first-order-logic

asked 2 hours ago SagarM 153

3

votes

1

answer

122

views

Can modern SAT-Solvers utilise the symmetry of First Order Logic?

sat first-order-logic

answered 3 hours ago HolKann 111

4

votes

1

answer

113

views

Subsets of $\omega$-words which share certain factors and languages accepted by special (prefix-closed) automata

fl.formal-languages automata-theory regular-language omega-language

answered 4 hours ago Denis 6,387

6

votes

0

answers

182

views

Separation of the states of a deterministic omega-automaton by looping words taken from a regular language of non-empty words

automata-theory regular-language omega-language

modified 5 hours ago Hermann Gruber 4,594

1

vote

1

answer

575

views

Regular safety properties and bad prefixes of $\omega$-regular properties

model-checking program-verification temporal-logic omega-language

modified 6 hours ago Hermann Gruber 4,594

2

votes

0

answers

201

views

Complexity of DBA-recognizable Omega-Languages

cc.complexity-theory fl.formal-languages automata-theory regular-expressions omega-language

modified 6 hours ago Hermann Gruber 4,594

8

votes

3

answers

539

views

Number of connected components of a random nearest neighbor graph?

graph-theory random-graphs

modified 7 hours ago Alexander Chervov 193

3

votes

2

answers

686

views

Continued Fraction Algorithm in Shor's Algorithm

quantum-computing factoring

answered 19 hours ago Yingkang Cao 21

12

votes

2

answers

304

views

Complexity relative to the graph of the Busy-Beaver function

cc.complexity-theory computability

modified yesterday Denis 6,387

-1

votes

0

answers

13

views

Universal Generalisation Inference rule over array Proprties

automated-theorem-proving program-verification

asked yesterday smxadn23 1

1

vote

1

answer

107

views

What is the complexity of this submatrix selection problem?

ds.algorithms linear-algebra

modified yesterday Neal Young 6,015

-1

votes

0

answers

24

views

Reduce a decision problem to an optimization problem

cc.complexity-theory graph-theory np-hardness reductions graph-colouring

asked yesterday BrianH 1

0

votes

1

answer

66

views

Minimizing the gaps with incremental capacity

ds.algorithms np-hardness dynamic-programming

modified yesterday Neal Young 6,015

Jun	JUL	Aug
	08
2019	2020	2021

Stack Exchange Network

current community

your communities

more stack exchange communities

Explore our Questions

An efficient Beta-Equivalence algorithm?

Constructing FOL formula for which counting is easy?

Can modern SAT-Solvers utilise the symmetry of First Order Logic?

Subsets of $\omega$-words which share certain factors and languages accepted by special (prefix-closed) automata

Separation of the states of a deterministic omega-automaton by looping words taken from a regular language of non-empty words

Regular safety properties and bad prefixes of $\omega$-regular properties

Complexity of DBA-recognizable Omega-Languages

Number of connected components of a random nearest neighbor graph?

Continued Fraction Algorithm in Shor's Algorithm

Complexity relative to the graph of the Busy-Beaver function

Universal Generalisation Inference rule over array Proprties

What is the complexity of this submatrix selection problem?

Reduce a decision problem to an optimization problem

Minimizing the gaps with incremental capacity

Hot Network Questions