Breandan Considine
@breandan
Nov 12
0
0
1
132
Breandan Considine retweeted
Computational Complexity Papers@QCRH
Nov 10
Type-logical grammars and formal languages

Richard Moot
arxiv.org/abs/2611.12618 [𝚌𝚜.𝙲𝙲 𝚌𝚜.𝙲𝙻 𝚌𝚜.𝙵𝙻 𝚌𝚜.𝙻𝙾]
We show that type-logical grammars with the standard rules for product, associativity, extraction and infixation have an NP-complete fixed recognition problem, adapting a construction for first-order linear logic from Pshenitsyn (2025), who already showed that grammars in first-order linear logic are closed under intersection and therefore not semilinear and not mildly context-sensitive. We strengthen these results and shown that grammars in first-order linear logic can simulate the quasi-linear grammars of Book & Greibach (1970), the grammars recognised in non-deterministic linear time (NSPACE(n) or. NLIN). I argue that NLIN is an interesting class of formal languages as well, and a useful upper bound on the time complexity of formalisms used for natural language, just like LOGCFL is a useful upper bound on the space complexity. Taken together this means that first-order linear logic can be seen as the logic of non-deterministic linear-time string languages, graph languages and automa
0
1
0
50
Breandan Considine retweeted
Nobutaka Shimizu@knewknowl
Nov 10
I finished my talk at FOCS26. Here is my slide!
nobutakashimizu.github.io/FOCS26/1
2
7
72
4,603
Breandan Considine retweeted
Programming Languages Papers@ProgPapers
Nov 10
Beating Rytter's Bound: All-Pairs CFL Reachability in O(n³(loglog n)²/(log n)²) Time

Rupak Majumdar
arxiv.org/abs/2611.12315 [𝚌𝚜.𝙿𝙻 𝚌𝚜.𝙵𝙻]
Context-free reachability and 2NPDA recognition are fundamental problems in program analysis and language theory. Despite years of effort, the best algorithms for these problems run in time O(n³/log n) on a word RAM model; they are based on an observation of Rytter in 1985 for 2NPDA which was adapted for CFL reachability by Chaudhuri in 2008. No better algorithm has been designed since. We give the first improvement to Rytter's algorithm. For both all-pairs context-free reachability and 2NPDA recognition, we show a deterministic algorithm running in O(n³(loglog n)²/(log n)²) time and O(n²+ε) words of space for every fixed 0<ε<1 on a word RAM. Our improvement is based on a new data structure that reports set differences using batched maintenance of exact intersection counts, allowing saturation to skip regions that contain no new reachability information.
0
1
3
223
Breandan Considine retweeted
Formal Languages and Automata Theory Papers@FormalLanguages
Nov 10
Towards A Parametrized Complexity of Determinization

Ivan Baburin, Ryan Cotterell
arxiv.org/abs/2611.10911 [𝚌𝚜.𝙵𝙻]
Given a nondeterministic finite automaton (NFA), we want to estimate the difficulty of finding an equivalent deterministic finite automaton (DFA). We demonstrate that computing the state complexity of an NFA within polynomial precision is PSPACE-hard, and furthermore the same holds for the complexity of the subset construction, Brzozowski's algorithm, or, indeed, any determinization algorithm which runs at least as fast. This result implies that making any a priori estimate of the running time of the major determinization algorithms is inherently hard. To circumvent this—in the spirit of parametrized complexity—we try to identify complexity measures which can guarantee efficient determinization. Our main idea rests on linking the complexity of the subset construction to transition monoids using the semigroup complexity. We show that the semigroup complexity by itself can be reasonably approximated for certain classes of NFAs, and then introduce subset complexity—a refinement of the sem
0
1
0
54
Breandan Considine retweeted
Archdiocese of SF
@ArchdioceseSF
Oct 16
St. Francis is in San Francisco! The sacred relics and art masterpieces of St. Francis of Assisi will be on display from Oct. 16-Nov. 28 at the Cathedral of St. Mary of the Assumption.

