Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.

Sign up to join this community

Anybody can ask a question

Anybody can answer

The best answers are voted up and rise to the top

Explore our Questions

Ask Question

more tags

Active Hot Week Month

-3

votes

0

answers

18

views

Stuttering steps in temporal logic of actions (TLA)

lo.logic formal-methods temporal-logic

asked 2 days ago occulti 95

1

vote

1

answer

53

views

Variable wire weights in DLOGTIME-uniform circuits

lo.logic circuit-complexity uniformity bounded-depth

answered Jan 20 at 22:38 Jake 159

1

vote

0

answers

60

views

Complexity class name for the class of languages that are $\Sigma^1_1$-definable over finite domains

cc.complexity-theory lo.logic terminology descriptive-complexity finite-model-theory

asked Jan 14 at 19:58 Erfan Khaniki 262

9

votes

3

answers

365

views

Simple model of computation with homoiconicity

lo.logic computability pl.programming-languages lambda-calculus

answered Jan 7 at 17:25 greps 57

21

votes

2

answers

1k

views

Decidability of diophantine equations over {=, +, gcd}

lo.logic nt.number-theory decidability

answered Dec 27 '20 at 11:37 Bartosz Bednarczyk 945

8

votes

2

answers

435

views

Can factorial be encoded in the Kappa-calculus with fixed point operator?

lo.logic type-theory lambda-calculus

modified Dec 20 '20 at 16:03 Martin Berger 10k

7

votes

0

answers

78

views

Proof of $DLOGTIME-CC^0 = MOD[<,bit]$

lo.logic circuit-complexity uniformity

asked Oct 28 '20 at 19:36 Jake 159

1

vote

0

answers

107

views

$\mathit{FO}[+,\times]$ seems more powerful than $\mathit{DLOGTIME}$-uniform $\mathit{AC}^0$?

lo.logic uniformity ac0

modified Oct 23 '20 at 7:54 Emil Jeřábek 12.8k

1

vote

0

answers

103

views

Functional abbreviation for Inst expression in Turing's 1936 paper

lo.logic computability turing-machines

modified Oct 22 '20 at 21:34 Ajax 111

2

votes

1

answer

140

views

Is modal $\mu$-calculus “equivalent” to bisimulation?

modified Oct 16 '20 at 23:09 Denis 6,695

0

votes

1

answer

51

views

Is every countable, finite-branching LTS bisimilar to a tree?

lo.logic model-checking temporal-logic process-algebra mu-calculus

modified Oct 16 '20 at 23:07 Denis 6,695

11

votes

2

answers

466

views

Boolean formula balancing in $\mathsf{AC^0}$

cc.complexity-theory ds.algorithms reference-request lo.logic boolean-formulas

modified Oct 1 '20 at 17:26 Emil Jeřábek 12.8k

4

votes

0

answers

160

views

Alternative exponential definition of Kolmogorov complexity

lo.logic kolmogorov-complexity

modified Sep 30 '20 at 23:10 Jori 41

1

vote

0

answers

91

views

λProlog vs HiLog

lo.logic pl.programming-languages type-theory logic-programming

modified Sep 16 '20 at 17:21 bobcat 221

Browse more Questions

Theoretical Computer Science Stack Exchange works best with JavaScript enabled