Search

We study the expressive power of polynomial recursive sequences, a nonlinear extension of the well-known class of linear recursive sequences. These sequences arise naturally in the study of nonlinear extensions of weighted automata, where (non)expressiveness results translate to class separations. A typical example of a polynomial recursive sequence is bn = n!. Our main result is that the sequence un = nn is not polynomial recursive. [ABSTRACT FROM AUTHOR]

In Entities and Indices, M. J. Cresswell argued that a first-order modal language can reach the expressive power of natural-language modal discourse only if we give to the formal language a semantics with indices containing infinite possible worlds and we add to it an infinite collection of operators actually n and R e f n which store and retrieve worlds. In the fourth chapter of the book, Cresswell gave a proof that the resulting intensional language, which he called L ∗ , is as expressive as an extensional variant of it, called L , which has full quantification over worlds. In both linguistics and philosophy, Cresswell's book has been viewed as offering a compelling argument for preferring extensional systems in the study of natural language. In this paper, after providing a model-theoretic definition of the relation being as expressive as that can be applied to Cresswell's languages L and L ∗ , we show that the intensional language L ∗ is not as expressive as the extensional language L . This result, we claim, undermines Cresswell's argument to the effect that English modal discourse has the power of explicit quantification over worlds. Additionally, we show that L ∗ does become as expressive as L when we add Cresswell's operator of universal modality □ to L ∗ , which provides an extra amount of expressive power. Recently, I. Yanovich has advocated a view that is similar to ours in important respects. At the end of the paper we offer a short discussion of his formalism. [ABSTRACT FROM AUTHOR]

In 1912 Antoine Meillet published a paper, L’évolution des forms grammaticales, that turned out to be one of the most inspiring contributions in the entire history of linguistics. In the present paper it is suggested that some of the ideas in Meillet’s article were probably stimulated by a letter unpublished so far that was sent to him by Ernesto Rignano, one of the co-editors of Scientia. the journal in which the article was published. The present paper is divided into two parts: in the first, Meillet’s paper will be analysed carefully and the conceptually relevant points will be highlighted, whereas in the second part the text of Rignano’s letter will be briefly commented on, stressing the points that could have stimulated some of Meillet’s reflections on grammaticalization.

The logic of information flows (LIF) is a general framework in which tasks of a procedural nature can be modeled in a declarative, logic-based fashion. The first contribution of this article is to propose semantic and syntactic definitions of inputs and outputs of LIF expressions. We study how the two relate and show that our syntactic definition is optimal in a sense that is made precise. The second contribution is a systematic study of the expressive power of sequential composition in LIF. Our results on composition tie in the results on inputs and outputs and relate LIF to first-order logic (FO) and bounded-variable LIF to boundedvariable FO. This article is the extended version of a paper presented at KR 2020 [2]. [ABSTRACT FROM AUTHOR]

The article looks at the phenomenon of the rediscovery of Irène Némirovsky through the eyes of a particular reader: a journalist-researcher responsible for presenting, in the pages of the Italian daily with which she collaborated, all of Irène's novels published after Suite française, which triggered the series of publishing revivals. In the first part, the article recounts the meetings with the writer's two daughters, twenty years apart, for interviews about their mother and her work. The second part presents some of the features of Irène Némirovsky's novels that made it possible to write these accounts from a journalist's point of view, each time choosing an element that becomes the specific mark of a constant expressive power.