Opening ceremonies for the exhibition will take place Friday, Oct. 16 at 5 p.m. at the Cathedral.

Also on display are historic mission models of the 21 missions originally created for the 1939 World’s Fair on Treasure Island courtesy of the Cline family.

The exhibition is sponsored by the Knights of Saint Francis, Archdiocese of San Francisco, National Shrine of St. Francis of Assisi, Cathedral of St. Mary of the Assumption, and the Benedict XVI Institute.

Learn more: sfarch.org/anniversaries
ABC7 News
@abc7newsbayarea
Oct 16
Relics of St. Francis of Assisi are on display at San Francisco's Cathedral of St. Mary of the Assumption in their first trip outside Italy. The exhibit features paintings and religious artifacts, including an item containing the saint's blood. Organizers say the display years of Franciscan history and highlights the connection between San Francisco and its namesake saint. For more information, click the link below. abc7news.com/19939724/
0
7
27
513
Breandan Considine
@breandan
Nov 9
Visiting the city of Saint Francis this week. Happy to chat with you about the real presence of our Lord Jesus in the sacrament of the Holy Eucharist, the Matthew effect and the cultivation of intellectual talent, analytic combinatorics, model counting, and structured generation.
0
0
4
238
Breandan Considine
@breandan
Nov 7
Had a pleasant chat about reverse mathematics and the equational theories project. He said the time is ripe for these kinds of collaborations and pointed me to an interesting conjecture by Poonen. Thanks Terry!
10
9
161
9,300
Breandan Considine retweeted
Formal Languages and Automata Theory Papers@FormalLanguages
Nov 2
General semiring conditions for weighted L* termination

Noah Bertram, Daniel Luckhardt, Alexandra Silva
arxiv.org/abs/2610.41184 [𝚌𝚜.𝙵𝙻 𝚌𝚜.𝙻𝙾]
Weighted automata learning has been well-studied over (semi)rings which have a dimension theory. In this work, we investigate active learning for weighted automata over semirings that lack such a structure. We first show that the principal ideal domain variant of the L* algorithm also terminates for a larger class of semirings containing Noetherian semirings, commutative rings, and bounded distributed lattices. We then present a variant of this algorithm for learning deterministic weighted automata, and prove that this algorithm terminates for commutative semirings.
0
1
2
127
Breandan Considine
@breandan
Oct 30
Noteworthy they disclosed the logs. Worth considering the second-order effects on parallel construction, monitorability, and language identification in the limit. Solomonoff says simplest hypothesis most probable, but there are no free lunches. Cybenko's absence was also curious.
0
0
0
365
Breandan Considine
@breandan
Oct 30
Will Griffith, trustee and partner at ICONIQ Capital interviews Peter DeSantis about his journey from Dartmouth CS to Amazon SVP 27 years later, ongoing investments in scaling AI and quantum, HW/research codesign, and the value of specialization and “going deep”.
0
0
3
440
Breandan Considine
@breandan
Oct 30
Presidents Beilock, Carlson, BoA CFO Borthwick, and Dartmouth senior Roger Friedlander on the premise, promise and purpose of a university education, how to navigate the coming challenges of AI, and the continued importance of a liberal arts education.
0
0
0
256
Breandan Considine
@breandan
Oct 29
Yann receives the AI at 70 award and gives a keynote lecture on JEPA, a new family of architectures for world modeling that learn a hierarchy of abstractions. Argues that LLMs are not the path to general intelligence.
0
0
0
460
Breandan Considine
@breandan
Oct 29
Mira Murati (Thayer ‘12) in conversation with Dartmouth president Sian Beilock on the risks of concentration, building interaction models at Thinking Machines, and advice to students on choosing a career in age of AI.
0
0
2
379
Breandan Considine
@breandan
Oct 26
Looking forward to visiting Dartmouth College later this week, where 70 years prior, a small group of scientists -- including one from McGill -- convened to establish a new field called "artificial intelligence" (today known as SI). Curious to see if they will let another one in!
Dartmouth 🌲
@dartmouth
Aug 26
70 years ago, we hosted the workshop that launched the field of AI. This October, we're marking the anniversary—asking what must remain human, and who's accountable when AI fails. bit.ly/4c8orpZ
0
0
2
230
Breandan Considine retweeted
Mathieu Blondel@mblondel_ml
Oct 22
Our book "The Elements of Differentiable Programming" can now be read directly in the browser:

