1.4k citations
- Fermi National Accelerator LaboratoryUS194 papers
- University of KansasUS194 papers
- Charles UniversityCZ187 papers
- Imperial College LondonGB186 papers
- Lyon 1 UniversitéFR186 papers
- Northeastern UniversityUS186 papers
- University of Maryland, College ParkUS186 papers
- University of California, RiversideUS185 papers
- University of Nebraska–LincolnUS185 papers
- Lomonosov Moscow State UniversityRU184 papers
- Brown UniversityUS182 papers
- Joint Institute for Nuclear ResearchRU182 papers
13 papers · 1 filter
On the speed of constraint propagation and the time complexity of arc consistency testing
Christoph Berkholz, Oleg Verbitsky
Establishing arc consistency on two relational structures is one of the most popular heuristics for the constraint satisfaction problem. We aim at determining the time complexity o…
Synthesizing Structured Reactive Programs via Deterministic Tree Automata
Benedikt Brütsch
Existing approaches to the synthesis of reactive systems typically involve the construction of transition systems such as Mealy automata. However, in order to obtain a succinct rep…
Lazy abstractions for timed automata
Frédéric Herbreteau, B. Srivathsan, Igor Walukiewicz
We consider the reachability problem for timed automata. A standard solution to this problem involves computing a search tree whose nodes are abstractions of zones. For efficiency…
Down the Borel Hierarchy: Solving Muller Games via Safety Games
Daniel Neider, Roman Rabinovich, Martin Zimmermann
We transform a Muller game with n vertices into a safety game with (n!)^3 vertices whose solution allows to determine the winning regions of the Muller game and to compute a finite…
Dependence and Independence
Erich Grädel, Jouko Väänänen
We introduce an atomic formula intuitively saying that given variables are independent from given other variables if a third set of variables is kept constant. We contrast this wit…
Polynomial Interpretations for Higher-Order Rewriting
Carsten Fuhs, Cynthia Kop
The termination method of weakly monotonic algebras, which has been defined for higher-order rewriting in the HRS formalism, offers a lot of power, but has seen little use in recen…