The development of a satisfying and rigorous mathematical understanding of the performance of neural networks is a major challenge in artificial intelligence. Against this background, we study the expressive power of neural networks through the example of the classical NP-hard knapsack problem. Our main contribution is a class of recurrent neural networks (RNNs) with rectified linear units that are iteratively applied to each item of a knapsack instance and thereby compute optimal or provably good solution values. We show that an RNN of depth four and width depending quadratically on the profit of an optimum knapsack solution is sufficient to find optimum knapsack solutions. We also prove the following tradeoff between the size of an RNN and the quality of the computed knapsack solution: for knapsack instances consisting of n items, an RNN of depth five and width w computes a solution of value at least 1 − O (n 2 / w) times the optimum solution value. Our results build on a classical dynamic programming formulation of the knapsack problem and a careful rounding of profit values that are also at the core of the well-known fully polynomial-time approximation scheme for the knapsack problem. A carefully conducted computational study qualitatively supports our theoretical size bounds. Finally, we point out that our results can be generalized to many other combinatorial optimization problems that admit dynamic programming solution methods, such as various shortest path problems, the longest common subsequence problem, and the traveling salesperson problem. History: Andrea Lodi, Area Editor for Design & Analysis of Algorithms–Discrete. An extended abstract of this article, including Figures 1–7, appeared in the Proceedings of the AAAI Conference on Artificial Intelligence, vol. 35, 7685–7693 (Hertrich and Skutella 2021); see https://ojs.aaai.org/index.php/AAAI/article/view/16939; copyright © 2021, Association for the Advancement of Artificial Intelligence. Funding: This work was supported by the Deutsche Forschungsgemeinschaft [Grants DFG-GRK 2434 and EXC-2046/1, Project 390685689] and the H2020 European Research Council [ScaleOpt-757481]. [ABSTRACT FROM AUTHOR]

This paper examines two alleged limitations in the use of formal languages: on the one hand, the trade-offs between expressive and inferential power, and on the other, the phenomenon of system imprisonment. After reconceptualizing the issue, we consider the role played by modality in the understanding of certain aspects of mathematical structures, and argue for its centrality. [ABSTRACT FROM AUTHOR]

In this paper, we introduce a variant of second-order propositional modal logic interpreted on general (or Henkin) frames, S O P M L H , and present a decidable fragment of this logic, S O P M L dec H , that preserves important expressive capabilities of S O P M L H . S O P M L dec H is defined as a modal loosely guarded fragment of S O P M L H . We demonstrate the expressive power of S O P M L dec H using examples in which modal operators obtain (a) the epistemic interpretation, (b) the dynamic interpretation. S O P M L dec H partially satisfies the principle of non-Fregean logic: two different atomic propositions with the same truth value can have different contents. In S O P M L dec H , we also define relating connectives and show that the weak Boethius' Thesis built using these connectives is a valid formula of S O P M L dec H . [ABSTRACT FROM AUTHOR]

We build and study dynamic versions of epistemic logic. We study languages parameterized by an action signature that allows one to express epistemic actions such as (truthful) public announcements, completely private announcements to groups of agents, and more. The language L (Σ) is modeled on dynamic logic. Its sentence-building operations include modalities for the execution of programs, and for knowledge and common knowledge. Its program-building operations include action execution, composition, repetition, and choice. We consider two fragments of L (Σ) . In L 1 (Σ) , we drop action repetition; in L 0 (Σ) , we also drop common knowledge. We present the syntax and semantics of these languages and sound proof systems for the validities in them. We prove the strong completeness of a logical system for L 0 (Σ) and the weak completeness of one for L 1 (Σ) . We show the finite model property and, hence, decidability of L 1 (Σ) . We translate L 1 (Σ) into PDL, obtaining a second proof of decidability. We prove results on expressive power, comparing L 1 (Σ) with modal logic together with transitive closure operators. We prove that a logical language with operators for private announcements is more expressive than one for public announcements. [ABSTRACT FROM AUTHOR]

Chinese painting is full of poetic, expressive power and rhythm, which is different from Western painting and could be unique in global art history and research. The poetic, expressive power and rhythm in Chinese painting have been unique in the global art world. Therefore, it should be evaluated correctly, thoroughly and accurately but not be included only as an example in the dominant Western art world. Doing comparisons between Chinese painting and Western painting is supposed to compare them with one another equally. Learning about the Chinese language and culture is also quite significant when studying Chinese painting to get to know it deeply enough and profoundly. [ABSTRACT FROM AUTHOR]

