Search

The author has recently introduced an abstract algebraic framework of analogical proportions within the general setting of universal algebra. This paper studies analogical proportions in the boolean domain consisting of two elements 0 and 1 within his framework. It turns out that our notion of boolean proportions coincides with two prominent models from the literature in different settings. This means that we can capture two separate modellings of boolean proportions within a single framework which is mathematically appealing and provides further evidence for the robustness and applicability of the general framework. [ABSTRACT FROM AUTHOR]

Baba is You is a 2019 indie puzzle game whose levels are two-dimensional grids of objects. This paper demonstrates how a universal Turing machine could be created as a custom level in the game if a specific in-game limit were to be removed. A player could perform any computation by playing this level, allowing infinitely many new and meaningful puzzles to be created. Furthermore, the construction is such that the level is won if and only if the Turing machine halts, proving perfect play of the game to be unattainable by any computer. The machine is found to be exponentially time-complex, and the paper concludes with a discussion of the practical feasibility of in-game computation. [ABSTRACT FROM AUTHOR]

We prove that ω-languages of (non-deterministic) Petri nets and ω-languages of (nondeterministic) Turing machines have the same topological complexity: the Borel and Wadge hierarchies of the class of ω-languages of (non-deterministic) Petri nets are equal to the Borel and Wadge hierarchies of the class of ω-languages of (non-deterministic) Turing machines. We also show that it is highly undecidable to determine the topological complexity of a Petri net ω-language. Moreover, we infer from the proofs of the above results that the equivalence and the inclusion problems for ω-languages of Petri nets are ∏ 2 1 -complete, hence also highly undecidable. Additionally, we show that the situation is quite the opposite when considering unambiguous Petri nets, which have the semantic property that at most one accepting run exists on every input. We provide a procedure of determinising them into deterministic Muller counter machines with counter copying. As a consequence, we entail that the ω-languages recognisable by unambiguous Petri nets are △ 3 0 sets. [ABSTRACT FROM AUTHOR]

We prove that one can construct various kinds of automata over finite words for which some elementary properties are actually independent from strong set theories like T n = : Z F C + "There exist (at least) n inaccessible cardinals", for integers n ≥ 0. In particular, we prove independence results for languages of finite words generated by context-free grammars, or accepted by 2-tape or 1-counter automata. Moreover we get some independence results for weighted automata and for some related finitely generated subsemigroups of the set ℤ 3 × 3 of 3-3 matrices with integer entries. Some of these latter results are independence results from the Peano axiomatic system PA. [ABSTRACT FROM AUTHOR]

The complexity of the model checking problem for various fragments of first-order logic (FO) has attracted much attention over the last two decades, in particular for the fragment induced by E and ^ and that induced by A, E, and ^, which are better known as the constraint satisfaction problem and the quantified constraint satisfaction problem, respectively. The former was conjectured to follow a dichotomy between P and NP-complete by Feder and Vardi [SIAM J. Comput., 28 (1998), pp. 57-104]. For the latter, there are several partial trichotomy results between P, NP-complete, and Pspace-complete, and Chen [Meditations on quantified constraint satisfaction, in Logic and Program Semantics, Springer, Heidelberg, 2012, pp. 35-49] ventured a conjecture regarding Pspace-completeness vs. membership in NP in the presence of constants. We give a comprehensive account of the whole field of the complexity of model checking similar syntactic fragments of FO. The above two fragments are in fact the only ones for which there is currently no known complexity classification. Indeed, we consider all other similar syntactic fragments of FO, induced by the presence or absence of quantifiers and connectives, and fully classify the complexities of the parameterization of the model-checking problem by a finite model D, that is, the expression complexities for certain finite D. Perhaps surprisingly, we show that for most of these fragments, "tractability" is witnessed by a generic solving algorithm which uses quantifier relativization. Our classification methodology relies on tailoring suitably the algebraic approach pioneered by Jeavons, Cohen, and Gyssens [J. ACM, 44 (1997), pp. 527-548] for the constraint satisfaction problem and by Börner et al. [Inform. and Comput., 207 (2009), pp. 923-944] for the quantified constraint satisfaction problem. Most fragments under consideration can be relatively easily classified, either directly or using Schaefer's dichotomy theorems for SAT and QSAT, with the notable exception of the positive equality-free fragment induced by E, A, ^, and V. This outstanding fragment can also be classified and enjoys a tetrachotomy: according to the model, the corresponding model checking problem is either tractable, NP-complete, co-NP-complete, or Pspace-complete. [ABSTRACT FROM AUTHOR]

Short-circuit evaluation denotes the semantics of propositional connectives in which the second argument is evaluated only if the first argument does not suffice to determine the value of the expression. Free short-circuit logic is the equational logic in which compound statements are evaluated from left to right, while atomic evaluations are not memorised throughout the evaluation, i.e. evaluations of distinct occurrences of an atom in a compound statement may yield different truth values. We provide a simple semantics for free short-circuit logic (SCL) and an independent axiomatisation. Finally, we discuss evaluation strategies, some other SCLs, and side effects. [ABSTRACT FROM AUTHOR]

