Skip to main content
Nicola Gigante's user avatar
Nicola Gigante's user avatar
Nicola Gigante's user avatar
Nicola Gigante
  • Member for 10 years, 8 months
  • Last seen this week
21 votes
2 answers
2k views

Has the semantics of TeX (as a programming language) ever been formalized?

14 votes
2 answers
2k views

Algebraic equivalent of SAT?

12 votes
1 answer
239 views

Is there a survey of the field of quantum automata?

7 votes
2 answers
159 views

Algebraic characterisation of star-free safety languages

6 votes
0 answers
102 views

Relationship between natural deduction refutation and tableaux for propositional logic

6 votes
1 answer
289 views

Relationship between the transition monoid of an automaton and its adjacency matrix

6 votes
0 answers
152 views

Complexity of validity of first-order logic over finite words with bounded quantifier alternation?

6 votes
2 answers
221 views

Finite Automata with succinct representation of chains of states

5 votes
1 answer
216 views

Complexity of propositional LTL with past operators and freeze quantifier?

5 votes
1 answer
317 views

Formula complexity of arithmetic multiplication

4 votes
1 answer
56 views

References on second-order quantifier elimination and related topics

3 votes
0 answers
46 views

Can you compute Shannon expansion of a Boolean formula more efficiently by using a QBF solver?

3 votes
0 answers
124 views

State-based vs. transition-based definitions of alternating automata

3 votes
1 answer
163 views

Connection between algebraic logic and computational complexity of logics?

3 votes
2 answers
207 views

Translation of Counter-free automata into Linear Temporal Logic

2 votes
0 answers
55 views

Full version of the paper "Characterization of Temporal Property Classes"

2 votes
2 answers
163 views

Tableau method for two-variable first-order logic

2 votes
0 answers
94 views

Tenth Hilbert problem on interval arithmetic

2 votes
0 answers
61 views

Complexity measures for semi-decidable problems

2 votes
1 answer
90 views

Second-order reachability in second-order logic

1 vote
0 answers
57 views

Elimination of monadic second-order quantifiers

1 vote
0 answers
37 views

First-order linear mu-calculus?

1 vote
0 answers
85 views

Conditional lower bounds for reachability

1 vote
0 answers
114 views

Boolean formula complexity of arithmetic expressions

0 votes
0 answers
39 views

Making primary keys explicit in a Boolean relation

0 votes
0 answers
83 views

Original references for Karp-Lipton theorem improvement by Sipser

0 votes
1 answer
115 views

Diophantine equations with bounds on variables

0 votes
2 answers
87 views

Inexpressibility results for first-order logic that fail extending the language