We use results from communication complexity, both new and old ones, to prove lower bounds for unambiguous finite automata (UFAs). We show three results. 1) Complement: There is a language L recognised by an n-state UFA such that the complement language ̅L ...
Schloss Dagstuhl - Leibniz-Zentrum für Informatik2022
Unrefinement is a tool that allows to perform faster numerical simulations by controlling the level of precision in the specified area. We introduce an algorithm that creates a coarser geometry from an initial regular geometry, which is represented with re ...
The celebrated PCP Theorem states that any language in NP can be decided via a verifier that reads O(1) bits from a polynomially long proof. Interactive oracle proofs (IOP), a generalization of PCPs, allow the verifier to interact with the prover for multi ...
We investigate the regularity of the free boundary for the Signorini problem in Rn+1. It is known that regular points are (n−1)-dimensional and C∞. However, even for C∞ obstacles φ, the set of non-regular (or degenerate) points could be very large—e.g. wit ...
Being bounded by hydrological (inflow and barrier) boundaries, natural aquifers have regular/irregular shapes. Here, we consider aquifers bounded by segmental inflow (variable head) boundaries in which water is extracted/injected by a multi-well system. St ...
Harnessing fluidic instabilities to produce structures with robust and regular properties has recently emerged as a new fabrication paradigm. This approach is exemplified in the work of Gumennik et al. [Nat. Commun. 4, 2216 (2103)], in which the authors fa ...
In this thesis, we explore techniques for the development of recursive functional programs over unbounded domains that are proved correct according to their high-level specifications. We present algorithms for automatically synthesizing executable code, st ...
We prove that the quantifier-free fragment of the theory of character strings with regular language membership constraints and linear integer constraints over string lengths is decidable. We do that by describing a sound, complete and terminating tableaux ...
The traditional synthesis question given a specification asks for the automatic construction of a system that satisfies the specification, whereas often there exists a preference order among the different systems that satisfy the given specification. Under ...
Consider a binary-input memoryless output-symmetric channel W. Such a channel has a capacity, call it I (W), and for any R < I (W) and strictly positive constant P-e we know that we can construct a coding scheme that allows transmission at rate R with an e ...
Reo is a coordination language that can be used to model different systems. We propose a technique for symbolic execution of Reo circuits using the symbolic representation of data constraints in Constraint Automata. This technique enables us to obtain the ...
Quantitative generalizations of classical languages, which assign to each word a real number instead of a Boolean value, have applications in modeling resource-constrained computation. We use weighted automata (finite automata with transition weights) to d ...
Weighted automata are nondeterministic automata with numerical weights on transitions. They can define quantitative languages L that assign to each word w a real number L(w). In the case of infinite words, the value of a run is naturally computed as the ma ...
We propose and evaluate antichain algorithms to solve the universality and language inclusion problems for nondeterministic Buchi automata, and the emptiness problem for alternating Buchi automata. To obtain those algorithms, we establish the existence of ...
