Recent zbMATH articles in MSC 68Qhttps://www.zbmath.org/atom/cc/68Q2021-03-30T15:24:00+00:00WerkzeugOrbit expandability of automaton semigroups and groups.https://www.zbmath.org/1455.681072021-03-30T15:24:00+00:00"D'Angeli, Daniele"https://www.zbmath.org/authors/?q=ai:dangeli.daniele"Rodaro, Emanuele"https://www.zbmath.org/authors/?q=ai:rodaro.emanuele"Wächter, Jan Philipp"https://www.zbmath.org/authors/?q=ai:wachter.jan-philippThe article studies several problems related to orbital growth in automaton semigroups and groups,
where automaton semigroups are understood to be generated by \textit{partial} deterministic letter-to-letter transducers.
Consider an automaton semigroup \(S\) acting on \(\Sigma^*\) and for each \(w \in \Sigma^*\) denote by \(Sw\) the orbit of \(w\) with respect to \(S\).
A word \(u \in \Sigma^*\) is said to be \(k\)-expandable with respect to \(S\) if there exists \(v \in \Sigma^+\) such that \(\lvert Suv\rvert \geq \lvert Su\rvert + k\) and
expandable if it is \(k\)-expandable for some \(k \geq 1\). This notion is motivated by the study of \(\omega\)-words with infinite orbits, as all prefixes of these ones
are clearly expandable.
In the main result of the article, the authors prove that, given a transducer \(\mathcal{T}\) generating an automaton semigroup \(S\),
a word \(u \in \Sigma^*\) and a natural number \(k\), it is decidable whether \(u\) is \(k\)-expandable with respect to \(S\).
A space-bounded nondeterministic decision procedure is described for this problem, while the Immerman-Szelepcsényi inductive counting technique is employed in its analysis
[\textit{N. Immerman}, SIAM J. Comput. 17, No. 5, 935--938 (1988; Zbl 0668.68056); \textit{R. Szelepcsényi}, Acta Inf. 26, No. 3, 279--284 (1988; Zbl 0638.68046)].
The results for automaton semigroups are further strengthened in the case of an automaton \textit{group} \(G\). The authors prove an algebraic characterisation of expandable words with respect to \(G\), which they use to obtain a more efficient decision procedure for this particular case.
It is also proved that every word is expandable in an automaton semigroup generated by a complete reversible transducer.
Reviewer: Peter Kostolányi (Bratislava)Sharpness of KKL on Schreier graphs.https://www.zbmath.org/1455.050272021-03-30T15:24:00+00:00"O'Donnell, Ryan"https://www.zbmath.org/authors/?q=ai:odonnell.ryan"Wimmer, Karl"https://www.zbmath.org/authors/?q=ai:wimmer.karlSummary: Recently, the Kahn-Kalai-Linial (KKL) Theorem on influences of functions on \(\{0,1\}^n\) was extended to the setting of functions on Schreier graphs. Specifically, it was shown that for an undirected Schreier graph \(\text{Sch}(G,X,U)\) with log Sobolev constant \(\rho\) and generating set \(U\) closed under conjugation, if \(f : X \to \{0,1\}\) then
\[
\mathcal{E}[f] \gtrsim \log(1/\text{MaxInf}[f]) \cdot \rho \cdot \text{Var}[f].
\]
Here \(\mathcal{E}[f]\) denotes the average of \(f\)'s influences, and \(\text{MaxInf}[f]\) denotes their maximum. In this work we investigate the extent to which this result is sharp. We show: 1. The condition that \(U\) is closed under conjugation cannot in general be eliminated. 2. The log-Sobolev constant cannot be replaced by the modified log-Sobolev constant. 3. The result cannot be improved for the Cayley graph on \(S_n\) with transpositions. 4. The result can be improved for the Cayley graph on \(\mathbb{Z}_m^n\) with standard generators. 5. Talagrand's strengthened version of KKL [\textit{M. Talagrand}, Ann. Probab. 22, No. 3, 1576--1587 (1994; Zbl 0819.28002)] also holds in the Schreier graph setting:
\[
\mathrm{avg}_{u \in U} \{\mathrm{Inf}_u[f]/\log(1/\mathrm{Inf}_u[f]) \} \gtrsim \rho \cdot \text{Var}[f].
\]New substitution bases for complexity classes.https://www.zbmath.org/1455.030512021-03-30T15:24:00+00:00"Mazzanti, Stefano"https://www.zbmath.org/authors/?q=ai:mazzanti.stefanoIn this paper, the author improves earlier work by showing that well-known function complexity classes can be characterised as the substitution closure of finite sets of simple functions \(\mathbf{AC}^0(F)\). Intuitively, this work is about finding fitting substitution bases, that is, finite sets of functions that define a function class (projection functions and substitution is allowed). For instance, if \(F=\{\text{mult}\}\) then \(\mathbf{AC}^0(F)=\mathbf{TC}^0\). Furthermore, the author present in the concluding section a discussion on how the introduced function algebras may lead to a new, algebraic proof that \(\mathbf{AC}^0\neq\mathbf{TC}^0\). At the end of the preliminaries, the author gives already a short outlook on the results he is going to prove which gives a nice context. Some results (e.g., Lemma 3.8, Lemma 3.12) in the main part are not proven (``straightforward''). Unfortunately, there is little intertext between the lemmas which could guide a reader a bit more.
Section 5 presents new bases for \(\mathbf{TC}^0\), and, in the next Section 6, one gets a nice characterisation of the complexity classes \(\mathbf{NC}^1, \mathbf{L}, \mathbf{P},\) and \(\mathbf{PSPACE}\) in terms of function sets \(F\) such that they respectively coincide with \(\mathbf{AC}^0(F)\).
Reviewer: Arne Meier (Hannover)Compact RCA based on multilayer quantum-dot cellular automata.https://www.zbmath.org/1455.680572021-03-30T15:24:00+00:00"Safoev, Nuriddin"https://www.zbmath.org/authors/?q=ai:safoev.nuriddin"Jeon, Jun-Cheol"https://www.zbmath.org/authors/?q=ai:jeon.jun-cheolSummary: The full adder is a basic logical circuit that performs an addition operation in any arithmetic circuits. In our paper, a bettered 1-bit full adder is proposed based on quantum-dot cellular automata (QCA). It confirms that the proposed circuit works properly and it can be used as a highly efficient design in arithmetic circuits. Finally, by connecting four 1-bit QCA full adders, we present a 4-bit ripple carry adder successfully. Our design has been realized with a simulation tool QCA Designer. The performance of our structure has significantly achieved improvements in terms of cell count, occupied area, and delay.
For the entire collection see [Zbl 1392.68010].Diagnosis of hybrid dynamic systems based on the behavior automaton abstraction.https://www.zbmath.org/1455.930942021-03-30T15:24:00+00:00"Sarrate, Ramon"https://www.zbmath.org/authors/?q=ai:sarrate.ramon"Puig, Vicenç"https://www.zbmath.org/authors/?q=ai:puig.vicenc"Travé-Massuyès, Louise"https://www.zbmath.org/authors/?q=ai:trave-massuyes.louiseSummary: This chapter focuses on the use of the hybrid automaton framework to develop a method for diagnosing hybrid systems. A hybrid automaton models the behavior of the system through a set of operation modes and a set of transitions between modes which trigger upon discrete events or based on continuous state conditions. Continuous dynamics within each mode are described by a set of differential equations which constrain the continuous state, input and output variables. The discrete event part constrains the possible transitions among modes and is referred to as the underlying DES. The restriction of the hybrid system to the continuously-valued part of the model is defined as the multimode system. The diagnosis method relies on abstracting the continuous dynamics by defining a set of ``distinguishability-aware'' events, called signature-events, associated to mode signature changes across modes. Signature-events are used to enrich appropriately the underlying DES to obtain the so-called behavior automaton from which a diagnoser can be built following standard methods of the discrete event system field. The diagnostic task involves detecting and isolating two types of faults: structural and non-structural faults. Structural faults are represented by a dynamic model as in the case of nominal modes and they are identified thanks to the diagnoser. Non-structural faults do not change the structure of the model in a given operation mode and are identified by a proper residual pattern. The proposed hybrid diagnosis method can operate in a non-incremental and an incremental manner. In the non-incremental form, algorithms are executed taking into account global models whereas in the incremental form only the useful parts of the diagnoser are built, developing the branches that are needed to explain the occurrence of incoming events. Thus, the resulting diagnoser adapts to the system operation life and is less demanding in terms of memory storage than building the full diagnoser offline. The incremental method is illustrated by the application to a case study based on a representative part of the Barcelona sewer network and its complexity is compared to the non-incremental method.
For the entire collection see [Zbl 1417.68010].Homomorphic encryption for finite automata.https://www.zbmath.org/1455.941572021-03-30T15:24:00+00:00"Genise, Nicholas"https://www.zbmath.org/authors/?q=ai:genise.nicholas"Gentry, Craig"https://www.zbmath.org/authors/?q=ai:gentry.craig"Halevi, Shai"https://www.zbmath.org/authors/?q=ai:halevi.shai"Li, Baiyu"https://www.zbmath.org/authors/?q=ai:li.baiyu"Micciancio, Daniele"https://www.zbmath.org/authors/?q=ai:micciancio.danieleSummary: We describe a somewhat homomorphic GSW-like encryption scheme, natively encrypting matrices rather than just single elements. This scheme offers much better performance than existing homomorphic encryption schemes for evaluating encrypted (nondeterministic) finite automata (NFAs). Differently from GSW, we do not know how to reduce the security of this scheme from LWE, instead we reduce it from a stronger assumption, that can be thought of as an inhomogeneous variant of the NTRU assumption. This assumption (that we term iNTRU) may be useful and interesting in its own right, and we examine a few of its properties. We also examine methods to encode regular expressions as NFAs, and in particular explore a new optimization problem, motivated by our application to encrypted NFA evaluation. In this problem, we seek to minimize the number of states in an NFA for a given expression, subject to the constraint on the ambiguity of the NFA.
For the entire collection see [Zbl 1428.94009].Active diagnosis for switched systems using Mealy machine modeling.https://www.zbmath.org/1455.930952021-03-30T15:24:00+00:00"van Gorp, Jeremy"https://www.zbmath.org/authors/?q=ai:van-gorp.jeremy"Giua, Alessandro"https://www.zbmath.org/authors/?q=ai:giua.alessandro"Defoort, Michael"https://www.zbmath.org/authors/?q=ai:defoort.michael"Djemaï, Mohamed"https://www.zbmath.org/authors/?q=ai:djemai.mohamedSummary: Generally, fault diagnosis schemes play an important role in ensuring the safety of physical or engineering systems. The study of diagnosis problem for switched systems is interesting and allows considering a more wide range of systems. This chapter deals with the active diagnosis for a class of switched systems which may not satisfy the classical diagnosability conditions usually considered in the Discrete-Event-Systems setting. In the first part, the modeling approach we propose is introduced. We propose to use an abstract representation of a switched system using a Mealy Machine where discrete faults may occur. An appropriate diagnoser is designed in order to reduce the uncertain state subset. In the second part, some diagnosability conditions are deduced. Based on the Mealy Machine, a new active diagnosis strategy is designed in order to ensure the fault detection and isolation for a class of switched systems. An algorithm combining the proposed diagnoser and a testing procedure is introduced in order to solve the fault identification problem. A study on the cascade multicellular converter is carried out to detect and isolate faulty cells. Illustrative simulation results, on a two-cells converter, show the details of the algorithm and experimental results, on a three-cells converter, present the effectiveness, in real time, of the proposed scheme.
For the entire collection see [Zbl 1417.68011].Pair component categories for directed spaces.https://www.zbmath.org/1455.180022021-03-30T15:24:00+00:00"Raussen, Martin"https://www.zbmath.org/authors/?q=ai:raussen.martinA directed space (d-space for short), as defined by \textit{M. Grandis} [Cah. Topol. Géom. Différ. Catég. 44, No. 4, 281--316 (2003; Zbl 1059.55009)] is a topological space, \(X\), together with a subset of the space of all paths on it, that satisfies some reasonable properties so as to include direction preserving paths in a space with a nice order on it. The elements of such are said to be directed paths. Such directed spaces have been applied to modelling non-reversible situations such as occur in the study of concurrent and distributed computing. To study such settings, various analogues of the fundamental groupoid construction have been proposed for d-spaces, but, for the applications, certain hoped for behaviour has been hard to achieve, with various often quite simply defined examples acting as a test bed for the evaluation of the attempted constructions.
In this paper, the author constructs a `pair component category' as a quotient, via a natural action of a certain monoid of `inessential maps', of a category of reachable pairs of points. The pair component category has as objects pair components along which the homotopy type of the path space between the points does not change. This builds on and refines work by \textit{L. Fajstrup} et al. [Appl. Categ. Struct. 12, No. 1, 81--108 (2004; Zbl 1078.55020)] and more recently by subsets of that list of authors. It removes some of the restrictions on the applicability of those earlier results. An evaluation and comparison of some of the various variants is given, and a discussion of directions for future work is included.
Reviewer: Timothy Porter (Llandegfan)Cryptanalysis of CLT13 multilinear maps with independent slots.https://www.zbmath.org/1455.941432021-03-30T15:24:00+00:00"Coron, Jean-Sébastien"https://www.zbmath.org/authors/?q=ai:coron.jean-sebastien"Notarnicola, Luca"https://www.zbmath.org/authors/?q=ai:notarnicola.lucaSummary: Many constructions based on multilinear maps require independent slots in the plaintext, so that multiple computations can be performed in parallel over the slots. Such constructions are usually based on CLT13 multilinear maps, since CLT13 inherently provides a composite encoding space, with a plaintext ring \(\bigoplus_{i=1}^n \mathbb{Z}/g_i\mathbb{Z}\) for small primes \(g_i\)'s. However, a vulnerability was identified at [\textit{C. Gentry} et al., Lect. Notes Comput. Sci. 8616, 426--443 (2014; Zbl 1345.94064)], with a lattice-based attack in dimension 2, and the authors have suggested a simple countermeasure. In this paper, we identify an attack based on higher dimension lattice reduction that breaks the author's countermeasure for a wide range of parameters. Combined with the \textit{J. Cheon} et al. [Lect. Notes Comput. Sci. 9056, 3--12 (2015; Zbl 1365.94416)] attack, this leads to the recovery of all the secret parameters of CLT13, assuming that low-level encodings of almost zero plaintexts are available. We show how to apply our attack against various constructions based on composite-order CLT13. For the [\textit{R. Fernando} et al., ibid. 10626, 242--271 (2017; Zbl 1417.94060)] construction, our attack enables to recover the secret CLT13 plaintext ring for a certain range of parameters; however, breaking the indistinguishability of the branching program remains an open problem.
For the entire collection see [Zbl 1428.94009].Order-LWE and the hardness of ring-LWE with entropic secrets.https://www.zbmath.org/1455.942042021-03-30T15:24:00+00:00"Bolboceanu, Madalina"https://www.zbmath.org/authors/?q=ai:bolboceanu.madalina"Brakerski, Zvika"https://www.zbmath.org/authors/?q=ai:brakerski.zvika"Perlman, Renen"https://www.zbmath.org/authors/?q=ai:perlman.renen"Sharma, Devika"https://www.zbmath.org/authors/?q=ai:sharma.devikaSummary: We propose a generalization of the celebrated Ring Learning with Errors (RLWE) problem [\textit{V. Lyubashevsky} et al., Lect. Notes Comput. Sci. 6110, 1--23 (2010; Zbl 1279.94099); ibid. 7881, 35--54 (2013; Zbl 1300.94082)], wherein the ambient ring is not the ring of integers of a number field, but rather an order (a full rank subring). We show that our Order-LWE problem enjoys worst-case hardness with respect to Short-Vector problems in invertible-ideal lattices of the order.
We show that Order-LWE can naturally be harnessed to prove security for RLWE instances where the ``RLWE secret'' (which often corresponds to the secret-key of a cryptosystem) is not sampled uniformly as required for RLWE hardness. We start by showing worst-case hardness even if the secret is sampled from a subring of the sample space. Then, we study the case where the secret is sampled from an ideal of the sample space or a coset thereof (equivalently, some of its CRT coordinates are fixed or leaked). In the latter, we show an interesting threshold phenomenon where the amount of RLWE noise determines whether the problem is tractable.
Lastly, we address the long standing question of whether high-entropy secret is sufficient for RLWE to be intractable. Our result on sampling from ideals shows that simply requiring high entropy is insufficient. We therefore propose a broad class of distributions where we conjecture that hardness should hold, and provide evidence via reduction to a concrete lattice problem.
For the entire collection see [Zbl 1428.94009].Path querying with conjunctive grammars by matrix multiplication.https://www.zbmath.org/1455.680772021-03-30T15:24:00+00:00"Azimov, R."https://www.zbmath.org/authors/?q=ai:azimov.r"Grigorev, S."https://www.zbmath.org/authors/?q=ai:grigorieff.serge|grigorev.stepan-andreevich|grigorev.s-l|grigorev.s-y|grigorev.s-a|grigorev.s-v.1|grigorev.s-g.1|grigorev.semyon|grigorev.s-nSummary: Problems in many areas can be reduced to one of the formal-languages-constrained path problems. Conjunctive grammars are more expressive than context-free grammars and are used, for example, in static analysis to describe an interleaved matched-parentheses language, which is not context-free. Path querying with conjunctive grammars is known to be undecidable. There is an algorithm for path querying with linear conjunctive grammars which provides an over-approximation of the result, but there is no algorithm for arbitrary conjunctive grammars. We propose the first algorithm for path querying with arbitrary conjunctive grammars. The proposed algorithm is matrix-based and allows us to efficiently apply GPGPU (General-Purpose computing on Graphics Processing Units) computing techniques and other optimizations for matrix operations.Parameter estimation for continuous time hidden Markov processes.https://www.zbmath.org/1455.931922021-03-30T15:24:00+00:00"Kutoyants, Yu. A."https://www.zbmath.org/authors/?q=ai:kutoyants.yury-aSummary: A survey of research works on the parameter estimation of hidden Markov processes is presented. Two observation models are considered: a partially observed two-dimensional Gaussian process and a telegraph process observed against the background of white Gaussian noise. The properties of estimators in the large sample and small noise asymptotics are described. Special attention is paid to the computational complexity and asymptotic efficiency of the estimators proposed.Fixing monotone Boolean networks asynchronously.https://www.zbmath.org/1455.680812021-03-30T15:24:00+00:00"Aracena, Julio"https://www.zbmath.org/authors/?q=ai:aracena.julio"Gadouleau, Maximilien"https://www.zbmath.org/authors/?q=ai:gadouleau.maximilien"Richard, Adrien"https://www.zbmath.org/authors/?q=ai:richard.adrien"Salinas, Lilian"https://www.zbmath.org/authors/?q=ai:salinas.lilianSummary: The asynchronous automaton associated with a Boolean network \(f : \{0, 1\}^n \to \{0, 1\}^n\) is considered in many applications. It is the finite deterministic automaton with set of states \(\{0, 1\}^n\), alphabet \(\{1, \ldots, n\}\), where the action of letter \(i\) on a state \(x\) consists in switching the \(i\) th component if \(f_i(x) \neq x_i\) or doing nothing otherwise. This action is extended to words in the natural way. We then say that a word \(w\) fixes \(f\) if, for all states \(x\), the result of the action of \(w\) on \(x\) is a fixed point of \(f\). In this paper, we ask for the existence of fixing words, and their minimal length. Firstly, our main results concern the minimal length of words that fix \textit{monotone} networks. We prove that there exists a monotone network \(f\) with \(n\) components such that any word fixing \(f\) has length \(\Omega (n^2)\). Conversely, we construct a word of length \(O (n^3)\) that fixes all monotone networks with \(n\) components. Secondly, we refine and extend our results to different classes of networks.Model-based sketching and recovery with expanders.https://www.zbmath.org/1455.940462021-03-30T15:24:00+00:00"Bah, Bubacarr"https://www.zbmath.org/authors/?q=ai:bah.bubacarr"Baldassarre, Luca"https://www.zbmath.org/authors/?q=ai:baldassarre.luca"Cevher, Volkan"https://www.zbmath.org/authors/?q=ai:cevher.volkanDolev-Yao theory with associative blindpair operators.https://www.zbmath.org/1455.941222021-03-30T15:24:00+00:00"Baskar, A."https://www.zbmath.org/authors/?q=ai:baskar.anguraj"Ramanujam, R."https://www.zbmath.org/authors/?q=ai:ramanujam.rohit-sunkam|ramanujam.ryan|ramanujam.ramaswamy"Suresh, S. P."https://www.zbmath.org/authors/?q=ai:suresh.s-pSummary: In the context of modeling cryptographic tools like blind signatures and homomorphic encryption, the Dolev-Yao model is typically extended with an operator over which encryption is distributive. The intruder deduction problem has a non-elementary upper bound when the extended operator is an abelian group operator. Here we show that the intruder deduction problem is DEXPTIME-complete when we restrict the operator to satisfy only the associative property. We propose an automata-based analysis for the upper bound and use the reachability problem for alternating pushdown systems to show the lower bound.
For the entire collection see [Zbl 1437.68010].How to smooth entropy?https://www.zbmath.org/1455.940822021-03-30T15:24:00+00:00"Skorski, Maciej"https://www.zbmath.org/authors/?q=ai:skorski.maciejSummary: Smooth entropy of \(X\) is defined as possibly biggest entropy of a distribution \(Y\) close to \(X\). It has found many applications including privacy amplification, information reconciliation, quantum information theory and even constructing random number generators. However the basic question about the optimal shape for the distribution \(Y\) has not been answered yet. In this paper we solve this problem for Rényi entropies in non-quantum settings, giving a formal treatment to an approach suggested at \textit{R. Renner} and \textit{R. König} [Lect. Notes Comput. Sci. 3378, 407--425 (2005; Zbl 1079.94570)] and \textit{R. Renner} and \textit{S. Wolf} [ibid. 3788, 199--216 (2005; Zbl 1154.94471)]. The main difference is that we use a threshold cut instead of a quantile cut to rearrange probability masses of \(X\). As an example of application, we derive tight lower bounds on the number of bits extractable from Shannon memoryless sources.
For the entire collection see [Zbl 1330.68022].Reducing the domination number of graphs via edge contractions and vertex deletions.https://www.zbmath.org/1455.050552021-03-30T15:24:00+00:00"Galby, Esther"https://www.zbmath.org/authors/?q=ai:galby.esther"Lima, Paloma T."https://www.zbmath.org/authors/?q=ai:lima.paloma-t"Ries, Bernard"https://www.zbmath.org/authors/?q=ai:ries.bernardSummary: In this work, we study the following problem: given a connected graph \(G\), can we reduce the domination number of \(G\) by at least one using \(k\) edge contractions, for some fixed integer \(k > 0\)? We show that for \(k = 1\) (resp. \( k = 2)\), the problem is NP-hard (resp. coNP-hard). We further prove that for \(k = 1\), the problem is \textsf{W}[1]-hard parameterized by domination number plus the mim-width of the input graph, and that it remains NP-hard when restricted to chordal \(\{P_6, P_4 + P_2\} \)-free graphs, bipartite graphs and \(\{C_3, \ldots , C_\ell \} \)-free graphs for any \(\ell \geq 3\). We also show that for \(k = 1\), the problem is coNP-hard on subcubic claw-free graphs, subcubic planar graphs and on \(2 P_3\)-free graphs. On the positive side, we show that for any \(k \geq 1\), the problem is polynomial-time solvable on \((P_5 + p K_1)\)-free graphs for any \(p \geq 0\) and that it can be solved in \(\mathsf{FPT} \)-time and \(\mathsf{XP}\)-time when parameterized by treewidth and mim-width, respectively. Finally, we start the study of the problem of reducing the domination number of a graph via vertex deletions and edge additions and, in this case, present a complexity dichotomy on \(H\)-free graphs.Adaptive computation of the symmetric nonnegative matrix factorization (SymNMF).https://www.zbmath.org/1455.652462021-03-30T15:24:00+00:00"Favati, P."https://www.zbmath.org/authors/?q=ai:favati.paola"Lotti, G."https://www.zbmath.org/authors/?q=ai:lotti.grazia"Menchi, O."https://www.zbmath.org/authors/?q=ai:menchi.ornella"Romani, F."https://www.zbmath.org/authors/?q=ai:romani.francescoSummary: Symmetric Nonnegative Matrix Factorization (SymNMF) provides a symmetric nonnegative low rank decomposition of symmetric matrices. It has found application in several domains such as data mining, bioinformatics and graph clustering. In this paper SymNMF is obtained by solving a penalized nonsymmetric minimization problem. Instead of letting the penalizing parameter increase according to an a priori fixed rule, as suggested in literature, we propose a heuristic approach based on an adaptive technique. The factorization is performed by applying, as inner-outer procedure, the Alternating Nonnegative Least Squares (ANLS). The inner problems are solved by two nonnegative quadratic optimization methods: an Active-Set-like method (BPP) and the Greedy Coordinate Descent method (GCD). Extensive experimentation shows that the proposed heuristic approach is effective with both the inner methods, GCD outperforming BPP in terms of computational time complexity.On the dimension of matrix embeddings of torsion-free nilpotent groups.https://www.zbmath.org/1455.200242021-03-30T15:24:00+00:00"Gul, Funda"https://www.zbmath.org/authors/?q=ai:gul.funda"Weiß, Armin"https://www.zbmath.org/authors/?q=ai:weiss.arminSummary: Since the work of \textit{S. A. Jennings} [Can. J. Math. 7, 169--187 (1955; Zbl 0066.01302)], it is well-known that any finitely generated torsion-free nilpotent group can be embedded into unitriangular integer matrices \(U T_N(\mathbb{Z})\) for some \(N\). \textit{W. Nickel} [J. Algebra 300, No. 1, 376--383 (2006; Zbl 1107.20014)] proposed an algorithm to calculate such embeddings. In this work, we show that if \(U T_n(\mathbb{Z})\) is embedded into \(U T_N(\mathbb{Z})\) using Nickel's algorithm, then \(N \geq 2^{n / 2 - 2}\) if the standard ordering of the Mal'cev basis (as in Nickel's original paper) is used. In particular, we establish an exponential worst-case running time of Nickel's algorithm. On the other hand, we also prove a general exponential upper bound on the dimension of the embedding by showing that for any torsion free, finitely generated nilpotent group the matrix representation produced by Nickel's algorithm has never larger dimension than Jennings' embedding. Moreover, when starting with a special Mal'cev basis, Nickel's embedding for \(U T_n(\mathbb{Z})\) has only quadratic size. Finally, we consider some special cases like free nilpotent groups and Heisenberg groups and compare the sizes of the embeddings.Approximation of set multi-cover via hypergraph matching.https://www.zbmath.org/1455.681392021-03-30T15:24:00+00:00"Gorgi, Abbass"https://www.zbmath.org/authors/?q=ai:gorgi.abbass"El Ouali, Mourad"https://www.zbmath.org/authors/?q=ai:el-ouali.mourad"Srivastav, Anand"https://www.zbmath.org/authors/?q=ai:srivastav.anand"Hachimi, Mohamed"https://www.zbmath.org/authors/?q=ai:hachimi.mohamedSummary: For a given \(\mathbf{b} \in \mathbb{N}^n\) and a hypergraph \(\mathcal{H} = (V, \mathcal{E})\) with maximum degree \(\Delta\), the \textbf{b}-set multicover problem which we are concerned with in this paper may be stated as follows: find a minimum cardinality subset \(\mathcal{C} \subseteq \mathcal{E}\) such that no vertex \(v_i \in V\) is contained in less than \(b_i\) hyperedges of \(\mathcal{C}\).
\textit{D. Peleg} et al. [Algorithmica 18, No. 1, 44--66 (1997; Zbl 0873.68077)] conjectured that for any fixed \(\Delta\) and \(b = \min_i b_i\), the problem cannot be approximated with a ratio strictly smaller than \(\delta := \Delta - b + 1\), unless \(\mathcal{P} = \mathcal{NP}\). In this paper, we show that the conjecture of Peleg et al. is not true on \(\ell\)-uniform hypergraphs by presenting a polynomial-time approximation algorithm based on a matching/covering duality for hypergraphs due to
Ray-Chaudhuri (1960),
which we convert into an approximative form. The given algorithm yields a ratio smaller than \((1 - \frac{b}{(\ell + 1) \Delta}) \frac{\Delta}{b}\). Moreover, we prove that the lower bound conjectured by Peleg et al. holds for regular hypergraphs under the unique games conjecture.Card-based protocols for secure ranking computations.https://www.zbmath.org/1455.680662021-03-30T15:24:00+00:00"Takashima, Ken"https://www.zbmath.org/authors/?q=ai:takashima.ken"Abe, Yuta"https://www.zbmath.org/authors/?q=ai:abe.yuta"Sasaki, Tatsuya"https://www.zbmath.org/authors/?q=ai:sasaki.tatsuya"Miyahara, Daiki"https://www.zbmath.org/authors/?q=ai:miyahara.daiki"Shinagawa, Kazumasa"https://www.zbmath.org/authors/?q=ai:shinagawa.kazumasa"Mizuki, Takaaki"https://www.zbmath.org/authors/?q=ai:mizuki.takaaki"Sone, Hideaki"https://www.zbmath.org/authors/?q=ai:sone.hideakiSummary: Consider a group of people who want to know the ``rich list'' among them, namely the ranking in terms of their total assets, without revealing any information about the actual value of their assets. This can be achieved by a ``secure ranking computation,'' which was first considered by
\textit{S. Jiang} and \textit{G. Gong} [Lect. Notes Comput. Sci. 3860, 350--364 (2006; Zbl 1125.94023)]; they constructed a secure ranking computation protocol based on a public-key cryptosystem. In this paper, instead of using a public-key cryptosystem, we use a deck of physical cards to provide secure ranking computation protocols. Therefore, our card-based protocols do not rely on computers, and they are simple and easy for humans to implement. Specifically, we design four protocols considering tradeoffs between the number of cards and the number of shuffles required to execute the protocols. We also present a guide to choose an appropriate protocol according to the number of people participating in the protocol and the size of the input range. To be precise, whereas our protocols make all players know the rich list, the Jiang-Gong scheme makes each player know his/her rank only; to achieve the same task (as the Jiang-Gong scheme) using a deck of cards is an intriguing open problem.Tight space bounds for two-dimensional approximate range counting.https://www.zbmath.org/1455.680472021-03-30T15:24:00+00:00"Wei, Zhewei"https://www.zbmath.org/authors/?q=ai:wei.zhewei"Yi, Ke"https://www.zbmath.org/authors/?q=ai:yi.keComputer says no: verdict explainability for runtime monitors using a local proof system.https://www.zbmath.org/1455.681032021-03-30T15:24:00+00:00"Francalanza, Adrian"https://www.zbmath.org/authors/?q=ai:francalanza.adrian"Cini, Clare"https://www.zbmath.org/authors/?q=ai:cini.clareSummary: Monitors in Runtime Verification are often constructed as black boxes: they provide verdicts on whether a property is satisfied or violated by the executing system under scrutiny, without much explanation as to why this is the case. In the best of cases, monitors might also return the trace observed, still leaving it up to the user to figure out the logic employed to reach the declared verdict from this trace. In this paper, we propose a local proof system for Linear Temporal Logic -- a popular logic used in Runtime Verification -- formalising the symbolic deductions within the constraints of Runtime Verification. We prove novel soundness and partial completeness results for this proof system with respect to the original semantics of the logic. Crucially, we show how such a deductive system can be used as a realistic basis for constructing online runtime monitors that provide explanations for their verdicts; we also show the resulting monitor algorithms to satisfy pleasing correctness criteria identified by other works, such as the decidability and incrementality of the analysis and the irrevocability of verdicts. Finally, we relate the expressiveness of the Linear Temporal Logic proof system to existing symbolic analysis techniques used in Runtime Verification.Weak completeness notions for exponential time.https://www.zbmath.org/1455.680682021-03-30T15:24:00+00:00"Ambos-Spies, Klaus"https://www.zbmath.org/authors/?q=ai:ambos-spies.klaus"Bakibayev, Timur"https://www.zbmath.org/authors/?q=ai:bakibayev.timurIn the present paper, the authors investigate reduction notions that can be employed in the context of linear exponential time (E).
It is well known that the complexity class E is not closed under polynomial many-to-one reductions (Lemma 1) through a padding argument.
Because of that, \textit{J. H. Lutz} [SIAM J. Comput. 24, No. 6, 1170--1189 (1995; Zbl 0845.68048)] formalised in a way a type of measure for that class.
The authors introduce two weak hardness notions for E, namely, (strong) E-nontriviality.
Intuitively, a subclass of E is negligible if it is contained in some \(\mathrm{E}_k= \mathrm{DTIME}(2^{kn})\) in the exponential-time hierarchy.
Arguing that ``E-nontriviality is the most general weak hardness notion for E'', the authors stress that it ``generalised E-hardness and implies intractability but that it also reflects the internal, hierarchical structure of E hence considers finite parts of the linear exponential time hierarchy to be negligible.''
The strong variant of this concept lies strictly between the weak notion and the ones of measure- and category-hardnesses.
The authors give a verbose overview of the sections in the introduction and motivate quite well.
Section 2 then handles the new central notions and Lemma 3 is an important result showing how meaningful their approach is.
Theorem 1 characterises the strong variant via \(\mathrm{E}_1\)-bi-immune sets (a set \(A\) is \(C\)-bi-immune for a class \(C\) if there is no infinite \(B\in C\) such that \(B\subseteq A\) or \(B\cap A=\emptyset\)).
Section 3 provides then some examples.
First, the existence of an E-trivial set in \(\mathrm{E}\setminus \mathrm{P}\) (Theorem 2), but also E-trivial sets in arbitrarily high levels \(\mathrm{E}\setminus \mathrm{E}_k\) of the E-hierarchy (Theorem 4).
Section 4 considers sparse and tally sets in this context.
The authors show the existence of an E-category-complete set which is sparse and that no such set is tally (Theorem 8).
Yet, there are tally sets which are strongly E-nontrivial (Theorem 9).
The authors show the context when tally sets are E-nontrivial (Theorem 10) and when even an E-nontrivial set is exptally (Corollary 2) which is also not strongly E-nontrivial (Corollary 3).
Theorem 13 then gives the context for a set \(A\) to be E-hard, E-measure-hard, E-category-hard, strongly E-nontrivial, E-nontrivial, and intractable (in this order).
Section 5 talks about information content. Can one, from splitting ``a weakly complete set \(A\) into two parts \(A_0\) and \(A_1\)'', deduce weak completeness for either of them?
The authors show that this is true for E-nontriviality but for the remainder of the weak completeness notions this is false.
Reviewer: Arne Meier (Hannover)The \(C_\pi\)-calculus: a model for confidential name passing.https://www.zbmath.org/1455.681282021-03-30T15:24:00+00:00"Prokić, Ivan"https://www.zbmath.org/authors/?q=ai:prokic.ivan"Vieira, Hugo Torres"https://www.zbmath.org/authors/?q=ai:vieira.hugo-torresSummary: Sharing confidential information in distributed systems is often a necessity in the context of many applications, however, it opens the problem of controlling information sharing even among trusted parties. In this paper, we present a formal model in which dissemination of information, in particular information \textit{forwarding}, is not allowed. Namely, we introduce a fragment of the \(\pi\)-calculus where forwarding of channels is disabled directly at the level of the syntax. This is the only difference with respect to the \(\pi\)-calculus, i.e., that channels that are received cannot be forwarded later on. Apart from the presentation of the language, we also address a preliminary investigation in the behavioral theory of the model. Furthermore, by means of examples, we give an idea of how some privacy notions already studied in the past, such as group creation and name hiding, can be represented in our language, in contrast with previous approaches that required additional language constructs. Finally, we present an encoding of the (sum-free) \(\pi\)-calculus in our calculus and prove operational correspondence. Our encoding allows to put focus on a notion of name ownership that arises in the process model, by confining the name sending capability to well-determined processes which may be of use for security purposes but also for other resource control properties.Checking deadlock-freedom of parametric component-based systems.https://www.zbmath.org/1455.681022021-03-30T15:24:00+00:00"Bozga, Marius"https://www.zbmath.org/authors/?q=ai:bozga.marius"Iosif, Radu"https://www.zbmath.org/authors/?q=ai:iosif.radu"Sifakis, Joseph"https://www.zbmath.org/authors/?q=ai:sifakis.josephSummary: We propose an automated method for computing inductive invariants used to proving deadlock freedom of parametric component-based systems. The method generalizes the approach for computing structural trap invariants from bounded to parametric systems with general architectures. It symbolically extracts trap invariants from interaction formulae defining the system architecture. The paper presents the theoretical foundations of the method and proves its soundness. It also reports on a preliminary experimental evaluation on several textbook examples.Runtime verification for dynamic architectures.https://www.zbmath.org/1455.681062021-03-30T15:24:00+00:00"Marmsoler, Diego"https://www.zbmath.org/authors/?q=ai:marmsoler.diego"Petrovska, Ana"https://www.zbmath.org/authors/?q=ai:petrovska.anaSummary: The architecture of a system captures important design decisions for the system. Over time, changes in a system's implementation may lead to violations of specific design decisions. This problem is common in industry and known as architectural erosion. Since it may have severe consequences on the quality of a system, research has focused on the development of tools and techniques to address the presented problem. As of today, most of the approaches to detect architectural erosion employ static analysis techniques. While these techniques are well-suited for the analysis of static architectures, they reach their limit when it comes to dynamic architectures. Thus, in this paper, we propose an alternative approach based on runtime verification: We describe techniques to formally specify constraints for dynamic architectures and algorithms to translate such specifications to instrumentation code and corresponding monitors. The approach is implemented in Eclipse/EMF, demonstrated through a running example, and evaluated using two case studies.On generic NP-completeness of the problem of Boolean circuits satisfiability.https://www.zbmath.org/1455.680712021-03-30T15:24:00+00:00"Rybalov, A. N."https://www.zbmath.org/authors/?q=ai:rybalov.aleksandr-nikolaevichSummary: Generic-case approach to algorithmic problems was suggested by \textit{I. Kapovich} et al. [J. Algebra 264, No. 2, 665--694 (2003; Zbl 1041.20021)]. This approach studies behavior of an algorithm on typical (almost all) inputs and ignores the rest of inputs. In [Prikl. Diskretn. Mat. 2017, No. 2(36), 106--112 (2017; Zbl 07311426)], we introduced a concept of polynomial generic reducibility of algorithmic problem that preserves the decidability property problems for almost all inputs and has the property of transitivity, and proved that the classical problem of the satisfiability of Boolean formulas is complete with respect to this reducibility in the generic analogue of class NP. Then the Boolean formulas were represented by binary labeled trees. In this paper, we prove the generic NP-completeness of the satisfiability problem for the so-called Boolean circuits. Boolean circuit is a way to represent Boolean functions, which show how the value of a Boolean function is obtained from values of variables using logical connectives. Boolean circuits are convenient models for the development of microprocessors, and are also the most important object of studying in computational complexity theory. Boolean circuit contains a finite number of variables \(x_1, \ldots, x_n\). Every variable \(x_i\) can be either input, or defined through other variables by assigning one of the following types: \(x_i = x_j \vee x_k\) or \(x_j \wedge x_k\), where \(j, k <i\); \(x_i = \neg x_j\) or \(x_j \), where \(j <i\). The last variable \(x_n\) of the circuit is called output. By the size of a Boolean circuit we mean the number of variables in it. The number of Boolean circuits of size \(n\) is \(\prod\limits_{m = 1}^n (1 + 2 (m-1)^2 + 2(m-1) )\).Soft constraint automata with memory.https://www.zbmath.org/1455.680872021-03-30T15:24:00+00:00"Dokter, Kasper"https://www.zbmath.org/authors/?q=ai:dokter.kasper"Gadducci, Fabio"https://www.zbmath.org/authors/?q=ai:gadducci.fabio"Lion, Benjamin"https://www.zbmath.org/authors/?q=ai:lion.benjamin"Santini, Francesco"https://www.zbmath.org/authors/?q=ai:santini.francescoSummary: We revise \textit{soft constraint automata}, wherein transitions are weighted and each action has an associated preference value. We first relax the underlying algebraic structure to allow bipolar preferences. We then equip automata with memory locations, that is, with an internal state to remember and update information from transition to transition. We furthermore revise automata operators, such as composition and hiding, providing examples on how such memory locations interact with preferences. We finally apply our framework to encode context-sensitive behaviour.A study on complexity measure of diamond tile self-assembly system.https://www.zbmath.org/1455.680582021-03-30T15:24:00+00:00"Kalyani, M. Nithya"https://www.zbmath.org/authors/?q=ai:kalyani.m-nithya"Chandra, P. Helen"https://www.zbmath.org/authors/?q=ai:chandra.p-helen"Kalavathy, S. M. Saroja T."https://www.zbmath.org/authors/?q=ai:kalavathy.s-m-saroja-tSummary: Molecular self-assembly gives rise to a great diversity of complex forms from crystals and DNA helices to microtubules and holoenzymes. We study a formal self-assembly model called the Diamond Tile Assembly System in which a diamond tile may be added to the growing object when the total interaction strength with its neighbours exceeds a parameter \(\mathcal{T}\). Self-assembled objects can also be studied from the point of view of computational complexity. Here, we define the program-size complexity of an \(N\times N\) diamond to be the minimum number of distinct tiles required to self-assemble the diamond. We study this complexity under the Diamond Tile Assembly Model and find a dramatic decrease in complexity from \(N^2\) tiles to \(O(\log N)\) tiles, as \(\mathcal{T}\) is increased from 1 where bonding is non co-operative to 2 allowing co-operative bonding. Further, we observe that the size of the largest diamond uniquely produced by a set of \(n\) tiles grows faster than any computable function.
For the entire collection see [Zbl 1411.65006].Are binary codings universal?https://www.zbmath.org/1455.680732021-03-30T15:24:00+00:00"Calcude, Cristian"https://www.zbmath.org/authors/?q=ai:calcude.cristian"Campeanu, Cezar"https://www.zbmath.org/authors/?q=ai:campeanu.cezarSummary: It is common sense to notice that one needs fewer digits to code numbers in ternary than in binary; new names are about \(\log _32\) times shorter. Is this trade-off a consequence of the special coding scheme? The answer is negative. More generally, we argue that the answer to the question, stated in the title and formulated to the first author by C. Rackhoff, is in fact negative. The conclusion will be achieved by studying the role of the size of the alphabet in constructing instantaneous codes for all natural numbers, and defining random strings and sequences. We show that there is no optimal instantaneous code for all positive integers, and the binary is the worst possible. Codes over a fixed alphabet can be indefinitely improved themselves, but only ``slightly''; in contrast, changing the size of the alphabet determines a significant, not linear, improvement. The key relation describing the above phenomenon can be expressed in terms of Chaitin complexity: changing the size of the coding alphabet from \(q\) to \(Q\), \(2 \le q<Q\), results in an improvement of the complexity by a factor of \(\log _Qq\).
As a consequence, a string avoiding consistently a fixed letter is not random. In binary, this corresponds to a trivial situation. In the nonbinary case the distinction is relevant: more than \(3.2^n\) ternary strings of length \(n\) are not random (many of these strings are binary random). This phenomenon is even sharper for infinite sequences.Propagation of local interactions create global gap structure and dynamics in a tropical rainforest.https://www.zbmath.org/1455.921542021-03-30T15:24:00+00:00"Pagnutti, C."https://www.zbmath.org/authors/?q=ai:pagnutti.christopher"Azzouz, M."https://www.zbmath.org/authors/?q=ai:azzouz.mohamed-s"Anand, M."https://www.zbmath.org/authors/?q=ai:anand.madhurSummary: Gap dynamics in tropical forests are of interest because an understanding of them can help to predict canopy structure and biodiversity. We present a simple cellular automaton model that is capable of capturing many of the trends seen in the canopy gap pattern of a complex tropical rainforest on the Barro Colorado Island (BCI) using a single set of model parameters. We fit the global and local densities, the cluster size distributions, and two correlation functions, for gaps, gap formations, and gap closures determined from a spatial map of the forest (1983--1984). To the best of our knowledge, this is the first report that the cluster size distributions of gap formations and closures in the BCI are both power laws. An important element in the model is that when a transition from gap to non-gap (closure), or vice versa (formation), occurs, this transition is allowed to expand into adjacent cells in order to make different cluster sizes of transitions. Model results are in excellent agreement with reported field data. The propagation of local interactions is necessary in order to obtain the complex dynamics of the gap pattern. We also establish a connection between the global and local densities via the neighborhood-dependent transition rates and the effective global transition rates.Cellular automata and the sciences of complexity. A review of some outstanding problems in the theory of cellular automata.https://www.zbmath.org/1455.681112021-03-30T15:24:00+00:00"Gutowitz, Howard"https://www.zbmath.org/authors/?q=ai:gutowitz.howard-aSummary: This two-part article reviews selected problems in the theory of cellular automata with the aim of locating this theory within the general theory of complex systems.A new version of algorithmic information theory.https://www.zbmath.org/1455.680742021-03-30T15:24:00+00:00"Chaitin, G. J."https://www.zbmath.org/authors/?q=ai:chaitin.gregory-jSummary: We present a much more concrete version of algorithmic information theory in which one can actually run on a computer the algorithms in the proofs of a number of key information-theoretic incompleteness theorems.Cellular automata and the sciences of complexity. II.https://www.zbmath.org/1455.681102021-03-30T15:24:00+00:00"Gutowitz, Howard"https://www.zbmath.org/authors/?q=ai:gutowitz.howard-aSummary: This is the final half of a review of selected problems in the theory of cellular automata. For Part I, see [the author, ibid. 1, No. 5, 16--22 (1996; Zbl 1455.68111)].Finite-state complexity and the size of transducers.https://www.zbmath.org/1455.680842021-03-30T15:24:00+00:00"Calude, Cristian S."https://www.zbmath.org/authors/?q=ai:calude.cristian-s"Salomaa, Kai"https://www.zbmath.org/authors/?q=ai:salomaa.kai-t"Roblot, Tania K."https://www.zbmath.org/authors/?q=ai:roblot.tania-kSummary: Finite-state complexity is a variant of algorithmic information theory obtained by replacing Turing machines with finite transducers. We consider the state-size of transducers needed for minimal descriptions of arbitrary strings and, as our main result, we show that the state-size hierarchy with respect to a standard encoding is infinite. We consider also hierarchies yielded by more general computable encodings.
For the entire collection see [Zbl 1392.68027].Deterministic fuzzy automaton on subclasses of fuzzy regular \(\omega\)-languages.https://www.zbmath.org/1455.680822021-03-30T15:24:00+00:00"Arulprakasam, R."https://www.zbmath.org/authors/?q=ai:arulprakasam.r"Dare, V. R."https://www.zbmath.org/authors/?q=ai:dare.vincent-rajkumar"Gnanasekara, S."https://www.zbmath.org/authors/?q=ai:gnanasekara.sSummary: In formal language theory, we are mainly interested in the natural language computational aspects of \(\omega\)-languages. Therefore in this respect it is convenient to consider fuzzy \(\omega\)-languages. In this paper, we introduce two subclasses of fuzzy regular \(\omega\)-languages called fuzzy \(n\)-local \(\omega\)-languages and Buchi fuzzy \(n\)-local \(\omega\)-languages, and give some closure properties for those subclasses. We defi ne a deterministic fuzzy automaton acceptance conditions on fuzzy \(\omega\)-languages and fuzzy \(n\)-local automaton. The relationship between deterministic fuzzy \(n\)-local automaton and two subclasses of fuzzy regular \(\omega\)-languages are established and proved that every fuzzy \(\omega\)-language accepted by a deterministic fuzzy automaton in 2-mode is a projection of a Buchi fuzzy 2-local \(\omega\)-language.Hardness and ease of curing the sign problem for two-local qubit Hamiltonians.https://www.zbmath.org/1455.810152021-03-30T15:24:00+00:00"Klassen, Joel"https://www.zbmath.org/authors/?q=ai:klassen.joel"Marvian, Milad"https://www.zbmath.org/authors/?q=ai:marvian.milad"Piddock, Stephen"https://www.zbmath.org/authors/?q=ai:piddock.stephen"Ioannou, Marios"https://www.zbmath.org/authors/?q=ai:ioannou.marios"Hen, Itay"https://www.zbmath.org/authors/?q=ai:hen.itay"Terhal, Barbara M."https://www.zbmath.org/authors/?q=ai:terhal.barbara-mThe paper is devoted to the complexity of the sign problem for two-local \(n\)-qubit Hamiltonians.
Let \(I,X,Y,Z\) be the identity and Pauli matrices,
a two-qubit Hamiltonian \(H = \sum_{k,l=I,X,Y,Z} a_{kl}\sigma_k \otimes \sigma_l\) is symmetric Z-matrix if and only if it is a real matrix, \(a_{IY} = s_{YI} = a_{XY}= a_{YX} = a_{ZY} = a_{YZ} = 0\),
and it has nonpositive off-diagonal elements \(a_{XX} < -|a_{YY}|, a_{IX} \leq -|a_{ZX}|, a_{XI} \leq -|a_{XZ}|\) (Proposition 4.1). For a given two-local \(n\)-qubit Hamiltonian, \texttt{LocalSignCure} is the problem for determining the existence of a set of single-qubit unitary transforms \(U= \bigotimes_{u=1}^n U_u,\) such that \(UHU^\dagger = H\) is a symmetric \(Z\)-matrix, where \(U_u \) are taken from the unitary group \(\mathrm{SU(2)}\) (Definition 3.1).
The main results of the paper are the two theorems: Theorem 3.2 stating that there exists a familty of a two-local \(n\)-qubit Hamiltonians for which the \texttt{LocalSignCure} is NP-complete. Theorem 3.3 states that for an exactly two-local \(n\)-qubit Hamiltonian \(H = \sum_{k,l=X,Y,Z} (\beta_{uv})_{kl}\sigma^u_k \otimes \sigma^v_l\) with matrix coefficient \(\beta_{uv}\) with \(O(1)\) bits, to solve \(\mathtt{LocalSignCure}\) there exists an efficient algorithm by using \(O(n^3)\) arithmetic operations over \(\mathbb R\) (Theorem 3.3).
Reviewer: Do Ngoc Diep (Hanoi)Breaking symmetries.https://www.zbmath.org/1455.681272021-03-30T15:24:00+00:00"Peters, Kirstin"https://www.zbmath.org/authors/?q=ai:peters.kirstin"Nestmann, Uwe"https://www.zbmath.org/authors/?q=ai:nestmann.uweSummary: A well-known result by Palamidessi tells us that \(\pi_\mathrm{mix}\) (the \(\pi\)-calculus with mixed choice) is more expressive than \(\pi_\mathrm{sep}\) (its subset with only separate choice). The proof of this result argues with their different expressive power concerning leader election in symmetric networks. Later on, Gorla offered an arguably simpler proof that, instead of leader election in symmetric networks, employed the reducibility of ``incestual'' processes (mixed choices that include both enabled senders and receivers for the same channel) when running two copies in parallel. In both proofs, the role of breaking (initial) symmetries is more or less apparent. In this paper, we shed more light on this role by re-proving the above result -- based on a proper formalization of what it means to break symmetries -- without referring to another layer of the distinguishing problem domain of leader election.
Both Palamidessi and Gorla rephrased their results by stating that there is no uniform and reasonable encoding from \(\pi_\mathrm{mix}\) into \(\pi_\mathrm{sep}\). We indicate how the respective proofs can be adapted and exhibit the consequences of varying notions of uniformity and reasonableness. In each case, the ability to break initial symmetries turns out to be essential.
For the entire collection see [Zbl 1415.68027].Formal modeling and analysis of timed systems. 18th international conference, FORMATS 2020, Vienna, Austria, September 1--3, 2020. Proceedings.https://www.zbmath.org/1455.680212021-03-30T15:24:00+00:00"Bertrand, Nathalie (ed.)"https://www.zbmath.org/authors/?q=ai:bertrand.nathalie"Jansen, Nils (ed.)"https://www.zbmath.org/authors/?q=ai:jansen.nilsThe articles of this volume will be reviewed individually. For the preceding conference see [Zbl 1428.68004].
Indexed articles:
\textit{Hasanbeig, Mohammadhosein; Kroening, Daniel; Abate, Alessandro}, Deep reinforcement learning with temporal logics, 1-22 [Zbl 1455.68190]
\textit{Nguyen Van, Hai; Balabonski, Thibaut; Boulanger, Frédéric; Keller, Chantal; Valiron, Benoît; Wolff, Burkhart}, On the semantics of polychronous polytimed specifications, 23-40 [Zbl 07317088]
\textit{Parrot, Rémi; Lime, Didier}, Backward symbolic optimal reachability in weighted timed automata, 41-57 [Zbl 07317089]
\textit{Wimmer, Simon; Herbreteau, Frédéric; van de Pol, Jaco}, Certifying emptiness of timed Büchi automata, 58-75 [Zbl 07317090]
\textit{Basset, Nicolas; Dang, Thao; Mambakam, Akshay; Requeno Jarabo, José Ignacio}, Learning specifications for labelled patterns, 76-93 [Zbl 07317091]
\textit{Brihaye, Thomas; Goeminne, Aline}, On subgame perfect equilibria in turn-based reachability timed games, 94-110 [Zbl 07317092]
\textit{Clement, Emily; Jéron, Thierry; Markey, Nicolas; Mentré, David}, Computing maximally-permissive strategies in acyclic timed automata, 111-126 [Zbl 07317093]
\textit{Kölbl, Martin; Leue, Stefan; Schmid, Robert}, Dynamic causes for the violation of timed reachability properties, 127-143 [Zbl 07317094]
\textit{Henry, Léo; Jéron, Thierry; Markey, Nicolas}, Active learning of timed automata with unobservable resets, 144-160 [Zbl 07317095]
\textit{Abate, Alessandro; Cimatti, Alessandro; Micheli, Andrea; Mufid, Muhammad Syifa'ul}, Computation of the transient in max-plus linear systems via SMT-solving, 161-177 [Zbl 07317096]
\textit{Qin, Xin; Deshmukh, Jyotirmoy V.}, Clairvoyant monitoring for signal temporal logic, 178-195 [Zbl 07317097]
\textit{Kempa, Brian; Zhang, Pei; Jones, Phillip H.; Zambreno, Joseph; Rozier, Kristin Yvonne}, Embedding online runtime verification for fault disambiguation on Robonaut2, 196-214 [Zbl 07317098]
\textit{Donatelli, Susanna; Haddad, Serge}, Guarded autonomous transitions increase conciseness and expressiveness of timed automata, 215-230 [Zbl 07317099]
\textit{Bacci, Edoardo; Parker, David}, Probabilistic guarantees for safe deep reinforcement learning, 231-248 [Zbl 07317100]
\textit{Jéron, Thierry; Markey, Nicolas; Mentré, David; Noguchi, Reiya; Sankur, Ocan}, Incremental methods for checking real-time consistency, 249-264 [Zbl 07317101]
\textit{Li, Dongxu; Bak, Stanley; Bogomolov, Sergiy}, Reachability analysis of nonlinear systems using hybridization and dynamics scaling, 265-282 [Zbl 07317102]
\textit{Granig, Wolfgang; Jakšić, Stefan; Lewitschnig, Horst; Mateis, Cristinel; Ničković, Dejan}, Weakness monitors for fail-aware systems, 283-299 [Zbl 07317103]Mathematics and computation. A theory revolutionizing technology and science.https://www.zbmath.org/1455.680042021-03-30T15:24:00+00:00"Wigderson, Avi"https://www.zbmath.org/authors/?q=ai:wigderson.aviOne might readily imagine numerous mathematical fields, expositions of which could easily fit under the title of this volume.
In the case of Avi Wigderson's book, it is computational complexity theory, which is meant to be a child of both mathematics and computer science ``revolutionizing technology and science''.
The book presents a broad selection of topics pertaining to computational complexity and closely related fields of theoretical computer science.
The material covered adheres more or less to what one would typically expect of a standard modern exposition of complexity theory (with the notable exception of Chapter 13, described below),
although its considerable breadth can only be compared with a limited number of other books in the area, such as the one of \textit{S. Arora} and \textit{B. Barak} [Computational complexity. A modern approach. Cambridge: Cambridge University Press (2009; Zbl 1193.68112)].
On the other hand, the style in which this material is presented is very far from being standard.
Though introductory in spirit, this book is not a textbook in the usual sense. The author's writing is \textit{intentionally} somewhere between semiformal and informal --
many important concepts are not rigorously defined and proofs are typically omitted. On the other hand, this is certainly not a popular science book either.
The book aims to explain ``the real thing'', although on a conceptual level and with heavy emphasis on intuition;
it is pretty dense with deep ideas, correct understanding of which undoubtedly requires some experience on the part of the reader. As such,
the book can perhaps most rightly be described as a travel guide -- and as each well-written travel guide, it will surely be best appreciated by the natives.
The book is divided into 20 chapters, with Chapter 1 as the Introduction. Intellectual roots of complexity theory in the study of computability
are briefly explained in Chapter 2.
The ``classical'' complexity theory, if such modifier makes sense in this context, is mostly covered in the next three chapters.
Chapter 3 covers the fundamentals of complexity theory -- complexity classes such as \(\mathbf{P}\), \(\mathbf{NP}\), and \(\mathbf{coNP}\)
are introduced and the concept of \(\mathbf{NP}\)-completeness is explained. While these live in the realm of decision problems,
Chapter 4 first introduces some other types of problems studied by complexity theory (such as optimisation and counting problems) and their complexity classes.
It is interesting that the polynomial hierarchy is introduced in this context, as a result of studying quantified problems.
Other topics discussed in Chapter 4 include \(\mathbf{NP}\)-intermediate problems and Ladner's theorem, constraint satisfaction problems, and average-case complexity.
Chapter 5 deals with classical approaches to the \(\mathbf{P}\) vs. \(\mathbf{NP}\) problem -- i.e., those based on relativisation and on proving lower bounds for Boolean circuits --
and their shortcomings.
Chapter 6, devoted to proof complexity, is followed by a series of chapters studying various aspects of randomness.
The complexity class \(\mathbf{BPP}\) is introduced in Chapter 7 and the reasons to believe that actually \(\mathbf{BPP} = \mathbf{P}\),
based on the notion of computational pseudo-randomness, are explored there as well. The notion of computational pseudo-randomness
is extended in Chapter 8 to what the author calls ``abstract'' pseudo-randomness. Both the Riemann hypothesis (through a more elementary equivalent statement)
and the \(\mathbf{P}\) vs. \(\mathbf{NP}\) problem are reinterpreted as questions about pseudo-randomness. Constructions of pseudo-random objects,
such as expander graphs, are discussed as well in Chapter 8. Chapter 9 focuses on weak random sources and randomness extractors, and Chapter 10 covers
proof systems frequently met in complexity theory: interactive proofs, zero-knowledge proofs, and probabilistically checkable proofs.
Chapter 11 focuses on quantum computing, including quantum interactive proof systems and quantum randomness. Chapter 12 discusses arithmetic complexity.
Chapter 13 is very different in nature from the rest of the book. It briefly describes several (sometimes unexpected) connections between complexity theory
and other parts of mathematics using a form of short tasters. Each section presents a connection to one mathematical field and the presentation is limited by design
to a single development per mathematical field. The topics covered in this chapter range from widely known ones, such as the Agrawal-Kayal-Saxena polynomial-time primality testing algorithm,
to topics for ``demanding readers'' (from the perspective of complexity theory), such as the Kadison-Singer problem of functional analysis.
While the first part of the book is largely centred around time complexity, Chapter 14 and Chapter 15 focus on two other important computational resources: space and
communication, respectively. Several applications of communication complexity are discussed in Chapter 15. Online algorithms are briefly touched upon in Chapter 16.
The following three chapters offer excursions to three major areas of theoretical computer science, more or less related to complexity theory.
Chapter 17 discusses computational learning theory and covers topics such as classification, probably approximately correct (PAC) learning and
the Vapnik-Chervonenkis dimension. Chapter 18 introduces selected topics in cryptography, and Chapter 19 does the same for distributed computing.
Finally, Chapter 20 offers the author's highly personal view of the theory of computation, its relations with other areas of science, and the theory of computation community.
Given the breadth of topics described above and the fact that the book is written at a highly informal level with accent on intuition, fundamental ideas, and interconnections between
them, the book appears to be well-suited especially for those interested in a bird's eye view of a familiar landscape of complexity theory. Avi Wigderson, one of the leading researchers
in the field, will undoubtedly be an inspiring guide.
Reviewer: Peter Kostolányi (Bratislava)Fixed point property for finite ordered sets that contain no crowns with 6 or more elements.https://www.zbmath.org/1455.060012021-03-30T15:24:00+00:00"Schröder, Bernd S. W."https://www.zbmath.org/authors/?q=ai:schroder.bernd-s-w.1|schroder.bernd-s-wA poset has the fixed point property if every endomorphism
has a fixed point. The problem of determining whether a
finite poset has the fixed point property is co-NP-complete.
This paper proves that the problem of determining whether
a finite poset which omits crowns of six or more elements
has the fixed point property is in P.
This result is established by first proving
that every finite, connected poset which omits
crowns of six or more elements either has
(i) an element of rank one that has a
unique lower cover or (ii) a retractable minimal element.
Reviewer: Keith Kearnes (Boulder)On well-founded and recursive coalgebras.https://www.zbmath.org/1455.180012021-03-30T15:24:00+00:00"Adámek, Jiří"https://www.zbmath.org/authors/?q=ai:adamek.jiri"Milius, Stefan"https://www.zbmath.org/authors/?q=ai:milius.stefan"Moss, Lawrence S."https://www.zbmath.org/authors/?q=ai:moss.lawrence-sLet \(F: Set \to Set\) be a functor. An \(F\)-algebra \((A, \alpha)\) consists of a set \(A\) and a map \(\alpha: F(A)\to A\). A morphism of \(F\)-algebras are called a homomorphism. Instead of Set, we can take an arbitrary category \(\mathcal{A}\) and a functor \(F:\mathcal{A}\to\mathcal{A}\) to work with \(F\)-algebras \(\alpha: F(A)\to A\) and \(F\)-coalgebras \(\alpha: A\to F(A)\).
The initial object \(\mu F\) of the category of \(F\)-algebras is called the initial algebra. A recursion is defined as a unique homomorphism
\(\mu F \to (A, \alpha)\). For example, the functor \(F(X)= X+1= X\cup \{X\}\) has the initial \(F\)-algebra \({\,\mathbb N}\), that is the set of nonnegative integers with the map \({\,\mathbb N}+1\to {\,\mathbb N}\) defined by \(n\mapsto n+1\), for \(n\in {\,\mathbb N}\) and \({\,\mathbb N}\mapsto 0\). For every \(F\)-algebra \((A, \alpha)\) with \(\alpha({\,\mathbb N})=a\), the homomorphism \(f(0)=a\) and \(f(n+1)=\alpha(f(n))\) is the recursion.
This approach leads to the problem for a given algebra to determine whether this algebra is initial. We provide the text of the answer from the paper under review:
``The answer -- again in slogans -- is that initial algebras are the ones with `no junk and no confusion'.''
However, initiality does not always describe recursive definitions. Let, for example, \((X, R)\) be a relation that is well founded in the sense that it does not contain infinite sequences \(\cdots x_2 R x_1 R x_0\). Let \(A\) be an arbitrary set. Let us denote by \(\mathcal{P} A\) the set of all its subsets. Then for each mapping \(\alpha:\mathcal{P} A \to A\) there is a unique mapping \(f: X \to A\) defined on all \(x\in X\) by the recursive definition \(f(x) = \alpha(\{y : yRx\})\). But it is impossible to determine the function \(f\) using initiality.
The purpose of this article is to explore the concepts behind initiality and apply those concepts to situations like recursive definitions for well-defined relationships. The work continues the research undertaken in the articles by \textit{G. Osius} [J. Pure Appl. Algebra 4, 79--119 (1974; Zbl 0282.02027)] and \textit{P. Taylor} [``Towards a unified treatment of induction I: the general recursion theorem, Preprint, \url{www.paultaylor.eu/ordinals/\#towuti}; Practical foundations of mathematics. Cambridge: Cambridge University Press (1999; Zbl 0939.18001)].
Osius first studied the notions of well-founded and recursive coalgebras for the power-set functor on sets (and, moreover, on an elementary topos). Taylor introduced well-founded coalgebras for a general endofunctor. He proved the General Recursion Theorem that all well-founded coalgebras are recursive, for every endofunctor on sets (and on more general categories) preserving inverse images.
Recursive coalgebras were also investigated by \textit{A. Eppendahl} [in: CTCS '99. Conference on category theory and computer science, Edinburgh, GB, September 10--12, 1999. Amsterdam: Elsevier. 8 p. (1999; Zbl 0961.18005)], who called them algebra-initial coalgebras.
\textit{V. Capretta} et al. [Lect. Notes Comput. Sci. 5902, 84--100 (2009; Zbl 1266.68083)] further studied recursive coalgebras, and they
showed how to construct new ones from given ones by using comonads. \textit{J.-B. Jeannin} et al. [Math. Struct. Comput. Sci. 27, No. 7, 1111--1131 (2017; Zbl 1376.68094)] proved the General Recursion Theorem for polynomial functors on the category of many-sorted sets.
In order to formulate the main results of the article, we recall definitions.
A category is well-powered if the subobjects of each of its objects can be indexed by a set. We assume that \(\mathcal{A}\) is a complete and well-powered category and that \(F:\mathcal{A}\to\mathcal{A}\) preserves monomorphisms.
Definition 2.8.
(1) A category \(\mathcal{A}\) has smooth monomorphisms if for every ordinal \(\lambda\) and a diagram \(C: \lambda\to\mathcal{A}\) of monomorphisms, a colimit exists, its colimit cocone is formed by monomorphisms, and for every cone of \(C\) formed by monomorphisms, the factorizing morphism from \(\mathrm{colim\,} C\) is monic.
(2) \(\mathcal{A}\) has universally smooth monomorphisms if \(\mathcal{A}\) also has pullbacks, and for every morphism \(f : X \to\mathrm{colim\,} C\), the functor \(\mathcal{A} /\mathrm{colim\,} C \to\mathcal{A} /X\) forming pullbacks along \(f\) preserves the colimit of \(C\).
Definition 3.2. A coalgebra \(\alpha: A \to FA\) is called recursive if for every algebra \(e: FX\to X\) there exists a unique coalgebra-to-algebra
morphism \(e^{\dagger}: A\to X\), i.e. a unique morphism such that \(e^{\dagger}= e F(e^{\dagger})\alpha\). A coalgebra \((A, \alpha)\) is called parametrically recursive if for every morphism \(e: FX \times A \to X\) there is a unique morphism \(e^{\dagger} : A \to X\) such that \(e^{\dagger}= e (F(e^{\dagger})\times 1_A) (\alpha, 1_A)\).
Definition 4.1. Every coalgebra \(\alpha: A \to FA\) induces an endofunction on \(\mathrm{Sub}(A)\), called the next time operator
\(\bigcirc:\mathrm{Sub}(A) \to\mathrm{Sub}(A)\), \(\bigcirc(s) = \overleftarrow\alpha (Fs)\) for \(s \in\mathrm{Sub}(A)\). Here, the \(\bigcirc s: \bigcirc S\to A\) denotes the side of the pullback built on the morphisms \(\alpha: A\to FA\) and \(Fs: FS\to FA\).
Theorem 5.1 (General Recursion Theorem). Let \(\mathcal{A}\) be a complete and well-powered category with smooth monomorphisms. For \(F:\mathcal{A} \to\mathcal{A}\) preserving monomorphisms, every well-founded coalgebra is parametrically recursive.
The assumptions are considered when the converse statement exists.
Theorem 5.5. Let \(\mathcal{A}\) be a complete and well-powered category with universally smooth monomorphisms, and suppose that \(F : \mathcal{A} \to\mathcal{A}\) preserves inverse images and has a pre-fixed point. Then every recursive coalgebra is well-founded.
Under these assumptions, the paper gives a new equivalent characterization of recursiveness and validity: a coalgebra is recursive if it has a morphism from the coalgebra to the algebra to the original algebra.
Corollary 5.6. Let \(\mathcal{A}\) and \(F\) satisfy the assumptions of Theorem 5.5. Then the following properties of a coalgebra are equivalent:
(1) well-foundedness,
(2) parametric recursiveness,
(3) recursiveness,
(4) existence of a homomorphism into \((\mu F, \iota^{-1})\),
(5) existence of a homomorphism into a well-founded coalgebra.
The other converse of the above implication is due to Taylor using the concept of a subobject classifier (Theorem 5.8). It implies that `recursive' and `well-founded' are equivalent concepts for all set functors preserving inverse images. It is also proved in the paper that a similar result is true for the category of vector spaces over a fixed field (Theorem 5.12).
For the entire collection see [Zbl 1440.68008].
Reviewer: Ahmet A. Khusainov (Komsomolsk-om-Amur)On the computational power of the light: a plan for breaking data encryption standard.https://www.zbmath.org/1455.941912021-03-30T15:24:00+00:00"Salimi Sartakhti, Javad"https://www.zbmath.org/authors/?q=ai:salimi-sartakhti.javad"Jalili, Saeed"https://www.zbmath.org/authors/?q=ai:jalili.saeedSummary: The successful of the light-based solutions for some NP-complete problems, such as Hamiltonian path problem, have demonstrated the power of light-based computing. The capabilities of the light-based computing such as massive parallelism of light, allow it to solve hard computational problems in polynomial time, while the conventional computers require exponential time. In this study we show how the light-based solution can be applied to break the Data Encryption Standard (DES). Under the assumption of having one given (plain-text, cipher-text) pair, our method recovers the DES key in a efficient time. We describe how to implement XOR gates, circular shifts, P-boxes, and S-boxes of DES in a light-based approach. The proposed solution encrypts the given plain-text with all possible keys and afterwards pair (Key; cipher-text) is extracted from them. We demonstrate that under chosen plain-text attack, it is possible to recover the DES key by providing all DES components in a reasonable time.The part-time parliament.https://www.zbmath.org/1455.680332021-03-30T15:24:00+00:00"Lamport, Leslie"https://www.zbmath.org/authors/?q=ai:lamport.lesliePolynomial kernels for hitting forbidden minors under structural parameterizations.https://www.zbmath.org/1455.681432021-03-30T15:24:00+00:00"Jansen, Bart M. P."https://www.zbmath.org/authors/?q=ai:jansen.bart-m-p"Pieterse, Astrid"https://www.zbmath.org/authors/?q=ai:pieterse.astridSummary: We investigate polynomial-time preprocessing for the problem of hitting forbidden minors in a graph, using the framework of kernelization. For a fixed finite set of connected graphs \(\mathcal{F}\), the \(\mathcal{F}\)-\textsc{Deletion} problem is the following: given a graph \(G\) and integer \(k\), is it possible to delete \(k\) vertices from \(G\) to ensure the resulting graph does not contain any graph from \(\mathcal{F}\) as a minor? Earlier work by
\textit{F. V. Fomin} et al. [``Planar \(F\)-deletion: approximation, kernelization and optimal FPT algorithms'', in: Proceedings of the 53rd annual IEEE symposium on foundations of computer science, FOCS'12. Los Alamitos, CA: IEEE Computer Society. 470--479 (2012; \url{doi:10.1109/FOCS.2012.62})]
showed that when \(\mathcal{F}\) contains a planar graph, an instance \((G, k)\) can be reduced in polynomial time to an equivalent one of size \(k^{\mathcal{O}(1)}\). In this work we focus on structural measures of the complexity of an instance, with the aim of giving nontrivial preprocessing guarantees for instances whose solutions are large. Motivated by several impossibility results, we parameterize the \(\mathcal{F}\)-\textsc{Deletion} problem by the size of a vertex modulator whose removal results in a graph of constant treedepth \(\eta\).
We prove that for each set \(\mathcal{F}\) of connected graphs and constant \(\eta\), the \(\mathcal{F}\)-\textsc{Deletion} problem parameterized by the size of a treedepth-\(\eta\) modulator has a polynomial kernel. Our kernelization is fully explicit and does not depend on protrusion reduction or well-quasi-ordering, which are sources of algorithmic non-constructivity in earlier works on \(\mathcal{F}\)-\textsc{Deletion}. Our main technical contribution is to analyze how models of a forbidden minor in a graph \(G\) with modulator \(X\), interact with the various connected components of \(G - X\). Using the language of labeled minors, we analyze the fragments of potential forbidden minor models that can remain after removing an optimal \(\mathcal{F}\)-\textsc{Deletion} solution from a single connected component of \(G - X\). By bounding the number of different types of behavior that can occur by a polynomial in \(| X |\), we obtain a polynomial kernel using a recursive preprocessing strategy. Our results extend earlier work for specific instances of \(\mathcal{F}\)-\textsc{Deletion} such as \textsc{Vertex Cover} and \textsc{Feedback Vertex Set}. It also generalizes earlier preprocessing results for \(\mathcal{F}\)-\textsc{Deletion} parameterized by a vertex cover, which is a treedepth-one modulator.Formal specification and verification.https://www.zbmath.org/1455.680162021-03-30T15:24:00+00:00"Merz, Stephan"https://www.zbmath.org/authors/?q=ai:merz.stephanFrom the introduction: This chapter focuses on the Temporal Logic of Actions (TLA) and the specification language \(\mathrm{TLA}^+\). These are Lamport's contributions to the formal specification and verification of algorithms that have had the greatest impact in the academic community and in industry.
For the entire collection see [Zbl 1434.68029].State machine replication with benign failures.https://www.zbmath.org/1455.680172021-03-30T15:24:00+00:00"van Renesse, Robbert"https://www.zbmath.org/authors/?q=ai:van-renesse.robbertFrom the text: This chapter focuses on the SMR model in the face of so-called benign process failures. ``Benign'' is a misnomer, but it indicates that a process follows its specification until it stops altogether. In particular, a process will not execute steps that are not according to its specification, but a faulty process may stop performing steps that are in its specification.
For the entire collection see [Zbl 1434.68029].The notions of time and global state in a distributed system.https://www.zbmath.org/1455.680112021-03-30T15:24:00+00:00"Antoniadis, Karolos"https://www.zbmath.org/authors/?q=ai:antoniadis.karolos"Guerraoui, Rachid"https://www.zbmath.org/authors/?q=ai:guerraoui.rachidFrom the introduction: \textit{L. Lamport} introduced his notion of logical time in his celebrated paper ``Time, clocks, and the ordering of events in a distributed system'' [Zbl 0378.68027; Zbl 1448.68134]. This paper is mostly known for defining logical time, as well as the concept of causality. However, of equal if not greater importance was the introduction (in the same paper) of a way to implement an arbitrary \textit{state machine} in a distributed setting. We describe the distributed state machine abstraction idea and an algorithm to implement any algorithm in the distributed setting.
Lastly, we describe the very concept of global state and how to retrieve it in a distributed system. This was first introduced by Chandy and Lamport in 1985.
For the entire collection see [Zbl 1434.68029].The computer science of concurrency: the early years.https://www.zbmath.org/1455.680142021-03-30T15:24:00+00:00"Lamport, Leslie"https://www.zbmath.org/authors/?q=ai:lamport.leslieReprint of the author's A. M. Turing Award Lecture originally published in [Commun. ACM 58, No. 6, 71--76 (2015; \url{doi:10.1145/2771951})].
For the entire collection see [Zbl 1434.68029].Introduction.https://www.zbmath.org/1455.680152021-03-30T15:24:00+00:00"Malkhi, Dahlia"https://www.zbmath.org/authors/?q=ai:malkhi.dahlia"Keidar, Idit"https://www.zbmath.org/authors/?q=ai:keidar.iditFrom the text: This book begins with an article covering Lamport's A. M. Turing Award Lecture, which he gave at the PODC conference in 2014. The article was published in [Commun. ACM 58, No. 6, 71--76 (2015; \url{doi:10.1145/2771951})].
This introduction is followed by two parts. Part I includes technical chapters centered around five key topics addressed in Lamport's work.
This book would not be complete without a glimpse onto the works themselves. A small selection of the original papers introducing the key notions discussed in the contributed papers is given in Part II.
For the entire collection see [Zbl 1434.68029].Embeddings of Schatten norms with applications to data streams.https://www.zbmath.org/1455.460252021-03-30T15:24:00+00:00"Li, Yi"https://www.zbmath.org/authors/?q=ai:li.yi.2|li.yi.3|li.yi.4|li.yi.5|li.yi|li.yi.1"Woodruff, David P."https://www.zbmath.org/authors/?q=ai:woodruff.david-pSummary: Given an \(n\times d\) matrix \(A\), its Schatten-\(p\) norm, \(p\ge 1\), is defined as \[\|A\|_p=\left(\sum_{i=1}^{\operatorname{rank}(A)}\sigma_i(A)^p \right)^{1/p},\] where \(\sigma_i(A)\) is the \(i\)-th largest singular value of \(A\). These norms have been studied in functional analysis in the context of non-commutative \(\ell_p\)-spaces, and recently in data stream and linear sketching models of computation. Basic questions on the relations between these norms, such as their embeddability, are still open. Specifically, given a set of matrices \(A_1,\dots,A^{\operatorname{poly}(nd)}\in\mathbb{R}^{n\times d}\), suppose we want to construct a linear map \(L\) such that \(L(A^i)\in\mathbb{R}^{n'\times d'}\) for each \(i\), where \(n'\le n\) and \(d'\le d\), and further, \(\|A^i\|_p\le\|L(A^i)\|_q\le D_{p,q}\|A_i\|_p\) for a given approximation factor \(D_{p,q}\) and real number \(q\ge 1\). Then how large do \(n'\) and \(d'\) need to be as a function of \(D_{p,q}\)?
We nearly resolve this question for every \(p,q\ge 1\), for the case where \(L(A^i)\) can be expressed as \(R\cdot A^i\cdot S\), where \(R\) and \(S\) are arbitrary matrices that are allowed to depend on \(A^1,\dots,A^t\), that is, \(L(A^i)\) can be implemented by left and right matrix multiplication. Namely, for every \(p,q\ge 1\), we provide nearly matching upper and lower bounds on the size of \(n'\) and \(d'\) as a function of \(D_{p,q}\). Importantly, our upper bounds are oblivious, meaning that \(R\) and \(S\) do not depend on the \(A_i\), while our lower bounds hold even if \(R\) and \(S\) depend on the \(A^i\). As an application of our upper bounds, we answer a recent open question of \textit{J. Błasiok} et al. [in: Proceedings of the 49th annual ACM SIGACT symposium on theory of computing, STOC '17, Montreal, QC, Canada, June 19--23, 2017. New York, NY: Association for Computing Machinery (ACM). 716--729 (2017; Zbl 1369.68205)] about space-approximation trade-offs for the Schatten 1-norm, showing in a data stream it is possible to estimate the Schatten 1-norm up to a factor of \(D\ge 1\) using \(\widehat O(\min(n,d)^2/D^4)\) space.
For the entire collection see [Zbl 1373.68018].Maximum reachability preserved graph cut.https://www.zbmath.org/1455.681452021-03-30T15:24:00+00:00"Miao, Dongjing"https://www.zbmath.org/authors/?q=ai:miao.dongjing"Li, Jianzhong"https://www.zbmath.org/authors/?q=ai:li.jianzhong"Cai, Zhipeng"https://www.zbmath.org/authors/?q=ai:cai.zhipengSummary: A class of reachability reduction problems were raised in the area of computer network security and software engineering. This paper studies such a reachability reduction problem on a vertex labeled graph. The reachability reduction here is modeled as maximum reachability preserved cut which is a variant of minimum multiway cut with a new objective function. Finding a maximum reachability preserved cut is to disconnect some labels specified in advance by edge deletion while preserving other reachable labels. It gives a way to model a large family of network problems based on graph model. We provide a comprehensive complexity analysis of this problem under different input settings. A landscape of the hardness hierarchy of this problem is shown in this paper, in which polynomial tractable and intractable cases are identified.Metamath Zero: designing a theorem prover prover.https://www.zbmath.org/1455.682432021-03-30T15:24:00+00:00"Carneiro, Mario"https://www.zbmath.org/authors/?q=ai:carneiro.mario-d|carneiro.mario-mSummary: As the usage of theorem prover technology expands, so too does the reliance on correctness of the tools. Metamath Zero is a verification system that aims for simplicity of logic and implementation, without compromising on efficiency of verification. It is formally specified in its own language, and supports a number of translations to and from other proof languages. This paper describes the abstract logic of Metamath Zero, essentially a multi-sorted first order logic, as well as the binary proof format and the way in which it can ensure essentially linear time verification while still being concise and efficient at scale. Metamath Zero currently holds the record for fastest verification of the set.mm Metamath library of proofs in ZFC (including 71 of Wiedijk's 100 formalization targets), at less than 200 ms. Ultimately, we intend to use it to verify the correctness of the implementation of the verifier down to binary executable, so it can be used as a root of trust for more complex proof systems.
For the entire collection see [Zbl 1452.68005].Radio aggregation scheduling.https://www.zbmath.org/1455.681382021-03-30T15:24:00+00:00"Gandhi, Rajiv"https://www.zbmath.org/authors/?q=ai:gandhi.rajiv-b"Halldórsson, Magnús M."https://www.zbmath.org/authors/?q=ai:halldorsson.magnus-m"Konrad, Christian"https://www.zbmath.org/authors/?q=ai:konrad.christian"Kortsarz, Guy"https://www.zbmath.org/authors/?q=ai:kortsarz.guy"Oh, Hoon"https://www.zbmath.org/authors/?q=ai:oh.hoonSummary: We consider the aggregation problem in radio networks: find a spanning tree in a given graph and a conflict-free schedule of the edges so as to minimize the latency of the computation. While a large body of literature exists on this and related problems, we give the first approximation results in graphs that are not induced by unit ranges in the plane. We give a polynomial-time \(\widetilde{\text{O}}(\sqrt{dn})\)-approximation algorithm, where \(d\) is the average degree and \(n\) the number of vertices in the graph, and show that the problem is \(\Omega(n^{1 - \epsilon})\)-hard (and \(\Omega((d n)^{1 / 2 - \epsilon})\)-hard) to approximate even on bipartite graphs, for any \(\epsilon > 0\), rendering our algorithm essentially optimal. We also obtain a \(O(\log n)\)-approximation in interval graphs.Algorithm and hardness results on liar's dominating set and \({k}\)-tuple dominating set.https://www.zbmath.org/1455.681332021-03-30T15:24:00+00:00"Banerjee, Sandip"https://www.zbmath.org/authors/?q=ai:banerjee.sandip"Bhore, Sujoy"https://www.zbmath.org/authors/?q=ai:bhore.sujoy-kumarSummary: Given a graph \(G=(V,E)\), the Dominating Set problem asks for a minimum subset of vertices \(D\subseteq V\) such that every vertex \(u\in V\setminus D\) is adjacent to at least one vertex \(v\in D\). That is, the set \(D\) satisfies the condition that \(|N[v]\cap D|\ge 1\) for each \(v\in V\), where \(N[v]\) is the closed neighborhood of \(v\). In this paper, we study two variants of the classical Dominating Set problem: \({k}\)-Tuple Dominating Set \((k\)-DS) problem and Liar's Dominating Set (LDS) problem, and obtain several algorithmic and hardness results. On the algorithmic side, we present a constant factor \((\frac{11}{2})\)-approximation algorithm for the Liar's Dominating Set problem on unit disk graphs. Then, we design a polynomial time approximation scheme (PTAS) for the \(k\)-Tuple Dominating Set problem on unit disk graphs. On the hardness side, we show a \(\varOmega(n^2)\) bits lower bound for the space complexity of any (randomized) streaming algorithm for Liar's Dominating Set problem as well as for the \(k\)-Tuple Dominating Set problem. Furthermore, we prove that the Liar's Dominating Set problem on bipartite graphs is W[2]-hard.
For the entire collection see [Zbl 1416.68006].Testing equivalences of time Petri nets.https://www.zbmath.org/1455.681182021-03-30T15:24:00+00:00"Bozhenkova, E. N."https://www.zbmath.org/authors/?q=ai:bozhenkova.elena-n"Virbitskaite, I. B."https://www.zbmath.org/authors/?q=ai:virbitskaite.irina-bSummary: In the paper, we study a family of testing equivalences in interleaving, partial-order semantics, and combined semantics in the context of safe time Petri nets (elementary net systems whose transitions are labeled with time firing intervals, can fire only if their lower time bounds are attained, and are forced to fire when their upper time bounds are reached). For this purpose, the following three representations of behavior of safe time Petri nets are developed: sequences of firings of net transitions, which represent interleaving semantics; time causal processes, from which partial orders are derived; and time causal tree, whose nodes are sequences of transition firings and arcs are labeled by information about partial orders. We establish relationships between these equivalences and show that semantics of time causal processes and time causal trees coincide.Efficient fair multiparty protocols using blockchain and trusted hardware.https://www.zbmath.org/1455.942172021-03-30T15:24:00+00:00"Paul, Souradyuti"https://www.zbmath.org/authors/?q=ai:paul.souradyuti"Shrivastava, Ananya"https://www.zbmath.org/authors/?q=ai:shrivastava.ananyaSummary: \textit{A. R. Choudhuri} et al. [``Fairness in an unfair world: fair multiparty computation from public bulletin boards'', in: Proceedings of the 2017 ACM SIGSAC conference on computer and communications security, CCS '17, Dallas, TX, USA, October 30--November 03, 2017. New York, NY: Association for Computing Machinery (ACM). 719--728 (2017; \url{doi:10.1145/3133956.3134092})] designed two fair public-ledger-based multi-party protocols (in the malicious model with dishonest majority) for computing an arbitrary function \(f\). One of their protocols is based on a trusted hardware enclave \(\mathcal{G} \) (which can be implemented using Intel SGX-hardware) and a public ledger (which can be implemented using a blockchain platform, such as Ethereum). Subsequently, in NDSS'19, a stateless version of the protocol was published. This is the first time, (a certain definition of) fairness -- that guarantees either all parties learn the final output or nobody does -- is achieved without any monetary or computational penalties. However, these protocols are fair, if the underlying core MPC component guarantees both privacy and correctness. While privacy is easy to achieve (using a secret sharing scheme), correctness requires expensive operations (such as ZK proofs and commitment schemes). We improve on this work in three different directions: attack, design and performance.
Our first major contribution is building practical attacks that demonstrate: if correctness is not satisfied then the fairness property of the aforementioned protocols collapse. Next, we design two new protocols -- stateful and stateless -- based on public ledger and trusted hardware that are: resistant against the aforementioned attacks, and made several orders of magnitude more efficient (related to both time and memory) than the existing ones by eliminating ZK proofs and commitment schemes in the design.
Last but not the least, we implemented the core MPC part of our protocols using the SPDZ-2 framework to demonstrate the feasibility of its practical implementation.
For the entire collection see [Zbl 1422.94005].On the complexity of the stability problem of binary freezing totalistic cellular automata.https://www.zbmath.org/1455.681082021-03-30T15:24:00+00:00"Goles, Eric"https://www.zbmath.org/authors/?q=ai:goles-chacc.eric"Maldonado, Diego"https://www.zbmath.org/authors/?q=ai:maldonado.diego"Montealegre, Pedro"https://www.zbmath.org/authors/?q=ai:montealegre.pedro"Ollinger, Nicolas"https://www.zbmath.org/authors/?q=ai:ollinger.nicolasSummary: In this paper we study the family of two-state Totalistic Freezing Cellular Automata (TFCA) defined over the triangular and square grids with von Neumann neighborhoods. We say that a Cellular Automaton is Freezing and Totalistic if the active cells remain unchanged, and the new value of an inactive cell depends only on the sum of its active neighbors.
We classify all the Cellular Automata in the class of TFCA, grouping them in five different classes: the Trivial rules, Turing Universal rules, Algebraic rules, Topological rules and Fractal Growing rules. At the same time, we study in this family the \textsc{Stability} problem, consisting in deciding whether an inactive cell becomes active, given an initial configuration. We exploit the properties of the automata in each group to show that:
\begin{itemize}
\item For Algebraic and Topological Rules the \textsc{Stability} problem is in \textbf{NC}.
\item For Turing Universal rules the \textsc{Stability} problem is \textbf{P}-Complete.
\end{itemize}Delegating quantum computation in the quantum random oracle model.https://www.zbmath.org/1455.810162021-03-30T15:24:00+00:00"Zhang, Jiayu"https://www.zbmath.org/authors/?q=ai:zhang.jiayuSummary: A delegation scheme allows a computationally weak client to use a server's resources to help it evaluate a complex circuit without leaking any information about the input (other than its length) to the server. In this paper, we consider delegation schemes for quantum circuits, where we try to minimize the quantum operations needed by the client. We construct a new scheme for delegating a large circuit family, which we call ``C+P circuits''. ``C+P'' circuits are the circuits composed of Toffoli gates and diagonal gates. Our scheme is non-interactive, requires small amount of quantum computation from the client (proportional to input length but independent of the circuit size), and can be proved secure in the quantum random oracle model, without relying on additional assumptions, such as the existence of fully homomorphic encryption. In practice the random oracle can be replaced by an appropriate hash function or block cipher, for example, SHA-3, AES.
This protocol allows a client to delegate the most expensive part of some quantum algorithms, for example, Shor's algorithm. The previous protocols that are powerful enough to delegate Shor's algorithm require either many client side quantum operations or the existence of FHE. The protocol requires asymptotically fewer quantum gates on the client side compared to running Shor's algorithm locally.
To hide the inputs, our scheme uses an encoding that maps one input qubit to multiple qubits. We then provide a novel generalization of classical garbled circuits (``reversible garbled circuits'') to allow the computation of Toffoli circuits on this encoding. We also give a technique that can support the computation of phase gates on this encoding.
To prove the security of this protocol, we study key dependent message (KDM) security in the quantum random oracle model. KDM security was not previously studied in quantum settings.
For the entire collection see [Zbl 1428.94014].A periodic isoperimetric problem related to the unique games conjecture.https://www.zbmath.org/1455.600292021-03-30T15:24:00+00:00"Heilman, Steven"https://www.zbmath.org/authors/?q=ai:heilman.steven-mSummary: We prove the endpoint case of a conjecture of \textit{S. Khot} and \textit{D. Moshkovitz} [in: Proceedings of the 48th annual ACM SIGACT symposium on theory of computing, STOC '16, Cambridge, MA, USA, June 19--21, 2016. New York, NY: Association for Computing Machinery (ACM). 63--76 (2016; Zbl 1373.68240)] related to the unique games conjecture, less a small error. Let \(n\geq 2\). Suppose a subset \(\Omega\) of \(n\)-dimensional Euclidean space \(\mathbb{R}^n\) satisfies \(-\Omega=\Omega^c\) and \(\Omega+v=\Omega^c\) (up to measure zero sets) for every standard basis vector \(v\in\mathbb{R}^n\). For any \(x=(x_1,\dots,x_n)\in\mathbb{R}^n\) and for any \(q\geq 1\), let \(||x||^q_q=|x_1|^q+\cdots+|x_n|^q\) and let \(\gamma_n(x)=(2\pi)^{-n/2}e^{-||x||^2_2/2}\). For any \(x\in\partial\Omega\), let \(N(x)\) denote the exterior normal vector at \(x\) such that \(\Vert N(x)\Vert_2=1\). Let \(B=\{x\in\mathbb{R}^n:\sin(\pi(x_1+\cdots+x_n))\geq 0\}\). Our main result shows that \(B\) has the smallest Gaussian surface area among all such subsets \(\Omega\), less a small error: \(\int_{\partial\Omega}\gamma_n(x)\mathrm{d}x\geq (1-6\times 10^{-9})\int_{\partial B}\gamma_n(x)\mathrm{d}x+\int_{\partial\Omega}\left(1-\frac{||N(x)||_1}{\sqrt n}\right)\gamma_n(x)\mathrm{d}x\). In particular, \(\int_{\partial\Omega}\gamma_n(x)\mathrm{d}x\geq(1-6\times 10^{-9})\int_{\partial B}\gamma_n(x)\mathrm{d}x\). Standard arguments extend these results to a corresponding weak inequality for noise stability. Removing the factor \(6\times 10^{-9}\) would prove the endpoint case of the Khot-Moshkovitz conjecture. Lastly, we prove a Euclidean analogue of the Khot and Moshkovitz conjecture. The full conjecture of Khot and Moshkovitz provides strong evidence for the truth of the unique games conjecture, a central conjecture in theoretical computer science that is closely related to the P versus NP problem. So, our results also provide evidence for the truth of the unique games conjecture. Nevertheless, this paper does not prove any case of the unique games conjecture.Preface.https://www.zbmath.org/1455.680222021-03-30T15:24:00+00:00"Dennunzio, Alberto (ed.)"https://www.zbmath.org/authors/?q=ai:dennunzio.alberto"Formenti, Enrico (ed.)"https://www.zbmath.org/authors/?q=ai:formenti.enricoFrom the text: The 23rd Annual International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA 2017) was held in Milano (Italy) in the period 7--9 June 2017 at the University of Milano-Bicocca.
The papers presented at the conference were selected following a rigorous peer review process in which all papers had two reviews. After the conference, authors were invited to submit a substantially extended and improved version of their papers. A further review round followed and all papers got two new reviews. Finally, ten of them were selected to appear in this special issue.Efficient information-theoretic secure multiparty computation over \(\mathbb{Z}/p^k\mathbb{Z}\) via Galois rings.https://www.zbmath.org/1455.942032021-03-30T15:24:00+00:00"Abspoel, Mark"https://www.zbmath.org/authors/?q=ai:abspoel.mark"Cramer, Ronald"https://www.zbmath.org/authors/?q=ai:cramer.ronald"Damgård, Ivan"https://www.zbmath.org/authors/?q=ai:damgard.ivan-bjerre"Escudero, Daniel"https://www.zbmath.org/authors/?q=ai:escudero.daniel-e"Yuan, Chen"https://www.zbmath.org/authors/?q=ai:yuan.chenSummary: \textit{R. Cramer} et al. [Lect. Notes Comput. Sci. 2656, 596--613 (2003; Zbl 1038.94554)] introduced a secret-sharing based protocol called \(\mathrm{SPD}\mathbb{Z}_{2^k}\) that allows for secure multiparty computation (MPC) in the dishonest majority setting over the ring of integers modulo \(2^k\), thus solving a long-standing open question in MPC about secure computation over rings in this setting. In this paper we study this problem in the information-theoretic scenario. More specifically, we ask the following question: Can we obtain information-theoretic MPC protocols that work over rings with comparable efficiency to corresponding protocols over fields? We answer this question in the affirmative by presenting an efficient protocol for robust secure multiparty computation over \(\mathbb{Z}/p^k\mathbb{Z} \) (for any prime \(p\) and positive integer \(k)\) that is perfectly secure against active adversaries corrupting a fraction of at most 1/3 players, and a robust protocol that is statistically secure against an active adversary corrupting a fraction of at most 1/2 players.
For the entire collection see [Zbl 1428.94013].Complexity of the multi-service center problem.https://www.zbmath.org/1455.681422021-03-30T15:24:00+00:00"Ito, Takehiro"https://www.zbmath.org/authors/?q=ai:ito.takehiro"Kakimura, Naonori"https://www.zbmath.org/authors/?q=ai:kakimura.naonori"Kobayashi, Yusuke"https://www.zbmath.org/authors/?q=ai:kobayashi.yusukeSummary: The multi-service center problem is a variant of facility location problems. In the problem, we consider locating \(p\) facilities on a graph, each of which provides distinct service required by all vertices. Each vertex incurs the cost determined by the sum of the weighted distances to the \(p\) facilities. The aim of the problem is to minimize the maximum cost among all vertices. This problem is known to be NP-hard for general graphs, while it is solvable in polynomial time when \(p\) is a fixed constant. In this paper, we give sharp analyses for the complexity of the problem from the viewpoint of graph classes and weights on vertices. We first propose a polynomial-time algorithm for trees when \(p\) is a part of input. In contrast, we prove that the problem becomes strongly NP-hard even for cycles. We also show that when vertices are allowed to have negative weights, the problem becomes NP-hard for paths of only three vertices and strongly NP-hard for stars.
For the entire collection see [Zbl 1376.68013].QANIZK for adversary-dependent languages and their applications.https://www.zbmath.org/1455.941642021-03-30T15:24:00+00:00"Han, Shuai"https://www.zbmath.org/authors/?q=ai:han.shuai"Liu, Shengli"https://www.zbmath.org/authors/?q=ai:liu.shengli"Lyu, Lin"https://www.zbmath.org/authors/?q=ai:lyu.linSummary: Quasi-Adaptive Non-Interactive Zero-Knowledge (QANIZK) proofs make possible efficient NIZK with short proofs by allowing the common reference string to depend on the language. The strongest notion of (computational) soundness for QANIZK is Unbounded Simulation-Soundness (USS). For USS, however, the language is completely beyond the adversary's control.
In this paper, we introduce a stronger notion of USS for QANIZK, called USS for Adversary-Dependent Languages (USS-ADL), by allowing the adversary to adaptively develop the language. We present a generic construction of efficient USS-ADL-QANIZK for diverse vector spaces (DVS) over graded rings, of which linear subspaces over bilinear groups are specific instantiations.
i) Our generic construction provides the first USS-QANIZK for DVS over graded rings. This complements Abdalla et al.'s work [\textit{M. Abdalla} et al., Lect. Notes Comput. Sci. 9057, 69--100 (2015; Zbl 1326.94065)] of QANIZK with one-time simulation-soundness.
ii) As for applications, USS-ADL-QANIZK leads to modular constructions of digital signature and linearly homomorphic (structure-preserving) signature schemes with black-box security reductions.
The instantiations cover the efficient USS-QANIZK for linear subspaces over bilinear groups proposed by \textit{E. Kiltz} and \textit{H. Wee} [ibid. 9057, 101--128 (2015; Zbl 1326.94103)], a variant of the efficient structure-preserving signature proposed by \textit{E. Kiltz} et al. [ibid. 9216, 275--295 (2015; Zbl 1352.94043)] and the efficient linearly homomorphic structure-preserving signature proposed by E. Kiltz and H. Wee [loc. cit.]. Our USS-ADL-QANIZK provides a new perspective on their constructions and security proofs in a unified way.On fully secure MPC with solitary output.https://www.zbmath.org/1455.941632021-03-30T15:24:00+00:00"Halevi, Shai"https://www.zbmath.org/authors/?q=ai:halevi.shai"Ishai, Yuval"https://www.zbmath.org/authors/?q=ai:ishai.yuval"Kushilevitz, Eyal"https://www.zbmath.org/authors/?q=ai:kushilevitz.eyal"Makriyannis, Nikolaos"https://www.zbmath.org/authors/?q=ai:makriyannis.nikolaos"Rabin, Tal"https://www.zbmath.org/authors/?q=ai:rabin.talSummary: We study the possibility of achieving full security, with guaranteed output delivery, for secure multiparty computation of functionalities where only one party receives output, to which we refer as solitary functionalities. In the standard setting where all parties receive an output, full security typically requires an honest majority; otherwise even just achieving fairness is impossible. However, for solitary functionalities, fairness is clearly not an issue. This raises the following question: is full security with no honest majority possible for all solitary functionalities?
We give a negative answer to this question, by showing the existence of solitary functionalities that cannot be computed with full security. While such a result cannot be proved using fairness-based arguments, our proof builds on the classical proof technique of \textit{R. Cleve} [``Limits on the security of coin flips when half the processors are fault'', in: Proceedings of the 18th Annual ACM Symposium on Theory of Computing STOC'86, Berkeley, California, USA, May 1986. New York, NY: Association for Computing Machinery (ACM). 364--369 (1986)] for ruling out fair coin-tossing and extends it in a nontrivial way.
On the positive side, we show that full security against any number of malicious parties is achievable for many natural and useful solitary functionalities, including ones for which the multi-output version cannot be realized with full security.
For the entire collection see [Zbl 1428.94013].Topics in theoretical computer science. Third IFIP WG 1.8 international conference, TTCS 2020, Tehran, Iran, July 1--2, 2020. Proceedings.https://www.zbmath.org/1455.680202021-03-30T15:24:00+00:00"Barbosa, Luís Soares (ed.)"https://www.zbmath.org/authors/?q=ai:barbosa.luis-soares"Abam, Mohammad Ali (ed.)"https://www.zbmath.org/authors/?q=ai:abam.mohammad-aliThe articles of this volume will be reviewed individually. For the preceding conference see [Zbl 1373.68021].
Indexed articles:
\textit{Mohagheghi, Mohammadsadegh; Chaboki, Behrang}, Dirac-based reduction techniques for quantitative analysis of discrete-time Markov models, 1-16 [Zbl 07316479]
\textit{Sabahi-Kaviani, Zeynab; Ghassemi, Fatemeh; Alimadadi, Zahra}, Combining machine and automata learning for network traffic classification, 17-31 [Zbl 07316480]
\textit{Harutyunyan, Ararat; Khosravian Ghadikolaei, Mehdi; Melissinos, Nikolaos; Monnot, Jérôme; Pagourtzis, Aris}, On the complexity of the upper \(r\)-tolerant edge cover problem, 32-47 [Zbl 07316481]
\textit{Emadi, Mona; Tanha, Jafar}, Margin-based semi-supervised learning using Apollonius circle, 48-60 [Zbl 07316482]
\textit{Boomari, Hossein; Farokhi, Soheila}, Computing boundary cycle of a pseudo-triangle polygon from its visibility graph, 61-71 [Zbl 07316483]
\textit{Mirjalali, Kian; Zarrabi-Zadeh, Hamid}, Improved algorithms for distributed balanced clustering, 72-84 [Zbl 07316484]
\textit{Tavassoli, Shaghayegh; Khosravi, Ramtin; Khamespanah, Ehsan}, Finite interval-time transition system for real-time actors, 85-100 [Zbl 07316485]
\textit{Davoodi, Mansoor; Rouhani, Arman; Sanisales, Maryam}, Path planning with objectives minimum length and maximum clearance, 101-115 [Zbl 07316486]From FE combiners to secure MPC and back.https://www.zbmath.org/1455.941082021-03-30T15:24:00+00:00"Ananth, Prabhanjan"https://www.zbmath.org/authors/?q=ai:ananth.prabhanjan-vijendra"Badrinarayanan, Saikrishna"https://www.zbmath.org/authors/?q=ai:badrinarayanan.saikrishna"Jain, Aayush"https://www.zbmath.org/authors/?q=ai:jain.aayush"Manohar, Nathan"https://www.zbmath.org/authors/?q=ai:manohar.nathan"Sahai, Amit"https://www.zbmath.org/authors/?q=ai:sahai.amitSummary: Cryptographic combiners allow one to combine many candidates for a cryptographic primitive, possibly based on different computational assumptions, into another candidate with the guarantee that the resulting candidate is secure as long as at least one of the original candidates is secure. While the original motivation of cryptographic combiners was to reduce trust on existing candidates, in this work, we study a rather surprising implication of combiners to constructing secure multiparty computation protocols. Specifically, we initiate the study of functional encryption combiners and show its connection to secure multiparty computation.
Functional encryption (FE) has incredible applications towards computing on encrypted data. However, constructing the most general form of this primitive has remained elusive. Although some candidate constructions exist, they rely on nonstandard assumptions, and thus, their security has been questioned. An FE combiner attempts to make use of these candidates while minimizing the trust placed on any individual FE candidate. Informally, an FE combiner takes in a set of FE candidates and outputs a secure FE scheme if at least one of the candidates is secure.
Another fundamental area in cryptography is secure multi-party computation (MPC), which has been extensively studied for several decades. In this work, we initiate a formal study of the relationship between functional encryption (FE) combiners and secure multi-party computation (MPC). In particular, we show implications in both directions between these primitives. As a consequence of these implications, we obtain the following main results.
i) A two-round semi-honest MPC protocol in the plain model secure against up to \(n-1\) corruptions with communication complexity proportional only to the depth of the circuit being computed assuming Learning with Errors (LWE). Prior two round protocols based on standard assumptions that achieved this communication complexity required trust assumptions, namely, a common reference string.
ii) A functional encryption combiner based on pseudorandom generators (PRGs) in \(\mathsf{NC}^1\). This is a weak assumption as such PRGs are implied by many concrete intractability problems commonly used in cryptography, such as ones related to factoring, discrete logarithm, and lattice problems [\textit{B. Applebaum} et al., Comput. Complexity 15, No. 2, 115--162 (2006; Zbl 1143.94009)].
Previous constructions of FE combiners, implicit in [\textit{P. Ananth} et al., Lect. Notes Comput. Sci. 10210, 91--121 (2017; Zbl 1410.94039)], were known only from LWE. Using this result, we build a universal construction of functional encryption: an explicit construction of functional encryption
For the entire collection see [Zbl 1428.94013].Actor-based model checking for software-defined networks.https://www.zbmath.org/1455.681012021-03-30T15:24:00+00:00"Albert, Elvira"https://www.zbmath.org/authors/?q=ai:albert.elvira"Gómez-Zamalloa, Miguel"https://www.zbmath.org/authors/?q=ai:gomez-zamalloa.miguel"Isabel, Miguel"https://www.zbmath.org/authors/?q=ai:isabel.miguel"Rubio, Albert"https://www.zbmath.org/authors/?q=ai:rubio.albert"Sammartino, Matteo"https://www.zbmath.org/authors/?q=ai:sammartino.matteo"Silva, Alexandra"https://www.zbmath.org/authors/?q=ai:silva.alexandraSummary: Software-Defined Networking (SDN) is a networking paradigm that has become increasingly popular in the last decade. The unprecedented control over the global behaviour of the network it provides opens a range of new opportunities for formal methods and much work has appeared in the last few years on providing bridges between SDN and verification. This article advances this research line and provides a link between SDN and traditional work on formal methods for verification of concurrent and distributed software -- actor-based modelling. We show how SDN programs can be seamlessly modelled using \textit{actors}, and thus existing advanced model checking techniques developed for actors can be directly applied to verify a range of properties of SDNs, including consistency of flow tables, violation of safety policies, and forwarding loops. Our model checker for SDNs is available through an online web interface, that also provides the SDN actor-models for a number of well-known SDN benchmarks.A linear-space data structure for range-LCP queries in poly-logarithmic time.https://www.zbmath.org/1455.680452021-03-30T15:24:00+00:00"Abedin, Paniz"https://www.zbmath.org/authors/?q=ai:abedin.paniz"Ganguly, Arnab"https://www.zbmath.org/authors/?q=ai:ganguly.arnab"Hon, Wing-Kai"https://www.zbmath.org/authors/?q=ai:hon.wing-kai"Matsuda, Kotaro"https://www.zbmath.org/authors/?q=ai:matsuda.kotaro"Nekrich, Yakov"https://www.zbmath.org/authors/?q=ai:nekrich.yakov"Sadakane, Kunihiko"https://www.zbmath.org/authors/?q=ai:sadakane.kunihiko"Shah, Rahul"https://www.zbmath.org/authors/?q=ai:shah.rahul"Thankachan, Sharma V."https://www.zbmath.org/authors/?q=ai:thankachan.sharma-vIn this paper, the authors study the range-LCP problem (or rlcp), which asks,
given a text \(T\) of length \(n\), for the Longest Common Prefix (LCP) of suffixes of \(T\)
(namely \(T[i,n]\) and \(T[j,n]\)) among all \(\alpha\leq i\neq j\leq \beta\),
where \(\alpha\) and \(\beta\) are integers (satisfying \(1\leq
\alpha<\beta\leq n\)) given as input.
The main question raised and positively answered by the authors is
whether it is possible to answer rlcp in polylogarithmic time, using a
linear-space data structure. More precisely, the data structure used
takes \(O(n)\) space and is constructed in \(O(n\log n)\) time. Using the
above-mentioned data structure, rlcp can then be answered in
\(O(\log^{1+\varepsilon} n)\) time, for any \(\varepsilon>0\).
Papers dealing with string algorithms are not always easy to follow
for the non-specialist, as this topic has a long and rich history, uses many
notations, and (as is the case here) aims at improving time/space
complexities and thus provides detailed and thorough analyses.
This paper is no exception. One has to be familiar with string
algorithms (and in particular with suffix arrays,
suffix trees and of course LCP issues) to understand the paper's
contents.
Reviewer: Guillaume Fertin (Nantes)Covering and packing of rectilinear subdivision.https://www.zbmath.org/1455.682312021-03-30T15:24:00+00:00"Jana, Satyabrata"https://www.zbmath.org/authors/?q=ai:jana.satyabrata"Pandit, Supantha"https://www.zbmath.org/authors/?q=ai:pandit.supanthaSummary: We study a class of geometric covering and packing problems for bounded closed regions on the plane. We are given a set of axis-parallel line segments that induce a planar subdivision with bounded (rectilinear) faces. We are interested in the following problems.
\begin{itemize}
\item Stab all closed bounded faces of the planar subdivision by selecting a minimum number of points in the plane.
\item Select a maximum size collection of pairwise non-intersecting closed bounded faces of the planar subdivision.
\item Select a minimum size collection of bounded faces of the planar subdivision such that every other face of the subdivision that is not selected has a non-empty intersection (i.e., sharing an edge or a vertex) with some selected face.
\end{itemize}
We show that these problems are \textsf{NP}-hard. We even prove that these problems are \textsf{NP}-hard when we concentrate only on the rectangular faces of the subdivision. Further, we provide constant factor approximation algorithms for the \textsc{Stabbing-Subdivision} problem.Learning dynamics with synchronous, asynchronous and general semantics.https://www.zbmath.org/1455.681792021-03-30T15:24:00+00:00"Ribeiro, Tony"https://www.zbmath.org/authors/?q=ai:ribeiro.tony"Folschette, Maxime"https://www.zbmath.org/authors/?q=ai:folschette.maxime"Magnin, Morgan"https://www.zbmath.org/authors/?q=ai:magnin.morgan"Roux, Olivier"https://www.zbmath.org/authors/?q=ai:roux.olivier-h|roux.olivier-f"Inoue, Katsumi"https://www.zbmath.org/authors/?q=ai:inoue.katsumiSummary: Learning from interpretation transition (LFIT) automatically constructs a model of the dynamics of a system from the observation of its state transitions. So far, the systems that LFIT handles are restricted to synchronous deterministic dynamics, i.e., all variables update their values at the same time and, for each state of the system, there is only one possible next state. However, other dynamics exist in the field of logical modeling, in particular the asynchronous semantics which is widely used to model biological systems. In this paper, we focus on a method that learns the dynamics of the system independently of its semantics. For this purpose, we propose a modeling of multi-valued systems as logic programs in which a rule represents what can occur rather than what will occur. This modeling allows us to represent non-determinism and to propose an extension of LFIT in the form of a semantics free algorithm to learn from discrete multi-valued transitions, regardless of their update schemes. We show through theoretical results that synchronous, asynchronous and general semantics are all captured by this method. Practical evaluation is performed on randomly generated systems and benchmarks from biological literature to study the scalability of this new algorithm regarding the three aforementioned semantics.
For the entire collection see [Zbl 1453.68019].Link crossing number is NP-hard.https://www.zbmath.org/1455.570102021-03-30T15:24:00+00:00"de Mesmay, Arnaud"https://www.zbmath.org/authors/?q=ai:de-mesmay.arnaud"Schaefer, Marcus"https://www.zbmath.org/authors/?q=ai:schafer.marcus"Sedgwick, Eric"https://www.zbmath.org/authors/?q=ai:sedgwick.ericThe main result of the paper shows that given a link diagram \(L\) and a positive integer \(k\), determining whether \(c(L) \leq k\) is \textbf{NP}-hard, where \(c(L)\) is the smallest number of crossings in a link diagram representing a link isotopic to that of \(L\).
Note that in the above theorem, \(k\) can vary. The authors then show that the theorem remains valid if the word ``isotopic'' in the above statement is replaced by any of the following notions:
\newline
-- link-concordant
-- link-homotopic: Two links \(L\) and \(L'\) are link-homotopic if there exists a homotopy between \(L\) and \(L'\) during which each component of \(L\) is allowed to cross itself but such that no two distinct components are allowed to intersect.
-- linking-number equivalent: Two links \(L\) and \(L'\) are linking-number equivalent if there is a bijection between the components of \(L\) and \(L'\) so that the linking number between two components in \(L\) is the same as the linking number between the corresponding components of \(L'\).
-- parity-linking-number equivalent: Two links \(L\) and \(L'\) are parity-linking-number equivalent if there is a bijection between the components of \(L\) and \(L'\) so that the parity of the linking number between two components in \(L\) is the same as the parity of the linking number between the corresponding components of \(L'\).
Moreover, in the last two cases, the problem at hand is \textbf{NP}-complete. In fact, the parity-linking-number equivalence is coarser than all the other equivalence notions above, and hence the authors only need to carry out the proof for that.
For a bipartite graph \(G=(U \cup V, E)\), a bipartite drawing is a drawing of \(G\) in which all vertices of \(U\) lie on one line, all vertices of \(V\) on a parallel line, and all edges lie strictly between those two lines. The bipartite crossing number of \(G\) is the smallest number of crossings in any bipartite drawing of \(G\).
In order to prove the main theorem, the authors use a variant of a theorem of \textit{M. R. Garey} and \textit{D. S. Johnson} [SIAM J. Algebraic Discrete Methods 4, 312--316 (1983; Zbl 0536.05016)] namely: computing the bipartite crossing number for graphs is \textbf{NP}-complete. The variant that the authors use is due to \textit{X. Muñoz} et al. [Lect. Notes Comput. Sci. 2265, 115--123 (2002; Zbl 1054.68598)].
See the pioneering work of \textit{M. Lackenby} [Discrete Comput. Geom. 58, No. 3, 580--595 (2017; Zbl 1384.57010)], as well as the work of \textit{D. Koenig} and \textit{A. Tsvietkova} [``NP-hard problems naturally arising in knot theory'', Preprint, \url{arXiv:1809.10334}].
Reviewer: Mehdi Yazdi (Oxford)Reproduction of spatio-temporal structures of traffic flows using various ways of averaging data.https://www.zbmath.org/1455.900322021-03-30T15:24:00+00:00"Chechina, A. A."https://www.zbmath.org/authors/?q=ai:chechina.a-a"Churbanova, N. G."https://www.zbmath.org/authors/?q=ai:churbanova.natalia-g"Trapeznikova, M. A."https://www.zbmath.org/authors/?q=ai:trapeznikova.marina-aSummary: The work is devoted to testing of the two-dimensional microscopic cellular automatabased traffic flow model created by the authors using test problems found in literature, as well as comparing the obtained spatio-temporal diagrams of traffic flow speeds with experimental data. Optimal methods of averaging data for a more adequate reflection of the results are investigated.
The presented results confirm that the proposed CA model adequately reproduces the patterns observed on the velocity diagrams of real traffic flows, and also provides greater similarity with experimental data in comparison with other presented models.The limit shape of convex hull peeling.https://www.zbmath.org/1455.350472021-03-30T15:24:00+00:00"Calder, Jeff"https://www.zbmath.org/authors/?q=ai:calder.jeff"Smart, Charles K."https://www.zbmath.org/authors/?q=ai:smart.charles-kSummary: We prove that the convex peeling of a random point set in dimension \(d\) approximates motion by the \(1/(d+1)\) power of Gaussian curvature. We use viscosity solution theory to interpret the limiting partial differential equation (PDE). We use the martingale method to solve the cell problem associated to convex peeling. Our proof follows the program of Armstrong and Cardaliaguet for homogenization of geometric motions, but with completely different ingredients.Hardness results for three kinds of colored connections of graphs.https://www.zbmath.org/1455.681402021-03-30T15:24:00+00:00"Huang, Zhong"https://www.zbmath.org/authors/?q=ai:huang.zhong"Li, Xueliang"https://www.zbmath.org/authors/?q=ai:li.xueliangSummary: The concept of rainbow connection number of a graph was introduced by
\textit{G. Chartrand} et al. [Math. Bohem. 133, No. 1, 85--98 (2008; Zbl 1199.05106)].
Inspired by this concept, other concepts on colored version of connectivity in graphs were introduced, such as the monochromatic connection number by
\textit{Y. Caro} and \textit{R. Yuster} [Discrete Math. 311, No. 16, 1786--1792 (2011; Zbl 1223.05065)],
the proper connection number by
\textit{V. Borozan} et al. [Discrete Math. 312, No. 17, 2550--2560 (2012; Zbl 1246.05090)],
and the conflict-free connection number by
\textit{J. Czap} et al. [Discuss. Math., Graph Theory 38, No. 4, 911--920 (2018; Zbl 1392.05039)],
as well as some other variants of connection numbers later on. Chakraborty et al. proved that to compute the rainbow connection number of a graph is NP-hard. For a long time, it has been tried to fix the computational complexity for the monochromatic connection number, the proper connection number and the conflict-free connection number of a graph. However, it has not been solved yet. Only the complexity results for the strong version, i.e., the strong proper connection number and the strong conflict-free connection number, of these connection numbers were determined to be NP-hard. In this paper, we prove that to compute each of the monochromatic connection number, the proper connection number and the conflict free connection number for a graph is NP-hard. This solves a long standing problem in this field, asked in many talks of workshops and papers.Algorithmic information theory and its statistical mechanical interpretation.https://www.zbmath.org/1455.680762021-03-30T15:24:00+00:00"Tadaki, Kohtaro"https://www.zbmath.org/authors/?q=ai:tadaki.kohtaroThe paper reviews similarities between statistical mechanics and algorithmic information theory (AIT). It includes a presentation of some elements of AIT, formulations in AIT terms of the partition function, free energy, energy and statistical mechanical entropy. A discussion of the interpretation of temperature as partial randomness is given. No new results in either statistical mechanics or in AIT are proved.
Reviewer: Cristian S. Calude (Auckland)Path contraction faster than \(2^n\).https://www.zbmath.org/1455.681322021-03-30T15:24:00+00:00"Agrawal, Akanksha"https://www.zbmath.org/authors/?q=ai:agrawal.akanksha"Fomin, Fedor V."https://www.zbmath.org/authors/?q=ai:fomin.fedor-v"Lokshtanov, Daniel"https://www.zbmath.org/authors/?q=ai:lokshtanov.daniel"Saurabh, Saket"https://www.zbmath.org/authors/?q=ai:saurabh.saket"Tale, Prafullkumar"https://www.zbmath.org/authors/?q=ai:tale.prafullkumarAuthors' abstract: A graph \(G\) is contractible to a graph \(H\) if there is a set \(X\subseteq E(G)\), such that \(G/X\) is isomorphic to \(H\). Here, \(G/X\) is the graph obtained from \(G\) by contracting all the edges in \(X\). For a family of graphs \(\mathcal{F}\), the \(\mathcal{F}\)-Contraction problem takes as input a graph \(G\) on \(n\) vertices, and the objective is to output the largest integer \(t\), such that \(G\) is contractible to a graph \(H\in\mathcal{F}\), where \(|V(H)|=t\). When \(\mathcal{F}\) is the family of paths, then the corresponding \(\mathcal{F}\)-Contraction problem is called Path Contraction. The problem Path Contraction admits a simple algorithm running in time \(2^n\cdot n^{\mathcal{O}(1)}\). In spite of the deceptive simplicity of the problem, beating the \(2^n\cdot n^{\mathcal{O}(1)}\) bound for Path Contraction seems quite challenging. In this paper, we design an exact exponential time algorithm for Path Contraction that runs in time \(1.99987^n\cdot n^{\mathcal{O}(1)}\). We also define a problem called 3-Disjoint Connected Subgraphs and design an algorithm for it that runs in time \(1.88^n\cdot n^{\mathcal{O}(1)}\). The above algorithm is used as a subroutine in our algorithm for Path Contraction.
Reviewer: Xueliang Li (Tianjin)Weaker variants of infinite time Turing machines.https://www.zbmath.org/1455.030492021-03-30T15:24:00+00:00"Bianchetti, Matteo"https://www.zbmath.org/authors/?q=ai:bianchetti.matteoThe paper is devoted to infinite time Turing machines (for short: ITTM). ITTM are Turing machines that can halt and provide a result after infinitely many steps. They are far more powerful than ordinary Turing machines. They were introduced by \textit{J. D. Hamkins} and \textit{A. Lewis} [J. Symb. Log. 65, No. 2, 567--604 (2000; Zbl 0963.03064)], In the paper under review, models of infinitary computation whose computational power lies strictly between that of Turing machines and ITTMs are investigated. Four types of weak infinite time Turing machines are defined and some results about their computational power are proved. Special attention is paid to so called weak infinite time Turing machines (wITTM). They are defined by replacing in tye definitione of ITTM the lim sup rule with an `eventually constant' rule: at each limit step, the value of each cell isdefined if and only if the content of that cell has stabilized before that limit step and is then equal to this constant value. The author studies different variants of wITTMs adding multiple tapes, heads, or bidimensional tapes. It is shown that some of these models are equivalent to each other concerning their computational strength and that wITTMs decide exactly the arithmetic relations on natural numbers.
Reviewer: Roman Murawski (Poznań)Noncommutative algebras, context-free grammars and algebraic Hilbert series.https://www.zbmath.org/1455.160072021-03-30T15:24:00+00:00"La Scala, Roberto"https://www.zbmath.org/authors/?q=ai:la-scala.roberto"Piontkovski, Dmitri"https://www.zbmath.org/authors/?q=ai:piontkovski.dmitri"Tiwari, Sharwan K."https://www.zbmath.org/authors/?q=ai:tiwari.sharwan-kumarSummary: In this paper we introduce a class of noncommutative (finitely generated) monomial algebras whose Hilbert series are algebraic functions. We use the concept of graded homology and the theory of unambiguous context-free grammars for this purpose. We also provide examples of finitely presented graded algebras whose corresponding leading monomial algebras belong to the proposed class and hence possess algebraic Hilbert series.Distributed proximal gradient algorithm for partially asynchronous computer clusters.https://www.zbmath.org/1455.901382021-03-30T15:24:00+00:00"Zhou, Yi"https://www.zbmath.org/authors/?q=ai:zhou.yi"Liang, Yingbin"https://www.zbmath.org/authors/?q=ai:liang.yingbin"Yu, Yaoliang"https://www.zbmath.org/authors/?q=ai:yu.yaoliang"Dai, Wei"https://www.zbmath.org/authors/?q=ai:dai.wei.6|dai.wei|dai.wei.7"Xing, Eric P."https://www.zbmath.org/authors/?q=ai:xing.eric-pThe composite minimization problem, where the first term is a smooth loss function over some training samples that describes the fitness to data and the second term is a nonsmooth regularization function that encodes a priori information, is studied. The authors propose an m-PAPG (model parallel, Partially Asynchronous, Proximal Gradient), an implementation of the flexible proximal gradient algorithm in model parallel systems equipped with the partially asynchronous communication protocol. It is focused on the case of a large model size but a moderate data volume. Thus, implementing the proximal gradient algorithm on a single machine is no longer feasible, hence a distributed computation is necessary.
The main goal is to provide a formal convergence analysis of m-PAPG. It is proved that every limit point of the sequences generated by m-PAPG is a critical point of the objective function. Under an additional error bound condition of convex objective functions it is proved that the function values generated by m-PAPG decay periodically linearly. Lastly, under the Kurdyka-Lojasiewicz inequality and under a sufficient decrease assumption, it is proved that the whole sequences of m-PAPG converge to a single critical point for functions satisfying a proximal Lipschitz condition.
The results extend those in [\textit{D. P. Bertsekas} and \textit{J. N. Tsitsiklis}, Parallel and distributed computation: numerical methods. Reprint of the 1989 edition published by Prentice-Hall (1989; Zbl 1325.65001)] and [\textit{P. Tseng}, SIAM J. Optim. 1, No. 4, 603--619 (1991; Zbl 0754.90055)] to allow nonsmooth and nonconvex functions.
Reviewer: Ctirad Matonoha (Praha)Constrained pseudorandom functions for Turing machines revisited: how to achieve verifiability and key delegation.https://www.zbmath.org/1455.941482021-03-30T15:24:00+00:00"Datta, Pratish"https://www.zbmath.org/authors/?q=ai:datta.pratish"Dutta, Ratna"https://www.zbmath.org/authors/?q=ai:dutta.ratna"Mukhopadhyay, Sourav"https://www.zbmath.org/authors/?q=ai:mukhopadhyay.souravSummary: Constrained pseudorandom functions (CPRF) are an enriched variant of traditional pseudorandom functions (PRF) -- a fundamental tool of modern cryptography. A CPRF enables a master PRF key holder to issue constrained keys corresponding to specific constraint predicates over the input domain. A constrained key can be used to evaluate the PRF on inputs accepted by the associated constraint predicate, while the PRF outputs on the rest of the inputs still remain computationally indistinguishable from uniformly random values. A constrained verifiable pseudorandom function (CVPRF) enhances a CPRF by adding a non-interactive public verification mechanism for checking the correctness of PRF evaluations. On the other hand, a delegatable constrained pseudorandom function (DCPRF) augments a CPRF with the ability to empower constrained key holders to delegate further constrained keys that allow PRF evaluations on inputs accepted by more restricted constraint predicates compared to ones embedded in their own constrained keys. Until recently, all the proposed constructions of CPRFs and their extensions (i) either could handle constraint predicates representable as circuits or (ii) were based on risky knowledge-type assumptions. \textit{A. Deshpande} et al. [Lect. Notes Comput. Sci. 9666, 124--153 (2016; Zbl 1400.94140)] presented a CPRF supporting constraint predicates realizable by Turing machines (TM) based on indistinguishability obfuscation and injective pseudorandom generators. Their construction was claimed to be selectively secure. The first contribution of this paper is demonstrating that their claim is not valid. In fact, their CPRF construction can actually be proven secure not in the selective model, rather in a significantly weaker one where the adversary is completely static. We then modify their construction with innovative techniques so as to make the resulting CPRF selectively secure. Towards our goal, we suitably redesign the security proof as well. Most significantly, our modification does not involve any additional heavy duty cryptographic tool. Next, employing only standard public key encryption, we extend our improved CPRF construction to present the first ever CVPRF and DCPRF constructions that can handle constraints expressible as TMs.Kernels for (connected) dominating set on graphs with excluded topological minors.https://www.zbmath.org/1455.680722021-03-30T15:24:00+00:00"Fomin, Fedor V."https://www.zbmath.org/authors/?q=ai:fomin.fedor-v"Lokshtanov, Daniel"https://www.zbmath.org/authors/?q=ai:lokshtanov.daniel"Saurabh, Saket"https://www.zbmath.org/authors/?q=ai:saurabh.saket"Thilikos, Dimitrios M."https://www.zbmath.org/authors/?q=ai:thilikos.dimitrios-mBasic course computer science -- Exercise book. 148 exercises with solutions. 2nd corrected edition.https://www.zbmath.org/1455.680032021-03-30T15:24:00+00:00"Schmidt, Jochen"https://www.zbmath.org/authors/?q=ai:schmidt.jochen.2|schmidt.jochen.1|schmidt.jochen-wSee the review of the first edition in [Zbl 1427.68006].Secure diagnosability of hybrid dynamical systems.https://www.zbmath.org/1455.930912021-03-30T15:24:00+00:00"Fiore, Gabriella"https://www.zbmath.org/authors/?q=ai:fiore.gabriella"De Santis, Elena"https://www.zbmath.org/authors/?q=ai:de-santis.elena"Di Benedetto, Maria Domenica"https://www.zbmath.org/authors/?q=ai:di-benedetto.maria-domenicaSummary: Observability and diagnosability properties of a hybrid dynamical system are essential in characterizing the possibility of identifying the system's hybrid state, and in particular the occurrence of some specific states that may correspond to a malfunctioning of the system due to a fault or an attack. Diagnosability has been extensively studied for Finite State Machines (FSMs). However, the results obtained for FSMs cannot, in general, be applied directly to hybrid systems where the discrete evolution interacts with the continuous one. In this chapter, we propose a formal definition of diagnosability for hybrid systems. Furthermore, motivated by the great importance of security issues for hybrid systems, we characterize the diagnosability property in the more general case where the available information may be corrupted by an external attacker. Finally, we establish sufficient conditions for a hybrid system to be diagnosable.
For the entire collection see [Zbl 1417.68011].The inverse Voronoi problem in graphs. I: Hardness.https://www.zbmath.org/1455.681352021-03-30T15:24:00+00:00"Bonnet, Édouard"https://www.zbmath.org/authors/?q=ai:bonnet.edouard"Cabello, Sergio"https://www.zbmath.org/authors/?q=ai:cabello.sergio"Mohar, Bojan"https://www.zbmath.org/authors/?q=ai:mohar.bojan"Pérez-Rosés, Hebert"https://www.zbmath.org/authors/?q=ai:perez-roses.hebertSummary: We introduce the inverse Voronoi diagram problem in graphs: given a graph \(G\) with positive edge-lengths and a collection \({\mathbb{U}}\) of subsets of vertices of \(V(G)\), decide whether \({\mathbb{U}}\) is a Voronoi diagram in \(G\) with respect to the shortest-path metric. We show that the problem is NP-hard, even for planar graphs where all the edges have unit length. We also study the parameterized complexity of the problem and show that the problem is W[1]-hard when parameterized by the number of Voronoi cells or by the pathwidth of the graph.On the uncertainty of CFD in sail aerodynamics.https://www.zbmath.org/1455.760702021-03-30T15:24:00+00:00"Viola, Ignazio M."https://www.zbmath.org/authors/?q=ai:viola.ignazio-maria"Bot, P."https://www.zbmath.org/authors/?q=ai:bot.p"Riotte, M."https://www.zbmath.org/authors/?q=ai:riotte.mSummary: A verification and validation procedure for yacht sail aerodynamics is presented. Guidelines and an example of application are provided. The grid uncertainty for the aerodynamic lift, drag and pressure distributions for the sails is computed. The pressures are validated against experimental measurements, showing that the validation procedure may allow the identification of modelling errors. Lift, drag and \(L_2\) norm of the pressures were computed with uncertainties of the order of 1\%. Convergence uncertainty and round-off uncertainty are several orders of magnitude smaller than the grid uncertainty. The uncertainty due to the dimension of the computational domain is computed for a flat plate at incidence and is found to be significant compared with the other uncertainties. Finally, it is shown how the probability that the ranking between different geometries is correct can be estimated knowing the uncertainty in the computation of the value used to rank.On geometric complexity theory: multiplicity obstructions are stronger than occurrence obstructions.https://www.zbmath.org/1455.680692021-03-30T15:24:00+00:00"Dörfler, Julian"https://www.zbmath.org/authors/?q=ai:dorfler.julian"Ikenmeyer, Christian"https://www.zbmath.org/authors/?q=ai:ikenmeyer.christian"Panova, Greta"https://www.zbmath.org/authors/?q=ai:panova.gretaOn the approximate compressibility of connected vertex cover.https://www.zbmath.org/1455.681442021-03-30T15:24:00+00:00"Majumdar, Diptapriyo"https://www.zbmath.org/authors/?q=ai:majumdar.diptapriyo"Ramanujan, M. S."https://www.zbmath.org/authors/?q=ai:ramanujan.m-s"Saurabh, Saket"https://www.zbmath.org/authors/?q=ai:saurabh.saketSummary: The Connected Vertex Cover problem, where the goal is to compute a minimum set of vertices in a given graph which forms a vertex cover and induces a connected subgraph, is a fundamental combinatorial problem and has received extensive attention in various subdomains of algorithmics. In the area of kernelization, it is known that this problem is unlikely to have a polynomial kernelization algorithm. However, it has been shown in a recent work of
\textit{D. Lokshtanov} et al. [in: Proceedings of the 49th annual ACM SIGACT symposium on theory of computing, STOC'17. New York, NY: Association for Computing Machinery (ACM). 224--237 (2017; Zbl 1370.68136)]
that if one considered an appropriate notion of \textit{approximate kernelization}, then this problem parameterized by the solution size does admit an \textit{approximate} polynomial kernelization. In fact, Lokshtanov et al. were able to obtain a polynomial size approximate kernelization scheme (PSAKS) for Connected Vertex Cover parameterized by the solution size. A PSAKS is essentially a preprocessing algorithm whose error can be made arbitrarily close to 0. In this paper we revisit this problem, and consider parameters that are \textit{strictly smaller} than the size of the solution and obtain the first polynomial size approximate kernelization schemes for the Connected Vertex Cover problem when parameterized by the deletion distance of the input graph to the class of cographs, the class of bounded treewidth graphs, and the class of all chordal graphs.Presynthesis of bounded choice-free or fork-attribution nets.https://www.zbmath.org/1455.681302021-03-30T15:24:00+00:00"Wimmel, Harro"https://www.zbmath.org/authors/?q=ai:wimmel.harroSynthesis of Petri nets from labelled transition systems (LTS) aims at generating a Petri net such that its marking graph is isomorphic to the LTS. The synthesis problem asks whether such a Petri net exists. If the Petri net should satisfy some requirements, then the synthesis problem can be easier to solve, because sometimes the existence of a respective Petri net can be directly derived from properties of the LTS. It can also be harder, if no such properties are known.
This contribution considers choice-free nets, which have, for each place, exactly one output transition, and fork-attribution nets, which additionally have, for each transition, exactly one input place. It was previously shown that marking graphs of choice-free nets have structural properties which can be employed for a so-called presynthesis: the LTS must enjoy these properties if the synthesis problem for choice-free nets has a solution. This paper generalizes and extends this result to fork-attribution nets and presents and analyzes a respective improved algorithm. Although fork-attribution nets are close to marked graphs (each transition has exactly one input and one output place), for which the synthesis problem is particularly simple to solve, the author convincingly argues that a similar result can only be obtained for plain fork-attribution nets (no weighted arcs).
Reviewer: Jörg Desel (Hagen)Minimum-width double-strip and parallelogram annulus.https://www.zbmath.org/1455.682282021-03-30T15:24:00+00:00"Bae, Sang Won"https://www.zbmath.org/authors/?q=ai:bae.sang-wonA planar strip is the closed set of points between two parallel lines, and its width is the (orthogonal) distance between these lines.
A double strip is the closure of the difference of an outer strip and an included inner strip, its width being half the difference between both strips' widths. A parallelogram annulus is obtained from two double strips of different orientations by intersecting their outer strips and deleting the interior of the intersected inner strips, its width being the larger of both double strip widths.
Given a set of \(n\) points \(P\) in the plane and a subset \(Q\) of size \(k\), a minimum-width double strip containing \(Q\) with outer strip containing \(P\) can be computed in \(O(n\log n+kn)\) time using the geometric dual. With a same complexity one may compute such a minimum-width double strip for all stepwise reduced \(Q\) in prespecified order. A minimum-width parallelogram annulus containing \(P\) is computable in \(O(n)\) time for two fixed orientations, in \(O(n^2)\) time for a single fixed orientation, and in \(O(n^3\log n)\) time when both orientations are free.
Reviewer: Frank Plastria (Brussels)An FPTAS for the volume of some \(\mathcal{V} \)-polytopes -- it is hard to compute the volume of the intersection of two cross-polytopes.https://www.zbmath.org/1455.682732021-03-30T15:24:00+00:00"Ando, Ei"https://www.zbmath.org/authors/?q=ai:ando.ei"Kijima, Shuji"https://www.zbmath.org/authors/?q=ai:kijima.shujiA \(\mathcal{V} \)-polytope is a convex hull of a finite point set in \(\mathbb{R}^n\). A particular type of \(\mathcal{V} \)-polytope, called ``knapsack dual polytope'' is defined as \(P_{a}=\text{conv}\{\pm e_1, \pm e_2, ..., \pm e_n, a\}\), \(a\in \mathbb{Z}^n_{\geq 0}\). The authors constructively prove the following theorem: For any \(\varepsilon\), \((0 <\varepsilon <1)\), there is a deterministic algorithm that computes \(\hat{V}\) satisfying \(|1- \frac{\text{Vol}(P_a)}{\hat{V}}| \leq \varepsilon\) in \(O(n^{10}\varepsilon^{-6})\) time. This is the first result on designing a fully polynomial time approximation scheme for computing the volume of a \(\mathcal{V} \)-polytope, which is known to be \#P-hard.
Reviewer: Gabriela Cristescu (Arad)UTP semantics of a calculus for mobile ad hoc networks.https://www.zbmath.org/1455.680302021-03-30T15:24:00+00:00"Wu, Xi"https://www.zbmath.org/authors/?q=ai:wu.xi"Zhu, Huibiao"https://www.zbmath.org/authors/?q=ai:zhu.huibiao"Xie, Wanling"https://www.zbmath.org/authors/?q=ai:xie.wanlingSummary: The mCWQ calculus was recently proposed for describing the features of local broadcast and mobility in Mobile Ad Hoc Networks (MANETs), focusing on the quality of wireless communications. In this paper, we investigate the denotational semantics for mCWQ calculus, whose behaviour is composed of the behaviours of subnetworks. A trace variable tr is introduced to record the communications among wireless nodes as well as the time points when the communications happen. A set of algebraic laws, especially the laws about the communications with quality binders, are also explored based on the formalized model.
For the entire collection see [Zbl 1419.68018].Tropical combinatorial Nullstellensatz and sparse polynomials.https://www.zbmath.org/1455.141262021-03-30T15:24:00+00:00"Grigoriev, Dima"https://www.zbmath.org/authors/?q=ai:grigorev.dimitri-yu"Podolskii, Vladimir V."https://www.zbmath.org/authors/?q=ai:podolskii.vladimir-vSummary: Tropical algebra emerges in many fields of mathematics such as algebraic geometry, mathematical physics and combinatorial optimization. In part, its importance is related to the fact that it makes various parameters of mathematical objects computationally accessible. Tropical polynomials play a fundamental role in this, especially for the case of algebraic geometry. On the other hand, many algebraic questions behind tropical polynomials remain open. In this paper, we address four basic questions on tropical polynomials closely related to their computational properties:
\begin{itemize}
\item [1.] Given a polynomial with a certain support (set of monomials) and a (finite) set of inputs, when is it possible for the polynomial to vanish on all these inputs?
\item [2.] A more precise question, given a polynomial with a certain support and a (finite) set of inputs, how many roots can this polynomial have on this set of inputs?
\item [3.] Given an integer \(k\), for which \(s\) there is a set of \(s\) inputs such that any nonzero polynomial with at most \(k\) monomials has a non-root among these inputs?
\item [4.] How many integer roots can have a one variable polynomial given by a tropical algebraic circuit?
\end{itemize}
In the classical algebra well-known results in the direction of these questions are Combinatorial Nullstellensatz due to N. Alon, J. Schwartz-R. Zippel Lemma and Universal Testing Set for sparse polynomials, respectively. The classical analog of the last question is known as \(\tau \)-conjecture due to M. Shub-S. Smale. In this paper, we provide results on these four questions for tropical polynomials.New choice for small universal devices: symport/antiport P systems.https://www.zbmath.org/1455.680622021-03-30T15:24:00+00:00"Verlan, Sergey"https://www.zbmath.org/authors/?q=ai:verlan.sergey"Rogozhin, Yurii"https://www.zbmath.org/authors/?q=ai:rogozhin.yuriiSummary: Symport/antiport P systems provide a very simple machinery inspired by corresponding operations in the living cell. It turns out that systems of small descriptional complexity are needed to achieve the universality by these systems. This makes them a good candidate for small universal devices replacing register machines for different simulations, especially when a simulating parallel machinery is involved. This article contains survey of these systems and presents different trade-offs between parameters.
For the entire collection see [Zbl 1392.68029].Computational processes and incompleteness.https://www.zbmath.org/1455.681152021-03-30T15:24:00+00:00"Sutner, Klaus"https://www.zbmath.org/authors/?q=ai:sutner.klausSummary: We introduce a formal definition of Wolfram's notion of computational process based on cellular automata, a physics-like model of computation. There is a natural classification of these processes into decidable, intermediate and complete. It is shown that in the context of standard finite injury priority arguments one cannot establish the existence of an intermediate computational process.
For the entire collection see [Zbl 1392.68029].Self-assembly of infinite structures.https://www.zbmath.org/1455.680642021-03-30T15:24:00+00:00"Patitz, Matthew J."https://www.zbmath.org/authors/?q=ai:patitz.matthew-j"Summers, Scott M."https://www.zbmath.org/authors/?q=ai:summers.scott-mSummary: We review some recent results related to the self-assembly of infinite structures in the Tile Assembly Model. These results include impossibility results, as well as novel tile assembly systems in which shapes and patterns that represent various notions of computation self-assemble. Several open questions are also presented and motivated.
For the entire collection see [Zbl 1392.68029].A particular universal cellular automaton.https://www.zbmath.org/1455.681142021-03-30T15:24:00+00:00"Ollinger, Nicolas"https://www.zbmath.org/authors/?q=ai:ollinger.nicolas"Richard, Gaétan"https://www.zbmath.org/authors/?q=ai:richard.gaetanSummary: Signals are a classical tool used in cellular automata constructions that proved to be useful for language recognition or firing-squad synchronisation. Particles and collisions formalize this idea one step further, describing regular nets of colliding signals. In the present paper, we investigate the use of particles and collisions for constructions involving an infinite number of interacting particles. We obtain a high-level construction for a new smallest intrinsically universal cellular automaton with 4 states.
For the entire collection see [Zbl 1392.68029].Intrinsically universal cellular automata.https://www.zbmath.org/1455.681132021-03-30T15:24:00+00:00"Ollinger, Nicolas"https://www.zbmath.org/authors/?q=ai:ollinger.nicolasSummary: This talk advocates intrinsic universality as a notion to identify simple cellular automata with complex computational behavior. After an historical introduction and proper definitions of intrinsic universality, which is discussed with respect to Turing and circuit universality, we discuss construction methods for small intrinsically universal cellular automata before discussing techniques for proving non universality.
For the entire collection see [Zbl 1392.68029].Representing a P-complete problem by small trellis automata.https://www.zbmath.org/1455.680702021-03-30T15:24:00+00:00"Okhotin, Alexander"https://www.zbmath.org/authors/?q=ai:okhotin.alexanderSummary: A restricted case of the Circuit Value Problem known as the Sequential NOR Circuit Value Problem was recently used to obtain very succinct examples of conjunctive grammars, Boolean grammars and language equations representing P-complete languages [the author, Lect. Notes Comput. Sci. 4664, 267--278 (2007; Zbl 1211.68237)].
In this paper, a new encoding of the same problem is proposed, and a trellis automaton (one-way real-time cellular automaton) with 11 states solving this problem is constructed.
For the entire collection see [Zbl 1392.68029].On acceptance conditions for membrane systems: characterisations of \textbf{L} and \textbf{NL}.https://www.zbmath.org/1455.680612021-03-30T15:24:00+00:00"Murphy, Niall"https://www.zbmath.org/authors/?q=ai:murphy.niall"Woods, Damien"https://www.zbmath.org/authors/?q=ai:woods.damienSummary: In this paper we investigate the affect of various acceptance conditions on recogniser membrane systems without dissolution. We demonstrate that two particular acceptance conditions (one easier to program, the other easier to prove correctness) both characterise the same complexity class, \textbf{NL}. We also find that by restricting the acceptance conditions we obtain a characterisation of \textbf{L}. We obtain these results by investigating the connectivity properties of dependency graphs that model membrane system computations.
For the entire collection see [Zbl 1392.68029].A general notion of useful information.https://www.zbmath.org/1455.680752021-03-30T15:24:00+00:00"Moser, Philippe"https://www.zbmath.org/authors/?q=ai:moser.philippeSummary: In this paper we introduce a general framework for defining the depth of a sequence with respect to a class of observers. We show that our general framework captures all depth notions introduced in complexity theory so far. We review most such notions, show how they are particular cases of our general depth framework, and review some classical results about the different depth notions.
For the entire collection see [Zbl 1392.68029].The Pagoda sequence: a ramble through linear complexity, number walls, D0L sequences, finite state automata, and aperiodic tilings.https://www.zbmath.org/1455.681542021-03-30T15:24:00+00:00"Lunnon, Fred"https://www.zbmath.org/authors/?q=ai:lunnon.fred.1Summary: We review the concept of the number wall as an alternative to the traditional linear complexity profile (LCP), and sketch the relationship to other topics such as linear feedback shift-register (LFSR) and context-free Lindenmayer (D0L) sequences. A remarkable ternary analogue of the Thue-Morse sequence is introduced having deficiency 2 modulo 3, and this property verified via the re-interpretation of the number wall as an aperiodic plane tiling.
For the entire collection see [Zbl 1392.68029].Some considerations on universality.https://www.zbmath.org/1455.680552021-03-30T15:24:00+00:00"Kudlek, Manfred"https://www.zbmath.org/authors/?q=ai:kudlek.manfredSummary: The paper puts into discussion the concept of universality, in particular for structures not of the power of Turing computability. The question arises if for such structures a universal structure of the same kind exists or not. For that the construction of universal Turing machines and those with some constraints are presented in some detail.
For the entire collection see [Zbl 1392.68029].Computational power of P systems with small size insertion and deletion rules.https://www.zbmath.org/1455.680602021-03-30T15:24:00+00:00"Krassovitskiy, Alexander"https://www.zbmath.org/authors/?q=ai:krassovitskiy.alexander"Rogozhin, Yurii"https://www.zbmath.org/authors/?q=ai:rogozhin.yurii"Verlan, Sergey"https://www.zbmath.org/authors/?q=ai:verlan.sergeySummary: Recent investigations show insertion-deletion systems of small size that are not complete and cannot generate all recursively enumerable languages. However, if additional computational distribution mechanisms like P systems are added, then the computational completeness is achieved in some cases. In this article we take two insertion-deletion systems that are not computationally complete, consider them in the framework of P systems and show that the computational power is strictly increased by proving that any recursively enumerable language can be generated. At the end some open problems are presented.
For the entire collection see [Zbl 1392.68029].Communications in cellular automata.https://www.zbmath.org/1455.681092021-03-30T15:24:00+00:00"Goles, Eric"https://www.zbmath.org/authors/?q=ai:goles-chacc.eric"Meunier, Pierre-Etienne"https://www.zbmath.org/authors/?q=ai:meunier.pierre-etienne"Rapaport, Ivan"https://www.zbmath.org/authors/?q=ai:rapaport.ivan"Theyssier, Guillaume"https://www.zbmath.org/authors/?q=ai:theyssier.guillaumeSummary: The goal of this paper is to show why the framework of communication complexity seems suitable for the study of cellular automata. Researchers have tackled different algorithmic problems ranging from the complexity of predicting to the decidability of different dynamical properties of cellular automata. But the difference here is that we look for communication protocols arising in the dynamics itself. Our work is guided by the following idea: if we are able to give a protocol describing a cellular automaton, then we can understand its behavior.
For the entire collection see [Zbl 1392.68029].Small Turing universal signal machines.https://www.zbmath.org/1455.680542021-03-30T15:24:00+00:00"Durand-Lose, Jérôme"https://www.zbmath.org/authors/?q=ai:durand-lose.jerome-oSummary: This article aims at providing signal machines as small as possible able to perform any computation (in the classical understanding). After presenting signal machines, it is shown how to get universal ones from Turing machines, cellular-automata and cyclic tag systems. Finally a halting universal signal machine with 13 meta-signals and 21 collision rules is presented.
For the entire collection see [Zbl 1392.68029].Complexity through the observation of simple systems.https://www.zbmath.org/1455.680632021-03-30T15:24:00+00:00"Cavaliere, Matteo"https://www.zbmath.org/authors/?q=ai:cavaliere.matteo"Leupold, Peter"https://www.zbmath.org/authors/?q=ai:leupold.peterSummary: We survey work on the paradigm called ``computing by observing''. Its central feature is that one considers the behavior of an evolving system as the result of a computation. To this end an observer records this behavior. It has turned out that the observed behavior of computationally simple systems can be very complex, when an appropriate observer is used. For example, a restricted version of context-free grammars with regular observers suffices to obtain computational completeness. As a second instantiation presented here, we apply an observer to sticker systems. Finally, some directions for further research are proposed.
For the entire collection see [Zbl 1392.68029].Simplicity via provability for universal prefix-free Turing machines.https://www.zbmath.org/1455.030502021-03-30T15:24:00+00:00"Calude, Cristian S."https://www.zbmath.org/authors/?q=ai:calude.cristian-sSummary: Universality is one of the most important ideas in computability theory. There are various criteria of simplicity for universal Turing machines. Probably the most popular one is to count the number of states/symbols. This criterion is more complex than it may appear at a first glance. In this note we review recent results in Algorithmic Information Theory and propose three new criteria of simplicity for universal prefix-free Turing machines. These criteria refer to the possibility of proving various natural properties of such a machine (its universality, for example) in a formal theory, PA or ZFC. In all cases some, but not all, machines are simple.
For the entire collection see [Zbl 1392.68029].Playing with population protocols.https://www.zbmath.org/1455.680312021-03-30T15:24:00+00:00"Bournez, Olivier"https://www.zbmath.org/authors/?q=ai:bournez.olivier"Chalopin, Jérémie"https://www.zbmath.org/authors/?q=ai:chalopin.jeremie"Cohen, Johanne"https://www.zbmath.org/authors/?q=ai:cohen.johanne"Koegler, Xavier"https://www.zbmath.org/authors/?q=ai:koegler.xavierSummary: Population protocols have been introduced as a model of sensor networks consisting of very limited mobile agents with no control over their own movement: A collection of anonymous agents, modeled by finite automata, interact in pairs according to some rules.
Predicates on the initial configurations that can be computed by such protocols have been characterized under several hypotheses.
We discuss here whether and when the rules of interactions between agents can be seen as a game from game theory. We do so by discussing several basic protocols.
For the entire collection see [Zbl 1392.68029].Universal computation in a simplified Brownian cellular automaton with von Neumann neighborhood.https://www.zbmath.org/1455.681162021-03-30T15:24:00+00:00"Xu, Wen-Li"https://www.zbmath.org/authors/?q=ai:xu.wenli"Lee, Jia"https://www.zbmath.org/authors/?q=ai:lee.jia"Chen, Hui-Hui"https://www.zbmath.org/authors/?q=ai:chen.huihui"Isokawa, Teijiro"https://www.zbmath.org/authors/?q=ai:isokawa.teijiroSummary: A Brownian cellular automaton (BCA) is an asynchronous cellular automaton (ACA) in which local configurations representing signals may move forth and back randomly, as if they were undergoing random walks. The random fluctuation offers a natural mechanism to propagate signals in the 2-dimensional cell space, and to cross signals moving in directions perpendicular to each other. As a result, the BCA
in [\textit{J. Lee} et al., Inf. Sci. 352--353, 150--166 (2016; Zbl 1398.68354); ``Brownian circuits: designs'', Int. J. Unconvent. Comput. 12, 341--362 (2016)]
employs 4 cell states and 17 transition rules to conduct universal computation, both of which are less than other equivalent ACAs in the literature. This paper aims to advance the fluctuation-based scheme one step further, via proposing a new BCA with 4 states and 14 rules that achieves a reduction in the number of transition rules. We show that the BCA is capable of implementing any arbitrary logic circuit, thereby proving its universality in computation. We illustrate this by implementing a circuit that converts a 4-bit number to its equivalent hexadecimal digit.Complexity in prefix-free regular languages.https://www.zbmath.org/1455.680922021-03-30T15:24:00+00:00"Jirásková, Galina"https://www.zbmath.org/authors/?q=ai:jiraskova.galina"Krausová, Monika"https://www.zbmath.org/authors/?q=ai:krausova.monikaSummary: We examine deterministic and nondeterministic state complexities of regular operations on prefix-free languages. We strengthen several results by providing witness languages over smaller alphabets, usually as small as possible. We next provide the tight bounds on state complexity of symmetric difference, and deterministic and nondeterministic state complexity of difference and cyclic shift of prefix-free languages.
For the entire collection see [Zbl 1392.68027].Nondeterministic state complexity for suffix-free regular languages.https://www.zbmath.org/1455.680912021-03-30T15:24:00+00:00"Han, Yo-Sub"https://www.zbmath.org/authors/?q=ai:han.yo-sub"Salomaa, Kai"https://www.zbmath.org/authors/?q=ai:salomaa.kai-tSummary: We investigate the nondeterministic state complexity of basic operations for suffix-free regular languages. The nondeterministic state complexity of an operation is the number of states that are necessary and sufficient in the worst-case for a minimal nondeterministic finite-state automaton that accepts the language obtained from the operation. We consider basic operations (catenation, union, intersection, Kleene star, reversal and complementation) and establish matching upper and lower bounds for each operation. In the case of complementation the upper and lower bounds differ by an additive constant of two.
For the entire collection see [Zbl 1392.68027].On the descriptional complexity of limited propagating Lindenmayer systems.https://www.zbmath.org/1455.680802021-03-30T15:24:00+00:00"Truthe, Bianca"https://www.zbmath.org/authors/?q=ai:truthe.biancaSummary: We investigate the descriptional complexity of limited propagating Lindenmayer systems and their deterministic and tabled variants with respect to the number of rules and the number of symbols. We determine the decrease of complexity when the generative capacity is increased. For incomparable families, we give languages that can be described more efficiently in either of these families than in the other.
For the entire collection see [Zbl 1392.68027].The maximal subword complexity of quasiperiodic infinite words.https://www.zbmath.org/1455.681552021-03-30T15:24:00+00:00"Polley, Ronny"https://www.zbmath.org/authors/?q=ai:polley.ronny"Staiger, Ludwig"https://www.zbmath.org/authors/?q=ai:staiger.ludwigSummary: We provide an exact estimate on the maximal subword complexity for quasiperiodic infinite words. To this end we give a representation of the set of finite and of infinite words having a certain quasiperiod \(q\) via a finite language derived from \(q\). It is shown that this language is a suffix code having a bounded delay of decipherability.
Our estimate of the subword complexity now follows from this result, previously known results on the subword complexity and elementary results on formal power series.
For the entire collection see [Zbl 1392.68027].Transformations between different types of unranked bottom-up tree automata.https://www.zbmath.org/1455.680962021-03-30T15:24:00+00:00"Piao, Xiaoxue"https://www.zbmath.org/authors/?q=ai:piao.xiaoxue"Salomaa, Kai"https://www.zbmath.org/authors/?q=ai:salomaa.kai-tSummary: We consider the representational state complexity of unranked tree automata. The bottom-up computation of an unranked tree automaton may be either deterministic or nondeterministic, and further variants arise depending on whether the horizontal string languages defining the transitions are represented by a DFA or an NFA. Also, we consider for unranked tree automata the alternative syntactic definition of determinism introduced by
\textit{J. Cristau} et al. [Lect. Notes Comput. Sci. 3623, 68--79 (2005; Zbl 1123.68055)].
We establish upper and lower bounds for the state complexity of conversions between different types of unranked tree automata.
For the entire collection see [Zbl 1392.68027].Operational state complexity of deterministic unranked tree automata.https://www.zbmath.org/1455.680952021-03-30T15:24:00+00:00"Piao, Xiaoxue"https://www.zbmath.org/authors/?q=ai:piao.xiaoxue"Salomaa, Kai"https://www.zbmath.org/authors/?q=ai:salomaa.kai-tSummary: We consider the state complexity of basic operations on tree languages recognized by deterministic unranked tree automata. For the operations of union and intersection the upper and lower bounds of both weakly and strongly deterministic tree automata are obtained. For tree concatenation we establish a tight upper bound that is of a different order than the known state complexity of concatenation of regular string languages. We show that \((n+1)((m+1)2^n-2^{n-1})-1\) vertical states are sufficient, and necessary in the worst case, to recognize the concatenation of tree languages recognized by (strongly or weakly) deterministic automata with, respectively, \(m\) and \(n\) vertical states.
For the entire collection see [Zbl 1392.68027].State elimination ordering strategies: some experimental results.https://www.zbmath.org/1455.680942021-03-30T15:24:00+00:00"Moreira, Nelma"https://www.zbmath.org/authors/?q=ai:moreira.nelma"Nabais, Davide"https://www.zbmath.org/authors/?q=ai:nabais.davide"Reis, Rogério"https://www.zbmath.org/authors/?q=ai:reis.rogerioSummary: Recently, the problem of obtaining a short regular expression equivalent to a given finite automaton has been intensively investigated. Algorithms for converting finite automata to regular expressions have an exponential blow-up in the worst-case. To overcome this, simple heuristic methods have been proposed. In this paper we analyse some of the heuristics presented in the literature and propose new ones. We also present some experimental comparative results based on uniform random generated deterministic finite automata.
For the entire collection see [Zbl 1392.68027].Descriptional complexity of the languages \(KaL\): automata, monoids and varieties.https://www.zbmath.org/1455.680932021-03-30T15:24:00+00:00"Klíma, Ondřej"https://www.zbmath.org/authors/?q=ai:klima.ondrej"Polák, Libor"https://www.zbmath.org/authors/?q=ai:polak.liborSummary: The first step when forming the polynomial hierarchies of languages is to consider languages of the form \(KaL\) where \(K\) and \(L\) are over a finite alphabet \(A\) and from a given variety \(\mathcal{V}\) of languages, \(a\in A\). All such \(KaL\)'s generate the variety of languages \(\mathsf{BPol}_1(\mathcal{V})\).
We estimate the numerical parameters of the language \(KaL\) in terms of their values for \(K\) and \(L\). These parameters include the state complexity of the minimal complete DFA and the size of the syntactic monoids. We also estimate the cardinality of the image of \(A^*\) in the Schuetzenberger product of the syntactic monoids of \(K\) and \(L\). In these three cases we obtain the optimal bounds.
Finally, we also consider estimates for the cardinalities of free monoids in the variety of monoids corresponding to \(\mathsf{BPol}_1(\mathcal{V})\) in terms of sizes of the free monoids in the variety of monoids corresponding to \(\mathcal{V}\).
For the entire collection see [Zbl 1392.68027].Ciliate gene unscrambling with fewer templates.https://www.zbmath.org/1455.680592021-03-30T15:24:00+00:00"Kari, Lila"https://www.zbmath.org/authors/?q=ai:kari.lila"Rahman, Afroza"https://www.zbmath.org/authors/?q=ai:rahman.afrozaSummary: One of the theoretical models proposed for the mechanism of gene unscrambling in some species of ciliates is the template-guided recombination (TGR) system by Prescott, Ehrenfeucht and Rozenberg which has been generalized by Daley and McQuillan from a formal language theory perspective. In this paper, we propose a refinement of this model that generates regular languages using the iterated TGR system with a finite initial language and a finite set of templates, using fewer templates and a smaller alphabet compared to that of the Daley-McQuillan model. To achieve Turing completeness using only finite components, i.e., a finite initial language and a finite set of templates, we also propose an extension of the contextual template-guided recombination system (CTGR system) by Daley and McQuillan, by adding an extra control called permitting contexts on the usage of templates.
For the entire collection see [Zbl 1392.68027].Transition complexity of incomplete DFAs.https://www.zbmath.org/1455.680902021-03-30T15:24:00+00:00"Gao, Yuan"https://www.zbmath.org/authors/?q=ai:gao.yuan"Salomaa, Kai"https://www.zbmath.org/authors/?q=ai:salomaa.kai-t"Yu, Sheng"https://www.zbmath.org/authors/?q=ai:yu.shengSummary: In this paper, we consider the transition complexity of regular languages based on the incomplete deterministic finite automata. A number of results on Boolean operations have been obtained. It is shown that the transition complexity results for union and complementation are very different from the state complexity results for the same operations. However, for intersection, the transition complexity result is similar to that of state complexity.
For the entire collection see [Zbl 1392.68027].Graph-controlled insertion-deletion systems.https://www.zbmath.org/1455.680782021-03-30T15:24:00+00:00"Freund, Rudolf"https://www.zbmath.org/authors/?q=ai:freund.rudolf"Kogler, Marian"https://www.zbmath.org/authors/?q=ai:kogler.marian"Rogozhin, Yurii"https://www.zbmath.org/authors/?q=ai:rogozhin.yurii"Verlan, Sergey"https://www.zbmath.org/authors/?q=ai:verlan.sergeySummary: In this article, we consider the operations of insertion and deletion working in a graph-controlled manner. We show that like in the case of context-free productions, the computational power is strictly increased when using a control graph: computational completeness can be obtained by systems with insertion or deletion rules involving at most two symbols in a contextual or in a context-free manner and with the control graph having only four nodes.
For the entire collection see [Zbl 1392.68027].Representing small ordinals by finite automata.https://www.zbmath.org/1455.680882021-03-30T15:24:00+00:00"Ésik, Zoltan"https://www.zbmath.org/authors/?q=ai:esik.zoltanSummary: It is known that an ordinal is the order type of the lexicographic ordering of a regular language if and only if it is less than \(\omega^{\omega}\). We design a polynomial time algorithm that constructs, for each well-ordered regular language \(L\) with respect to the lexicographic ordering, given by a deterministic finite automaton, the Cantor Normal Form of its order type. It follows that there is a polynomial time algorithm to decide whether two deterministic finite automata accepting well-ordered regular languages accept isomorphic languages. We also give estimates on the size of the smallest automaton representing an ordinal less than \(\omega^{\omega}\), together with an algorithm that translates each such ordinal to an automaton.
For the entire collection see [Zbl 1392.68027].Accepting hybrid networks of evolutionary processors with special topologies and small communication.https://www.zbmath.org/1455.680652021-03-30T15:24:00+00:00"Dassow, Jürgen"https://www.zbmath.org/authors/?q=ai:dassow.jurgen"Manea, Florin"https://www.zbmath.org/authors/?q=ai:manea.florinSummary: Starting from the fact that complete Accepting Hybrid Networks of Evolutionary Processors allow much communication between the nodes and are far from network structures used in practice, we propose in this paper three network topologies that restrict the communication: star networks, ring networks, and grid networks. We show that ring-AHNEPs can simulate 2-tag systems, thus we deduce the existence of a universal ring-AHNEP. For star networks or grid networks, we show a more general result; that is, each recursively enumerable language can be accepted efficiently by a star- or grid-AHNEP. We also present bounds for the size of these star and grid networks. As a consequence we get that each recursively enumerable can be accepted by networks with at most 13 communication channels and by networks where each node communicates with at most three other nodes.
For the entire collection see [Zbl 1392.68027].State complexity of catenation combined with star and reversal.https://www.zbmath.org/1455.680862021-03-30T15:24:00+00:00"Cui, Bo"https://www.zbmath.org/authors/?q=ai:cui.bo"Gao, Yuan"https://www.zbmath.org/authors/?q=ai:gao.yuan"Kari, Lila"https://www.zbmath.org/authors/?q=ai:kari.lila"Yu, Sheng"https://www.zbmath.org/authors/?q=ai:yu.shengSummary: This paper is a continuation of our research work on state complexity of combined operations. Motivated by applications, we study the state complexities of two particular combined operations: catenation combined with star and catenation combined with reversal. We show that the state complexities of both of these combined operations are considerably less than the compositions of the state complexities of their individual participating operations.
For the entire collection see [Zbl 1392.68027].State complexity of testing divisibility.https://www.zbmath.org/1455.680852021-03-30T15:24:00+00:00"Charlier, Emilie"https://www.zbmath.org/authors/?q=ai:charlier.emilie"Rampersad, Narad"https://www.zbmath.org/authors/?q=ai:rampersad.narad"Rigo, Michel"https://www.zbmath.org/authors/?q=ai:rigo.michel"Waxweiler, Laurent"https://www.zbmath.org/authors/?q=ai:waxweiler.laurentSummary: Under some mild assumptions, we study the state complexity of the trim minimal automaton accepting the greedy representations of the multiples of \(m\ge 2\) for a wide class of linear numeration systems. As an example, the number of states of the trim minimal automaton accepting the greedy representations of the multiples of \(m\mathbb{N}\) in the Fibonacci system is exactly \(2m^2\).
For the entire collection see [Zbl 1392.68027].Quantum algorithm for the multicollision problem.https://www.zbmath.org/1455.680672021-03-30T15:24:00+00:00"Hosoyamada, Akinori"https://www.zbmath.org/authors/?q=ai:hosoyamada.akinori"Sasaki, Yu"https://www.zbmath.org/authors/?q=ai:sasaki.yu"Tani, Seiichiro"https://www.zbmath.org/authors/?q=ai:tani.seiichiro"Xagawa, Keita"https://www.zbmath.org/authors/?q=ai:xagawa.keitaSummary: The current paper presents a new quantum algorithm for finding multicollisions, often denoted by \(\ell \)-collisions, where an \(\ell \)-collision for a function is a set of \(\ell \) distinct inputs that are mapped by the function to the same value. In cryptology, it is important to study how many queries are required to find an \(\ell \)-collision for a random function of which domain is larger than its range. However, the problem of finding \(\ell \)-collisions for random functions has not received much attention in the quantum setting. The tight bound of quantum query complexity for finding a 2-collisions of a random function has been revealed to be \({\Theta}( N^{1 / 3})\), where \(N\) is the size of the range of the function, but neither the lower nor upper bounds are known for general \(\ell \)-collisions. The paper first integrates the results from existing research to derive several new observations, e.g., \( \ell \)-collisions can be generated only with \(O( N^{1 / 2})\) quantum queries for any integer constant \(\ell \). It then provides a quantum algorithm that finds an \(\ell \)-collision for a random function with the average quantum query complexity of \(O( N^{( 2^{\ell - 1} - 1 ) / ( 2^\ell - 1 )})\), which matches the tight bound of \({\Theta}( N^{1 / 3})\) for \(\ell = 2\) and improves upon the known bounds, including the above simple bound of \(O( N^{1 / 2})\). More generally, the algorithm achieves the average quantum query complexity of \(O( c_N \cdot N^{( 2^{\ell - 1} - 1 ) / ( 2^\ell - 1 )})\), and runs over \(\widetilde{O}( c_N \cdot N^{( 2^{\ell - 1} - 1 ) / ( 2^\ell - 1 )})\) qubits in \(\widetilde{O}( c_N \cdot N^{( 2^{\ell - 1} - 1 ) / ( 2^\ell - 1 )})\) expected time for a random function \(F : X \to Y\) such that \(| X | \geq \ell \cdot | Y | / c_N\) for any \(1 \leq c_N \in o( N^{1 / ( 2^\ell - 1 )})\), where it is assumed that QRAM is available. With the same query complexity, it is actually able to find a multiclaw for random functions, which is harder to find than a multicollision.On the complexity of the evaluation of transient extensions of Boolean functions.https://www.zbmath.org/1455.680562021-03-30T15:24:00+00:00"Brzozowski, Janusz"https://www.zbmath.org/authors/?q=ai:brzozowski.janusz-a"Li, Baiyu"https://www.zbmath.org/authors/?q=ai:li.baiyu"Ye, Yuli"https://www.zbmath.org/authors/?q=ai:ye.yuliSummary: Transient algebra is a multi-valued algebra for hazard detection in gate circuits. Sequences of alternating 0's and 1's, called transients, represent signal values, and gates are modeled by extensions of Boolean functions to transients. Formulas for computing the output transient of a gate from the input transients are known for \textsc{not}, \textsc{and}, \textsc{or} and \textsc{xor} gates and their complements, but, in general, even the problem of deciding whether the length of the output transient exceeds a given bound is NP-complete. We propose a method of evaluating extensions of general Boolean functions. We introduce and study a class of functions with the following property: Instead of evaluating an extension of a Boolean function on a given set of transients, it is possible to get the same value by using transients derived from the given ones, but having length at most 3. We prove that all functions of three variables, as well as certain other functions, have this property, and can be efficiently evaluated.
For the entire collection see [Zbl 1392.68027].L-systems in geometric modeling.https://www.zbmath.org/1455.682322021-03-30T15:24:00+00:00"Prusinkiewicz, Przemyslaw"https://www.zbmath.org/authors/?q=ai:prusinkiewicz.przemyslaw"Shirmohammadi, Mitra"https://www.zbmath.org/authors/?q=ai:shirmohammadi.mitra"Samavati, Faramarz"https://www.zbmath.org/authors/?q=ai:samavati.faramarz-fSummary: We show that parametric context-sensitive L-systems with affine geometry interpretation provide a succinct description of some of the most fundamental algorithms of geometric modeling of curves. Examples include the Lane-Riesenfeld algorithm for generating B-splines, the de Casteljau algorithm for generating Bezier curves, and their extensions to rational curves. Our results generalize the previously reported geometric-modeling applications of L-systems, which were limited to subdivision curves.
For the entire collection see [Zbl 1392.68027].Test generation from event system abstractions to cover their states and transitions.https://www.zbmath.org/1455.681042021-03-30T15:24:00+00:00"Julliand, J."https://www.zbmath.org/authors/?q=ai:julliand.jacques"Kouchnarenko, O."https://www.zbmath.org/authors/?q=ai:kouchnarenko.olga"Masson, P. A."https://www.zbmath.org/authors/?q=ai:masson.pierre-alain"Voiron, G."https://www.zbmath.org/authors/?q=ai:voiron.gSummary: Model-based testing of event systems can take advantage of considering abstractions rather than explicit models, for controlling their size. When abstracting still a test has to be a concrete connected and reachable event sequence. This paper presents a test generation method based on computing a reachable and connected under-approximation of the abstraction of an event system. We compute the under-approximation with concrete instances of the abstract transitions, that cover all the states and transitions of the predicatebased abstraction. We propose an algorithmic method that instantiates each of the abstract transitions, and maintains for widening it a frontier of concretely reached states. We present heuristics to favour the instances connectivity. The idea is to prolong whenever possible the already reached sequences of concrete transitions, and to parameterize the order in which the states and actions occur. This concrete under-approximation ends up covering partially (at best totally) the reachable abstract transitions. The computed tests are paths of the under-approximation. The paper also reports on an implementation, which permits to provide experimental results confirming the interest of the approach with related heuristics.Multiparty symmetric sum types.https://www.zbmath.org/1455.681262021-03-30T15:24:00+00:00"Nielsen, Lasse"https://www.zbmath.org/authors/?q=ai:nielsen.lasse-r"Yoshida, Nobuko"https://www.zbmath.org/authors/?q=ai:yoshida.nobuko"Honda, Kohei"https://www.zbmath.org/authors/?q=ai:honda.koheiSummary: This paper introduces a new theory of multiparty session types based on symmetric sum types, by which we can type non-deterministic orchestration choice behaviours. While the original branching type in session types can represent a choice made by a single participant and accepted by others determining how the session proceeds, the symmetric sum type represents a choice made by agreement among all the participants of a session. Such behaviour can be found in many practical systems, including collaborative workflow in healthcare systems for clinical practice guidelines (CPGs). Processes using the symmetric sums can be embedded into the original branching types using conductor processes. We show that this type-driven embedding preserves typability, satisfies semantic soundness and completeness, and meets the encodability criteria adapted to the typed setting. The theory leads to an efficient implementation of a prototypical tool for CPGs which automatically translates the original CPG specifications from a representation called the Process Matrix to symmetric sum types, type checks programs and executes them.
For the entire collection see [Zbl 1415.68027].Robustness of equations under operational extensions.https://www.zbmath.org/1455.681252021-03-30T15:24:00+00:00"Mosses, Peter D."https://www.zbmath.org/authors/?q=ai:mosses.peter-d"Mousavi, Mohammadreza"https://www.zbmath.org/authors/?q=ai:mousavi.mohammadreza"Reniers, Michel A."https://www.zbmath.org/authors/?q=ai:reniers.michel-adriaanSummary: Sound behavioral equations on open terms may become unsound after conservative extensions of the underlying operational semantics. Providing criteria under which such equations are preserved is extremely useful; in particular, it can avoid the need to repeat proofs when extending the specified language.
This paper investigates preservation of sound equations for several notions of bisimilarity on open terms: closed-instance (ci-)bisimilarity and formal-hypothesis (fh-)bisimilarity, both due to Robert de Simone, and hypothesis-preserving (hp-)bisimilarity, due to Arend Rensink. For both fh-bisimilarity and hp-bisimilarity, we prove that arbitrary sound equations on open terms are preserved by all disjoint extensions which do not add labels. We also define slight variations of fh- and hp-bisimilarity such that all sound equations are preserved by arbitrary disjoint extensions. Finally, we give two sets of syntactic criteria (on equations, resp. operational extensions) and prove each of them to be sufficient for preserving ci-bisimilarity.
For the entire collection see [Zbl 1415.68027].Models for CSP with availability information.https://www.zbmath.org/1455.681242021-03-30T15:24:00+00:00"Lowe, Gavin"https://www.zbmath.org/authors/?q=ai:lowe.gavinSummary: We consider models of CSP based on recording what events are available as possible alternatives to the events that are actually performed. We present many different varieties of such models. For each, we give a compositional semantics, congruent to the operational semantics, and prove full abstraction and no-junk results. We compare the expressiveness of the different models.
For the entire collection see [Zbl 1415.68027].A process calculus for expressing finite place/transition Petri nets.https://www.zbmath.org/1455.681222021-03-30T15:24:00+00:00"Gorrieri, Roberto"https://www.zbmath.org/authors/?q=ai:gorrieri.roberto"Versari, Cristian"https://www.zbmath.org/authors/?q=ai:versari.cristianSummary: We introduce the process calculus Multi-CCS, which extends conservatively CCS with an operator of strong prefixing able to model atomic sequences of actions as well as multiparty synchronization. Multi-CCS is equipped with a labeled transition system semantics, which makes use of a minimal structural congruence. Multi-CCS is also equipped with an unsafe P/T Petri net semantics by means of a novel technique. This is the first rich process calculus, including CCS as a subcalculus, which receives a semantics in terms of unsafe, labeled P/T nets. The main result of the paper is that a class of Multi-CCS processes, called finite-net processes, is able to represent all finite (reduced) P/T nets.
For the entire collection see [Zbl 1415.68027].Relating timed and register automata.https://www.zbmath.org/1455.680892021-03-30T15:24:00+00:00"Figueira, Diego"https://www.zbmath.org/authors/?q=ai:figueira.diego"Hofman, Piotr"https://www.zbmath.org/authors/?q=ai:hofman.piotr"Lasota, Sławomir"https://www.zbmath.org/authors/?q=ai:lasota.slawomirSummary: Timed automata and register automata are well-known models of computation over timed and data words respectively. The former has clocks that allow to test the lapse of time between two events, whilst the latter includes registers that can store data values for later comparison. Although these two models behave in appearance differently, several decision problems have the same (un)decidability and complexity results for both models. As a prominent example, emptiness is decidable for alternating automata with one clock or register, both with non-primitive recursive complexity. This is not by chance.
This work confirms that there is indeed a tight relationship between the two models. We show that a run of a timed automaton can be simulated by a register automaton, and conversely that a run of a register automaton can be simulated by a timed automaton. Our results allow to transfer complexity and decidability results back and forth between these two kinds of models. We justify the usefulness of these reductions by obtaining new results on register automata.
For the entire collection see [Zbl 1415.68027].Light logics and higher-order processes.https://www.zbmath.org/1455.681212021-03-30T15:24:00+00:00"Dal Lago, Ugo"https://www.zbmath.org/authors/?q=ai:dal-lago.ugo"Martini, Simone"https://www.zbmath.org/authors/?q=ai:martini.simone"Sangiorgi, Davide"https://www.zbmath.org/authors/?q=ai:sangiorgi.davideSummary: We show that the techniques for resource control that have been developed in the so-called ``light logics'' can be fruitfully applied also to process algebras. In particular, we present a restriction of Higher-Order \(\pi\)-calculus inspired by Soft Linear Logic. We prove that any soft process terminates in polynomial time. We argue that the class of soft processes may be naturally enlarged so that interesting processes are expressible, still maintaining the polynomial bound on executions.
For the entire collection see [Zbl 1415.68027].Process behaviour: formulae vs. tests (extended abstract).https://www.zbmath.org/1455.681202021-03-30T15:24:00+00:00"Cerone, Andrea"https://www.zbmath.org/authors/?q=ai:cerone.andrea"Hennessy, Matthew"https://www.zbmath.org/authors/?q=ai:hennessy.matthew-gSummary: Process behaviour is often defined either in terms of the tests they satisfy, or in terms of the logical properties they enjoy. Here we compare these two approaches, using extensional testing in the style of DeNicola, Hennessy, and a recursive version of the property logic HML.
We first characterise subsets of this property logic which can be captured by tests. Then we show that those subsets of the property logic capture precisely the power of tests.
For the entire collection see [Zbl 1415.68027].A criterion for separating process calculi.https://www.zbmath.org/1455.681172021-03-30T15:24:00+00:00"Banti, Federico"https://www.zbmath.org/authors/?q=ai:banti.federico"Pugliese, Rosario"https://www.zbmath.org/authors/?q=ai:pugliese.rosario"Tiezzi, Francesco"https://www.zbmath.org/authors/?q=ai:tiezzi.francescoSummary: We introduce a new criterion, replacement freeness, to discern the relative expressiveness of process calculi. Intuitively, a calculus is strongly replacement free if replacing, within an enclosing context, a process that cannot perform any visible action by an arbitrary process never inhibits the capability of the resulting process to perform a visible action. We prove that there exists no compositional and interaction sensitive encoding of a not strongly replacement free calculus into any strongly replacement free one. We then define a weaker version of replacement freeness, by only considering replacement of closed processes, and prove that, if we additionally require the encoding to preserve name independence, it is not even possible to encode a non replacement free calculus into a weakly replacement free one. As a consequence of our encodability results, we get that many calculi equipped with priority are not replacement free and hence are not encodable into mainstream calculi like CCS and \(\pi\)-calculus, that instead are strongly replacement free. We also prove that variants of \(\pi\)-calculus with match among names, pattern matching or polyadic synchronization are only weakly replacement free, hence they are separated both from process calculi with priority and from mainstream calculi.
For the entire collection see [Zbl 1415.68027].Expressiveness modulo bisimilarity of regular expressions with parallel composition (extended abstract).https://www.zbmath.org/1455.680832021-03-30T15:24:00+00:00"Baeten, Jos C. M."https://www.zbmath.org/authors/?q=ai:baeten.jos-c-m"Luttik, Bas"https://www.zbmath.org/authors/?q=ai:luttik.bas"Muller, Tim"https://www.zbmath.org/authors/?q=ai:muller.tim"van Tilburg, Paul"https://www.zbmath.org/authors/?q=ai:van-tilburg.paulSummary: The languages accepted by finite automata are precisely the languages denoted by regular expressions. In contrast, finite automata may exhibit behaviours that cannot be described by regular expressions up to bisimilarity. In this paper, we consider extensions of the theory of regular expressions with various forms of parallel composition and study the effect on expressiveness. First we prove that adding pure interleaving to the theory of regular expressions strictly increases its expressiveness up to bisimilarity. Then, we prove that replacing the operation for pure interleaving by ACP-style parallel composition gives a further increase in expressiveness. Finally, we prove that the theory of regular expressions with ACP-style parallel composition and encapsulation is expressive enough to express all finite automata up to bisimilarity. Our results extend the expressiveness results obtained by Bergstra, Bethke and Ponse for process algebras with (the binary variant of) Kleene's star operation.
For the entire collection see [Zbl 1415.68027].A linear programming approach to general dataflow process network verification and dimensioning.https://www.zbmath.org/1455.681292021-03-30T15:24:00+00:00"Sirdey, Renaud"https://www.zbmath.org/authors/?q=ai:sirdey.renaud"Aubry, Pascal"https://www.zbmath.org/authors/?q=ai:aubry.pascal-jSummary: In this paper, we present linear programming-based sufficient conditions, some of them polynomial-time, to establish the liveness and memory boundedness of general dataflow process networks. Furthermore, this approach can be used to obtain safe upper bounds on the size of the channel buffers of such a network.
For the entire collection see [Zbl 1420.68006].A theory of desynchronisable closed loop system.https://www.zbmath.org/1455.930052021-03-30T15:24:00+00:00"Beohar, Harsh"https://www.zbmath.org/authors/?q=ai:beohar.harsh"Cuijpers, Pieter"https://www.zbmath.org/authors/?q=ai:cuijpers.pieter-j-lSummary: The task of implementing a supervisory controller is non-trivial, even though different theories exist that allow automatic synthesis of these controllers in the form of automata. One of the reasons for this discord is due to the asynchronous interaction between a plant and its controller in implementations, whereas the existing supervisory control theories assume synchronous interaction. As a consequence the implementation suffer from the so-called inexact synchronisation problem. In this paper we address the issue of inexact synchronisation in a process algebraic setting, by solving a more general problem of refinement. We construct an asynchronous closed loop system by introducing a communication medium in a given synchronous closed loop system. Our goal is to find sufficient conditions under which a synchronous closed loop system is branching bisimilar to its corresponding asynchronous closed loop system.
For the entire collection see [Zbl 1420.68006].An introduction to time-constrained automata.https://www.zbmath.org/1455.680382021-03-30T15:24:00+00:00"Lemerre, Matthieu"https://www.zbmath.org/authors/?q=ai:lemerre.matthieu"David, Vincent"https://www.zbmath.org/authors/?q=ai:david.vincent-daniel"Aussaguès, Christophe"https://www.zbmath.org/authors/?q=ai:aussagues.christophe"Vidal-Naquet, Guy"https://www.zbmath.org/authors/?q=ai:vidal-naquet.guySummary: We present time-constrained automata (TCA), a model for hard real-time computation in which agents behaviors are modeled by automata and constrained by time intervals.
TCA actions can have multiple start time and deadlines, can be aperiodic, and are selected dynamically following a graph, the time-constrained automaton. This allows expressing much more precise time constraints than classical periodic or sporadic model, while preserving the ease of scheduling and analysis.
We provide some properties of this model as well as their scheduling semantics. We show that TCA can be automatically derived from source-code, and optimally scheduled on single processors using a variant of EDF. We explain how time constraints can be used to guarantee communication determinism by construction, and to study when possible agent interactions happen.
For the entire collection see [Zbl 1420.68006].Static vs dynamic SAGAs.https://www.zbmath.org/1455.681232021-03-30T15:24:00+00:00"Lanese, Ivan"https://www.zbmath.org/authors/?q=ai:lanese.ivanSummary: SAGAs calculi (or simply SAGAs) have been proposed by Bruni et al. as a model for long-running transactions. The approach therein can be considered static, while a dynamic approach has been proposed by Lanese and Zavattaro. In this paper we first extend both static SAGAs (in the centralized interruption policy) and dynamic SAGAs to deal with nesting, then we compare the two approaches.
For the entire collection see [Zbl 1420.68006].A graphical approach to progress for structured communication in web services.https://www.zbmath.org/1455.681192021-03-30T15:24:00+00:00"Carbone, Marco"https://www.zbmath.org/authors/?q=ai:carbone.marco"Debois, Søren"https://www.zbmath.org/authors/?q=ai:debois.sorenSummary: We investigate a graphical representation of session invocation interdependency in order to prove progress for the \(\pi\)-calculus with sessions under the usual session typing discipline. We show that those processes whose associated dependency graph is acyclic can be brought to reduce. We call such processes transparent processes. Additionally, we prove that for well-typed processes where services contain no free names, such acyclicity is preserved by the reduction semantics.
Our results encompass programs (processes containing neither free nor restricted session channels) and higher-order sessions (delegation). Furthermore, we give examples suggesting that transparent processes constitute a large enough class of processes with progress to have applications in modern session-based programming languages for web services.
For the entire collection see [Zbl 1420.68006].Port protocols for deadlock-freedom of component systems.https://www.zbmath.org/1455.681052021-03-30T15:24:00+00:00"Lambertz, Christian"https://www.zbmath.org/authors/?q=ai:lambertz.christian"Majster-Cederbaum, Mila"https://www.zbmath.org/authors/?q=ai:majster-cederbaum.mila-eSummary: In component-based development, approaches for property verification exist that avoid building the global system behavior of the component model. Typically, these approaches rely on the analysis of the local behavior of fixed sized subsystems of components. In our approach, we want to avoid not only the analysis of the global behavior but also of the local behaviors of the components. Instead, we consider very small parts of the local behaviors called port protocols that suffice to verify properties.
For the entire collection see [Zbl 1420.68006].Resumptions, weak bisimilarity and big-step semantics for While with interactive I/O: an exercise in mixed induction-coinduction.https://www.zbmath.org/1455.681002021-03-30T15:24:00+00:00"Nakata, Keiko"https://www.zbmath.org/authors/?q=ai:nakata.keiko"Uustalu, Tarmo"https://www.zbmath.org/authors/?q=ai:uustalu.tarmoSummary: We look at the operational semantics of languages with interactive I/O through the glasses of constructive type theory. Following on from our earlier work on coinductive trace-based semantics for While, we define several big-step semantics for While with interactive I/O, based on resumptions and termination-sensitive weak bisimilarity. These require nesting inductive definitions in coinductive definitions, which is interesting both mathematically and from the point-of-view of implementation in a proof assistant.
After first defining a basic semantics of statements in terms of resumptions with explicit internal actions (delays), we introduce a semantics in terms of delay-free resumptions that essentially removes finite sequences of delays on the fly from those resumptions that are responsive. Finally, we also look at a semantics in terms of delay-free resumptions supplemented with a silent divergence option. This semantics hinges on decisions between convergence and divergence and is only equivalent to the basic one classically. We have fully formalized our development in Coq.
For the entire collection see [Zbl 1392.68008].Hierarchical states in the compositional interchange format.https://www.zbmath.org/1455.680972021-03-30T15:24:00+00:00"Beohar, H."https://www.zbmath.org/authors/?q=ai:beohar.harsh"Nadales Agut, D. E."https://www.zbmath.org/authors/?q=ai:nadales-agut.d-e"van Beek, D. A."https://www.zbmath.org/authors/?q=ai:van-beek.d-a"Cuijpers, P. J. L."https://www.zbmath.org/authors/?q=ai:cuijpers.pieter-j-lSummary: CIF is a language designed for two purposes, namely as a specification language for hybrid systems and as an interchange format for allowing model transformations between other languages for hybrid systems. To facilitate the top-down development of a hybrid system and also to be able to express models more succinctly in the CIF formalism, we need a mechanism for stepwise refinement. In this paper, we add the notion of hierarchy to a subset of the CIF language, which we call hCIF\(^{\subset}\). The semantic domain of the CIF formalism is a hybrid transition system, constructed using structural operational semantics. The goal of this paper is to present a semantics for hierarchy in such a way that only the SOS rules for atomic entities in hCIF\(^{\subset}\) are redesigned in comparison to CIF. Furthermore, to be able to reuse existing tools like simulators of the CIF language, a procedure to eliminate hierarchy from an automaton is given.
For the entire collection see [Zbl 1392.68008].Structural decomposition of reactions of graph-like objects.https://www.zbmath.org/1455.680792021-03-30T15:24:00+00:00"Heindel, Tobias"https://www.zbmath.org/authors/?q=ai:heindel.tobiasSummary: Inspired by decomposition problems in rule-based formalisms in Computational Systems Biology and recent work on compositionality in graph transformation, this paper proposes to use arbitrary colimits to ``deconstruct'' models of reactions in which states are represented as objects of adhesive categories. The fundamental problem is the decomposition of complex reactions of large states into simpler reactions of smaller states.
The paper defines the local decomposition problem for transformations. To solve this problem means to ``reconstruct'' a given transformation as the colimit of ``smaller'' ones where the shape of the colimit and the decomposition of the source object of the transformation are fixed in advance. The first result is the soundness of colimit decomposition for arbitrary double pushout transformations in any category, which roughly means that several ``local'' transformations can be combined into a single ``global'' one. Moreover, a solution for a certain class of local decomposition problems is given, which generalizes and clarifies recent work on compositionality in graph transformation.
For the entire collection see [Zbl 1392.68008].Congruence from the operator's point of view: compositionality requirements on process semantics.https://www.zbmath.org/1455.680992021-03-30T15:24:00+00:00"Gazda, Maciej"https://www.zbmath.org/authors/?q=ai:gazda.maciej-w"Fokkink, Wan"https://www.zbmath.org/authors/?q=au:Fokkink, WanSummary: One of the basic sanity properties of a behavioural semantics is that it constitutes a congruence with respect to standard process operators. This issue has been traditionally addressed by the development of rule formats for transition system specifications that define process algebras. In this paper we suggest a novel, orthogonal approach. Namely, we focus on a number of process operators, and for each of them attempt to find the widest possible class of congruences. To this end, we impose restrictions on sublanguages of Hennessy-Milner logic, so that a semantics whose modal characterization satisfies a given criterion is guaranteed to be a congruence with respect to the operator in question. We investigate action prefix, alternative composition, two restriction operators, and parallel composition.
For the entire collection see [Zbl 1392.68008].Equational characterization of covariant-contravariant simulation and conformance simulation semantics.https://www.zbmath.org/1455.680982021-03-30T15:24:00+00:00"Fábregas, Ignacio"https://www.zbmath.org/authors/?q=ai:fabregas.ignacio"de Frutos-Escrig, David"https://www.zbmath.org/authors/?q=ai:de-frutos-escrig.david"Palomino, Miguel"https://www.zbmath.org/authors/?q=ai:palomino.miguelSummary: Covariant-contravariant simulation and conformance simulation generalize plain simulation and try to capture the fact that it is not always the case that ``the larger the number of behaviors, the better''. We have previously studied their logical characterizations and in this paper we present the axiomatizations of the preorders defined by the new simulation relations and their induced equivalences. The interest of our results lies in the fact that the axiomatizations help us to know the new simulations better, understanding in particular the role of the contravariant characteristics and their interplay with the covariant ones; moreover, the axiomatizations provide us with a powerful tool to (algebraically) prove results of the corresponding semantics. But we also consider our results interesting from a metatheoretical point of view: the fact that the covariant-contravariant simulation equivalence is indeed ground axiomatizable when there is no action that exhibits both a covariant and a contravariant behaviour, but becomes non-axiomatizable whenever we have together actions of that kind and either covariant or contravariant actions, offers us a new subtle example of the narrow border separating axiomatizable and non-axiomatizable semantics. We expect that by studying these examples we will be able to develop a general theory separating axiomatizable and non-axiomatizable semantics.
For the entire collection see [Zbl 1392.68008].Achieving better security using nonlinear cellular automata as a cryptographic primitive.https://www.zbmath.org/1455.681122021-03-30T15:24:00+00:00"Maiti, Swapan"https://www.zbmath.org/authors/?q=ai:maiti.swapan"Chowdhury, Dipanwita Roy"https://www.zbmath.org/authors/?q=ai:chowdhury.dipanwita-roySummary: Nonlinear functions are essential in different crypto-primitives as they play an important role on the security of a cipher design. Wolfram identified Rule 30 as a powerful nonlinear function for cryptographic applications. However, Meier and Staffelbach mounted an attack (MS attack) against Rule 30 Cellular Automata (CA). MS attack is a real threat on a CA based system. Nonlinear rules as well as maximum period CA increase randomness property. In this work, nonlinear rules of maximum period nonlinear hybrid CA (M-NHCA) are studied and it is shown to be a better crypto-primitive than Rule 30 CA. It has also been analysed that the M-NHCA with single nonlinearity injection proposed in the literature is vulnerable against MS attack, whereas M-NHCA with multiple nonlinearity injections provide better cryptographic primitives and they are also secure against MS attack.
For the entire collection see [Zbl 1411.65006].Exploration of carrier-based time-varying networks: the power of waiting.https://www.zbmath.org/1455.681412021-03-30T15:24:00+00:00"Ilcinkas, David"https://www.zbmath.org/authors/?q=ai:ilcinkas.david"Wade, Ahmed M."https://www.zbmath.org/authors/?q=ai:wade.ahmed-mouhamadouSummary: We study the problem of exploration by a mobile entity (agent) of a class of highly dynamic networks, namely the carrier graphs (the C-graphs, modeling public transportation systems, among others). These are defined by a set of carriers following infinitely their prescribed route along the stations of the network.
\textit{P. Flocchini} et al. [Theor. Comput. Sci. 469, 53--68 (2013; Zbl 1258.68103)]
studied this problem in the case when the agent must always travel on the carriers and thus cannot wait on a station. They described the necessary and sufficient conditions for the problem to be solvable and proved that the optimal worst-case number of time units (and thus of moves) to explore a \(n\)-node C-graph of \(k\) carriers and maximal period \(p\) is in \(\Theta(k p^2)\) in the general case.
In this paper, we study the impact of the ability to wait at the stations. We exhibit the necessary and sufficient conditions for the problem to be solvable in this context, and we prove that waiting at the stations allows the agent to reduce the optimal worst-case number of moves by a multiplicative factor of at least \(\Theta(p)\), while the worst-case time complexity is reduced to \(\Theta(np)\). (In any connected carrier graph, we have \(n \leq kp\).) We also show some complementary optimal results in specific cases (same period for all carriers, highly connected C-graphs). Finally this new ability allows the agent to completely map the C-graph, in addition to just exploring it.Micro- and macroscopic modeling of crowding and pushing in corridors.https://www.zbmath.org/1455.911752021-03-30T15:24:00+00:00"Fischer, Michael"https://www.zbmath.org/authors/?q=ai:fischer.michael-j"Jankowiak, Gaspard"https://www.zbmath.org/authors/?q=ai:jankowiak.gaspard"Wolfram, Marie-Therese"https://www.zbmath.org/authors/?q=ai:wolfram.marie-thereseSummary: Experiments with pedestrians revealed that the geometry of the domain, as well as the incentive of pedestrians to reach a target as fast as possible have a strong influence on the overall dynamics. In this paper, we propose and validate different mathematical models at the micro- and macroscopic levels to study the influence of both effects. We calibrate the models with experimental data and compare the results at the micro- as well as macroscopic levels. Our numerical simulations reproduce qualitative experimental features on both levels, and indicate how geometry and motivation level influence the observed pedestrian density. Furthermore, we discuss the dynamics of solutions for different modeling approaches and comment on the analysis of the respective equations.Bubble-flip -- a new generation algorithm for prefix normal words.https://www.zbmath.org/1455.682912021-03-30T15:24:00+00:00"Cicalese, Ferdinando"https://www.zbmath.org/authors/?q=ai:cicalese.ferdinando"Lipták, Zsuzsanna"https://www.zbmath.org/authors/?q=ai:liptak.zsuzsanna"Rossi, Massimiliano"https://www.zbmath.org/authors/?q=ai:rossi.massimilianoSummary: We present a new recursive generation algorithm for prefix normal words. These are binary words with the property that no factor has more 1s than the prefix of the same length. The new algorithm uses two operations on binary words, which exploit certain properties of prefix normal words in a smart way. We introduce infinite prefix normal words and show that one of the operations used by the algorithm, if applied repeatedly to extend the word, produces an ultimately periodic infinite word, which is prefix normal and whose period's length and density we can predict from the original word.
For the entire collection see [Zbl 1386.68008].