Ordinary Kripke models are not reactive. When we evaluate (test/ measure) a formula A at a model m, the model does not react, respond or change while we evaluate. The model is static and unchanged. This paper studies Kripke models which react to the evaluation process and change themselves during the process. The additional device we add to Kripke semantics to make it reactive is to allow the accessibility relation to access itself. Thus the accessibility relation ${\cal R}$ of a reactive Kripke model contains not only pairs $(a, b) \in {\cal R}$ of possible worlds ( b is accessible to a, i.e., there is an accessibility arc from a to b) but also pairs of the form $(t, (a, b))\in {\cal R}$, meaning that the arc ( a, b) is accessible to t, or even connections of the form $((a,b), (c,d))\in {\cal R}$. This new kind of Kripke semantics allows us to characterise more axiomatic modal logics (with one modality $\square$) by a class of reactive frames. There are logics which cannot be characterised by ordinary frames but which can be characterised by reactive frames. We also discuss the manifestation of the 'reactive' idea in the context of automata theory, where we allow the automaton to react and change it's own definition as it responds to input, and in graph theory, where the graph can change under us as we manipulate it. [ABSTRACT FROM AUTHOR]

This paper introduces the idea of reactive semantics and reactive Beth tableaux for modal logic and quotes some of its applications. The reactive idea is very simple. Given a system with states and the possibility of transitions moving from one state to another, we can naturally imagine a path beginning at an initial state and moving along the path following allowed transitions. If our starting point is s, and the path is s, s,..., s, then the system is ordinary non-reactive system if the options available at s (i.e., which states t we can go to from s) do not depend on the path s,..., s (i.e., do not depend on how we got to s). Otherwise if there is such dependence then the system is reactive. It seems that the simple idea of taking existing systems and turning them reactive in certain ways, has many new applications. The purpose of this paper is to introduce reactive tableaux in particular and illustrate and present some of the applications of reactivity in general. Mathematically one can take a reactive system and turn it into an ordinary system by taking the paths as our new states. This is true but from the point of view of applications there is serious loss of information here as the applicability of the reactive system comes from the way the change occurs along the path. In any specific application, the states have meaning, the transitions have meaning and the paths have meaning. Therefore the changes in the system as we go along a path can have very important meaning in the context, which enhances the usability of the model. [ABSTRACT FROM AUTHOR]

We consider logics which define different properties of functions - such as injectivity, surjectivity, monotonicity, etc. - in the context of temporal×modal logic. In this type of logics, the possible worlds semantics is modified by considering each world as a temporal flow and using accessibility functions to represent the connection among them. This approach is adequate to model interactions between processes with clocks that can be either synchronized or not. We study the definability and give indexed axiomatic systems for these properties. [ABSTRACT FROM AUTHOR]

We study the isomorphic implication problem for Boolean constraints. We show that this is a natural analog of the subgraph isomorphism problem. We prove that, depending on the set of constraints, this problem is in P, or is NP-complete, or is NP-hard, coNP-hard, and in P. We show how to extend the NP-hardness and coNP-hardness to P-hardness for some cases, and conjecture that this can be done in all cases. [ABSTRACT FROM AUTHOR]

We classify the computational complexity of all constraint satisfaction problems where the constraint language is preserved by all permutations of the domain. A constraint language is preserved by all permutations of the domain if and only if all the relations in the language can be defined by boolean combinations of the equality relation. We call the corresponding constraint languages equality constraint languages. For the classification result we apply the universal-algebraic approach to infinite-valued constraint satisfaction, and show that an equality constraint language is tractable if it admits a constant unary polymorphism or an injective binary polymorphism, and is NP-complete otherwise. We also discuss how to determine algorithmically whether a given constraint language is tractable. [ABSTRACT FROM AUTHOR]

In this paper, we generalize the definitions of transitivity, reflexivity, symmetry, Euclidean and serial properties of relations in the context of a functional approach for temporal×modal logic. The main result is the proof of definability of these definitions which is obtained by using algebraic characterizations. As a consequence, we will have in our temporal×modal context the generalizations of modal logics T, S4, S5, KD45, etc. These new logics will allow us to establish connections among time flows in very different ways, which enables us to carry out different relations among asynchronous systems. Our further research is focused on the construction of logics with these properties and the design of theorem provers for these logics. [ABSTRACT FROM AUTHOR]

We show that the class of Event Clock Automata [2] admit a logical characterisation via an unrestricted monadic second order logic interpreted over timed words. The result is interesting in that it provides an unrestricted yet decidable logical characterisation of a non-trivial class of timed languages. A timed temporal logic considered earlier in the literature [11] is shown to be expressively complete with respect to the monadic logic. [ABSTRACT FROM AUTHOR]