We study the expressivity and complexity of two modal logics interpreted on finite forests and equipped with standard modalities to reason on submodels. The logic ML(|) extends the modal logic K with the composition operator from ambient logicwhereasML(*) features the separating conjunction * from separation logic. Both operators are second-order in nature. We show that ML(|) is as expressive as the graded modal logic GML (on trees) whereas ML(*) is strictly less expressive than GML. Moreover, we establish that the satisfiability problem is Tower-complete for ML(*), whereas it is (only) AExpPol-complete for ML(|), a result that is surprising given their relative expressivity. As by-products, we solve open problems related to sister logics such as static ambient logic and modal separation logic. [ABSTRACT FROM AUTHOR]

The expressive power of logics is one of the major research topics in mathematical logic and computer science. One way of comparing the complexities of different formalisms (e.g. knowledge representation formalisms) stems from the perspective of representational succinctness. The concept of covariant–contravariant refinement (CC-refinement, for short) generalizes the concepts of refinement, simulation and bisimulation. We introduce an extension of the standard multi-agent modal μ -calculus system K μ with CC-refinement operators ( CCRML μ ) and show that CCRML μ is equivalently expressive to K μ . This paper presents the succinctness results of CCRML μ compared with K μ from two viewpoints based on the sets of covariant and contravariant actions. We establish a family of CC-refinement formulas for comparing the succinctness based on the well-known parity symmetric alternating automata, which is often used to describe modal μ -calculus formulas. [ABSTRACT FROM AUTHOR]

The most representative interval temporal logic, called HS, was introduced by Halpern and Shoham in the nineties. Recently, HS has been proposed as a suitable formalism for modern artificial intelligence applications; however, when dealing with real-life data one is not always able to express temporal relations and propositional labels in a definite, crisp way. In this paper, following the seminal ideas of Fitting and Zadeh, we present a fuzzy generalization of HS, called FHS, that partially solves such problems of expressive power. We study FHS from both a theoretical and an application standpoint: first, we discuss its syntax, semantics, expressive power, and satisfiability problem; then, we define and solve the time series FHS finite model checking problem, to serve as the basis of future applications. [ABSTRACT FROM AUTHOR]

Deep neural networks have achieved great success in solving many machine learning and computer vision problems. In this paper, we propose a deep neural network called the Tucker network derived from the Tucker format and analyze its expressive power. The results demonstrate that the Tucker network has exponentially higher expressive power than the shallow network. In other words, a shallow network with an exponential width is required to realize the same score function as that computed by the Tucker network. Moreover, we discuss the expressive power between the hierarchical Tucker tensor network (HT network) and the proposed Tucker network. To generalize the Tucker network into a deep version, we combine the hierarchical Tucker format and Tucker format to propose a deep Tucker tensor decomposition. Its corresponding deep Tucker network is presented. Experiments are conducted on three datasets: MNIST, CIFAR-10 and CIFAR-100. The results experimentally validate the theoretical results and show that the Tucker network and deep Tucker network have better performance than the shallow network and HT network. [ABSTRACT FROM AUTHOR]

Population protocols are a model of distributed computation intended for the study of networks of independent computing agents with dynamic communication structure. Each agent has a finite number of states, and communication occurs nondeterministically, allowing the involved agents to change their states based on each other's states. In the present paper we study unreliable models based on population protocols and their variations from the point of view of expressive power. We model the effects of message loss. We show that for a general definition of protocols with unreliable communication with constant-storage agents such protocols can only compute predicates computable by immediate observation (IO) population protocols (sometimes also called one-way protocols). Immediate observation population protocols are inherently tolerant to unreliable communication and keep their expressive power under a wide range of fairness conditions. We also prove that a large class of message-based models that are generally more expressive than IO becomes strictly less expressive than IO in the unreliable case. • Population protocols lose expressive power when transactions are non-atomic. • Same expressive power as one-way communication population protocols even for extensions. • Message-based population protocols become strictly weaker instead of strictly stronger than one-way communication protocols. [ABSTRACT FROM AUTHOR]

