40.2k citations
- Max Planck SocietyDE68 papers
- University of OxfordGB25 papers
- Centre National de la Recherche ScientifiqueFR24 papers
- Saarland UniversityDE17 papers
- University of CambridgeGB12 papers
- ETH ZurichCH11 papers
- IMDEA Software InstituteES10 papers
- Indian Institute of Technology KharagpurIN10 papers
- University of California, Los AngelesUS10 papers
- Max Planck Institute for InformaticsDE9 papers
- National University of SingaporeSG9 papers
- Newcastle UniversityGB9 papers
26 papers · 1 filter
Representing One Letter Weighted Automata Over the Tropical Semiring
Shaull Almagor, Ismaël Jecker, Filip Mazowiecki +3
We consider weighted automata over the tropical semiring . Recently, it was shown that determinisation is decidable; in this paper we focus on the comple…
History-Constrained Systems
Louwe B. Kuijer, David Purser, Henry Sinclair-Banks +1
We study verification problems for history-constrained systems (HCS), a model of guarded computation that uses nested systems. An outer system describes the process architecture in…
Bounded treewidth, multiple context-free grammars, and downward closures
C. Aiswarya, Pascal Baumann, Prakash Saivasan +2
The reachability problem in multi-pushdown automata (MPDA) has many applications in static analysis of recursive programs. An example is safety verification of multi-threaded recur…
Completing the picture for the Skolem Problem on order-4 linear recurrence sequences
Piotr Bacik
For almost a century, the decidability of the Skolem Problem - that is, the problem of finding whether a given linear recurrence sequence (LRS) has a zero term - has remained open.…
Verifying Unboundedness via Amalgamation
Ashwani Anand, Sylvain Schmitz, Lia Schütze +1
Well-structured transition systems (WSTS) are an abstract family of systems that encompasses a vast landscape of infinite-state systems. By requiring a well-quasi-ordering (wqo) on…
Analyzing Robustness of Angluin's L Algorithm in Presence of Noise
Lina Ye, Igor Khmelnitsky, Serge Haddad +5
Angluin's L algorithm learns the minimal deterministic finite automaton (DFA) of a regular language using membership and equivalence queries. Its probabilistic approximatively…