diffprog.github.io
11
91
783
59,323
Breandan Considine
@breandan
Oct 22
Had a fraction of the resources devoted to schemes like AI safety went to formal methods like symbolic execution, model checking &amp; language based security maybe we wouldn’t be facing so many zero days today. For decades, defense has languished due to weak adversaries. Calculemus!
Breandan Considine
@breandan
7 Jan 2024
If you think AI safety matters, then type safety should also matter a great deal. Formal verification is the antidote to misaligned computation.
0
0
1
281
Breandan Considine retweeted
Data Structures and Algorithms Papers@AlgorithmPapers
Oct 21
Dynamic Distances Without Matrix Inverse

Jan van den Brand, Adam Karczmarz, Aryan Patel
arxiv.org/abs/2610.28573 [𝚌𝚜.𝙳𝚂]
We study the fully dynamic exact distance problem in unweighted directed graphs, where the graph undergoes edge insertions and deletions, and the distance between two query vertices must be reported. Under the combinatorial Boolean matrix multiplication conjecture, any subquadratic-time algorithm for this problem must use algebraic techniques. All prior work uses the polynomial matrix inverse as its algebraic tool, but within subquadratic time, this technique can only maintain distances up to a small-polynomial hop bound. So larger distances must be reassembled from short-range pieces by a combinatorial layer. This hybrid algebraic-combinatorial construction has led to a substantial slowdown for dynamic distances compared to other dynamic graph problems relying on algebraic techniques. We give the first subquadratic-time dynamic distance algorithm built on dynamically maintaining a different algebraic object than the matrix inverse. By maintaining the Frobenius form A=KCK⁻¹ of a dynami
0
1
5
357
Breandan Considine
@breandan
Jul 25
Looking forward to attending the Thomistic Summer Conference at the newly established New England campus of Thomas Aquinas College next week. Over 20 years ago, I used to play ultimate frisbee there when it was called the Northfield Mount Hermon school. Fides Quarens Intellectum!
1
0
2
552
Breandan Considine
@breandan
Oct 5
Replying to @breandan
The TSC lectures have now been published. I didn't attend them all and many went over my head, but I found "A Fractured Mirror?", "On Divine Suffering and Theological Predication", and "On the Importance of Understanding Universals" especially interesting. thomasaquinas.edu/lectures-2026-…
0
0
0
108
Breandan Considine retweeted
Programming Languages Papers@ProgPapers
Sep 28
SafeNom: Data-Aware Microservice Policies

Karuna Grewal, P. Brighten Godfrey, Justin Hsu
arxiv.org/abs/2609.30394 [𝚌𝚜.𝙿𝙻 𝚌𝚜.𝙽𝙸]
Many cloud-based applications are organized as loosely coupled microservices, where invoking a service's API triggers a cascade of APIs across many services and leads to inter-service exchange of API parameters and output responses. Current tools for monitoring microservice safety properties have limited expressiveness for properties that describe the flow of data through API calls. To this end, we present SafeNom, a specification and monitoring framework for microservices based on nominal languages. SafeNom policies can express both the desired order of API calls and how the data carried in requests and responses should or should not flow between the APIs. Policies are enforced using a nominal automaton-based distributed runtime monitor which can be applied in a blackbox and non-invasive manner, without access to the service implementation and without making changes to the service implementation. Our experiments show that our monitor can efficiently enforce rich data-aware properties
0
1
0
111
Load more