We study capacitated automata (CAs) [10], where transitions correspond to resources and have capacities, bounding the number of times they may be traversed. We follow the utilization semantics of CAs and view them as recognizers of multi-languages - sets of multisets of words, where a multiset S of words is in the multi-language of a CA A if all the words in S can be mutually accepted by A: the multiset of runs on all the words in S together respects the bounds induced by the capacities. Thus, capacitated automata model possible utilizations of systems with bounded resources. We study the basic properties of CAs: their expressive power in the non-deterministic and deterministic models, closure under classical operations, and the complexity of basic decision problems. [ABSTRACT FROM AUTHOR]

Bisimulations are a key notion to study the expressive power of a modal language. This paper studies the expressivity of Game Description Language (GDL) and its epistemic extension Epistemic GDL (EGDL) through a bisimulation approach. We first define a notion of bisimulation for GDL and prove that it coincides with the indistinguishability of GDL formulas. Based on it, we establish a characterization of the definability of GDL in terms of |$k$| -bisimulations. Then we design novel notions of bisimulation for EGDL and obtain characterizations of the expressive power of EGDL in terms of them. These characterizations provide a powerful tool to identify the expressive power of game description languages. Finally, we demonstrate with real games that bisimulation can be generalized to capture a wide range of game equivalence. [ABSTRACT FROM AUTHOR]

Nondeterminism models an ability to see the future: An automaton with an infinite look ahead can successfully resolve its nondeterministic choices. An automaton is history deterministic (HD) if it can successfully resolve its nondeterministic choices in a way that only depends on the past. Formally, an HD automaton has a strategy that maps each finite word to the transition to be taken after the word is read and following this strategy results in accepting all the words in the language of the automaton. Beyond being theoretically interesting and intriguing, HD automata can replace deterministic automata in several applications, most notably reactive synthesis, and they attract a lot of interest in the research community. The survey describes the development of HD ω-regular automata, relates history determinism to other types of bounded nondeterminism, studies the determinization of HD automata and their succinctness with respect to deterministic ones, and discusses variants, extensions, and open problems around HD automata.

We study the expressive power of the Lara language – a recently proposed unified model for expressing relational and linear algebra operations – both in terms of traditional database query languages and some analytic tasks often performed in machine learning pipelines. Since Lara is parameterized by a set of user-defined functions which allow to transform values in tables, known as extension functions , the exact expressive power of the language depends on how these functions are defined. We start by showing Lara to be expressive complete with respect to a syntactic fragment of relational algebra with aggregation (under the mild assumption that extension functions in Lara can cope with traditional relational algebra operations such as selection and renaming). We then look further into the expressiveness of Lara based on different classes of extension functions, and distinguish two main cases depending on the level of genericity that queries are enforced to satisfy. Under strong genericity assumptions the language cannot express matrix convolution, a very important operation in current machine learning pipelines. This language is also local, and thus cannot express operations such as matrix inverse that exhibit a recursive behavior. For expressing convolution, one can relax the genericity requirement by adding an underlying linear order on the domain. This, however, destroys locality and turns the expressive power of the language much more difficult to understand. In particular, although under complexity assumptions some versions of the resulting language can still not express matrix inverse, a proof of this fact without such assumptions seems challenging to obtain. [ABSTRACT FROM AUTHOR]

The automation of decision procedures makes certification essential. We suggest to use determinacy of turn-based two-player games with regular winning conditions in order to generate certificates for the number of states that a deterministic finite automaton (DFA) needs in order to recognize a given language. Given a language L and a bound k, recognizability of L by a DFA with k states is reduced to a game between Prover and Refuter. The interaction along the game then serves as a certificate. A certificate generated by Prover consists of a DFA with at most k states. A certificate generated by Refuter consists of a faulty attempt to define the required DFA. We compare the length of offline certificates, which are generated with no interaction between Prover and Refuter, and online certificates, which are based on such an interaction, and are thus shorter. We show that our approach is useful also for certification of separability of regular languages by a DFA of a given size. Unlike DFA minimization, which can be solved in polynomial time, separation is NP-complete, and thus the certification approach is essential. In addition, we prove NP-completeness of a strict version of separation. [ABSTRACT FROM AUTHOR]

We study ReLU deep neural networks (DNNs) by investigating their connections with the hierarchical basis method in finite element methods. First, we show that the approximation schemes of ReLU DNNs for x 2 and xy are composition versions of the hierarchical basis approximation for these two functions. Based on this fact, we obtain a geometric interpretation and systematic proof for the approximation result of ReLU DNNs for polynomials, which plays an important role in a series of recent exponential approximation results of ReLU DNNs. Through our investigation of connections between ReLU DNNs and the hierarchical basis approximation for x 2 and xy , we show that ReLU DNNs with this special structure can be applied only to approximate quadratic functions. Furthermore, we obtain a concise representation to explicitly reproduce any linear finite element function on a two-dimensional uniform mesh by using ReLU DNNs with only two hidden layers. [ABSTRACT FROM AUTHOR]

This paper contributes to the philosophical accounts of generalisation in formal modelling by introducing a conceptual framework that allows for recognising generalisations that are epistemically beneficial in the sense of contributing to the truth of a model result or component. The framework is useful for modellers themselves because it is shown how to recognise different kinds of generalisation on the basis of changes in model descriptions. Since epistemically beneficial generalisations usually de-idealise the model, the paper proposes a reformulation of the well-known distinction between abstraction and idealisation. A reformulated notion of abstraction is needed because the extant accounts yield wrong judgments when model-modifications introduce implicit assumptions. [ABSTRACT FROM AUTHOR]

The priority of building hardware-oriented neural network models is growing steadily. The target goals for their development are the performance and energy efficiency of promising hardware-software solutions. Simultaneously, for different classes of computing architectures of the computer, the optimal neural network models will differ. The most interesting from a practical point of view are application-specific integrated circuits (ASICs), field-programmable gate arrays (FPGAs) and central processing units (CPUs). We have recently proposed a bipolar morphological network as a hardware-oriented model for these computer types, the computationally intensive parts of which use only maximum and addition. In this work, we present for the first time a theoretical assessment of the expressive power of a neural network consisting of BM neurons and show that it corresponds to the expressive power of the classical multilayer perceptron. In addition, we summarize the current results on the use of the bipolar morphological model in typical tasks of technical vision: image classification and semantic segmentation. We consider simple LeNet-5-like neural networks, as well as deeper ResNet and UNet architectures. We show that BM networks demonstrate accuracy that allows their practical use, with significantly higher performance in terms of a transistor budget for two (ASIC, FPGA) of the three architectures under consideration. The source code of the model and ResNet experiments are available at https://github.com/SmartEngines/bipolar-morphological-resnet.

We show that the matrix query language MATLANG corresponds to a natural fragment of the positive relational algebra on K-relations. The fragment is defined by introducing a composition operator and restricting K-relation arities to 2. We then proceed to show that MATLANG can express all matrix queries expressible in the positive relational algebra on K-relations, when intermediate arities are restricted to 3. Thus we offer an analogue, in a model with numerical data, to the situation in classical logic, where the algebra of binary relations is equivalent to first-order logic with three variables. [ABSTRACT FROM AUTHOR]

The world has evolved from being international to being global. Increasingly, global issues like climate change, migration, pandemics, trade, big data, and terrorism spill over borders drawn centuries ago as if they were no longer there. In this globalized world, however, people are still born and educated as citizens of particular nation states. Indeed, education is still used as one of the state's main tools for shaping citizen virtues and commitments. Political philosophers have acknowledged both the increasingly global nature of contemporary political problems and the power of education to shape citizens but have failed to recognize how the two are interconnected. In his book, Democratic Education in a Globalized World: A Normative Theory, Julian Culp seeks to rectify this double-sided failure by building a theory of and framework for educating people for democratic citizenship in a world of border-crossing issues. I outline how he seeks to overcome this problem, set out an analytical framework with which to engage with his account, and note some significant worries that arise from this analysis. In particular, I focus on a specific blindness from which Culp's account suffers, which makes it unable to detect wrongs that arise when the state fails to commit to fundamental normative principles. [ABSTRACT FROM AUTHOR]

Vadalog is a system for performing complex reasoning tasks such as those required in advanced knowledge graphs. The logical core of the underlying Vadalog language is the warded fragment of tuple-generating dependencies (TGDs). This formalism ensures tractable reasoning in data complexity, while a recent analysis focusing on a practical implementation led to the reasoning algorithm around which the Vadalog system is built. A fundamental question that has emerged in the context of Vadalog is whether we can limit the recursion allowed by wardedness in order to obtain a formalism that provides a convenient syntax for expressing useful recursive statements, and at the same time achieves space-efficiency. After analyzing several real-life examples of warded sets of TGDs provided by our industrial partners, as well as recent benchmarks, we observed that recursion is often used in a restricted way: the body of a TGD contains at most one atom whose predicate is mutually recursive with a predicate in the head. We show that this type of recursion, known as piece-wise linear in the Datalog literature, is the answer to our main question. We further show that piecewise linear recursion alone, without the wardedness condition, is not enough as it leads to undecidability. We also study the relative expressiveness of the query languages based on (piece-wise linear) warded sets of TGDs. Finally, we give preliminary experimental evidence for the practical effect of piece-wise linearity on Vadalog. [ABSTRACT FROM AUTHOR]

The world has evolved from being international to being global. Increasingly, global issues like climate change, migration, pandemics, trade, big data, and terrorism spill over borders drawn centuries ago as if they were no longer there. In this globalized world, however, people are still born and educated as citizens of particular nation states. Indeed, education is still used as one of the state's main tools for shaping citizen virtues and commitments. Political philosophers have acknowledged both the increasingly global nature of contemporary political problems and the power of education to shape citizens but have failed to recognize how the two are interconnected. In his book, Democratic Education in a Globalized World: A Normative Theory, Julian Culp seeks to rectify this double-sided failure by building a theory of and framework for educating people for democratic citizenship in a world of border-crossing issues. I outline how he seeks to overcome this problem, set out an analytical framework with which to engage with his account, and note some significant worries that arise from this analysis. In particular, I focus on a specific blindness from which Culp's account suffers, which makes it unable to detect wrongs that arise when the state fails to commit to fundamental normative principles.

We show that for neural network functions that have width less or equal to the input dimension all connected components of decision regions are unbounded. The result holds for continuous and strictly monotonic activation functions as well as for the ReLU activation function. This complements recent results on approximation capabilities by Hanin and Sellke (2017) and connectivity of decision regions by Nguyen et al. (2018) for such narrow neural networks. Our results are illustrated by means of numerical experiments. [ABSTRACT FROM AUTHOR]

Session types provide a flexible programming style for structuring interaction, and are used to guarantee a safe and consistent composition of distributed processes. Traditional session types include only one-directional input (external) and output (internal) guarded choices. This prevents the session-processes to explore the full expressive power of the π -calculus where mixed choice was proved more expressive. Recently Casal, Mordido, and Vasconcelos proposed binary session types with mixed choices (CMV +). Surprisingly, in spite of an inclusion of unrestricted channels with mixed choice, CMV + 's mixed choice is rather separate and not mixed. We prove this negative result using two methodologies (using either the leader election problem or a synchronisation pattern as distinguishing feature), showing that there exists no good encoding from the π -calculus into CMV + , preserving distribution. We then close their open problem on the encoding from CMV + into CMV (without mixed choice), proving its soundness. [ABSTRACT FROM AUTHOR]