Results 31 to 40 of about 471,067 (339)
Number conserving cellular automata: new results on decidability and dynamics [PDF]
Discrete Mathematics & Theoretical Computer Science, 2003 This paper is a survey on our recent results about number conserving cellular automata. First, we prove the linear time decidability of the property of number conservation. The sequel focuses on dynamical evolutions of number conserving cellular automata.
Bruno Durand +3 more
doaj +1 more source
Equivalence Problems for Tree Transducers: A Brief Survey [PDF]
Electronic Proceedings in Theoretical Computer Science, 2014 The decidability of equivalence for three important classes of tree transducers is discussed. Each class can be obtained as a natural restriction of deterministic macro tree transducers (MTTs): (1) no context parameters, i.e., top-down tree transducers, (
Sebastian Maneth
doaj +1 more source
An analytical method for well-formed workflow/Petri net verification of classical soundness
International Journal of Applied Mathematics and Computer Science, 2014 In this paper we consider workflow nets as dynamical systems governed by ordinary difference equations described by a particular class of Petri nets. Workflow nets are a formal model of business processes.
Clempner Julio
doaj +1 more source
An Application of the Feferman-Vaught Theorem to Automata and Logics for Words over an Infinite Alphabet [PDF]
Logical Methods in Computer Science, 2008 We show that a special case of the Feferman-Vaught composition theorem gives rise to a natural notion of automata for finite words over an infinite alphabet, with good closure and decidability properties, as well as several logical characterizations.
Alexis Bès
doaj +1 more source
Decidability of second-order theories and automata on infinite trees
, 1968 Introduction. In this paper we solve the decision problem of a certain secondorder mathematical theory and apply it to obtain a large number of decidability results.
M. Rabin
semanticscholar +1 more source
DECIDABILITY IN LOCAL AND GLOBAL FIELDS
International Congress of Mathematicans, 2019 This lecture highlights some recent advances on classical decidability issues in local and global (cid:28)elds. 2010 Mathematics Subject Classi(cid:28)cation: Primary 11U05; Secondary: 03B25, 11F85, 12J10, 12L05.
J. Koenigsmann
semanticscholar +1 more source
Decidability and Undecidability Results for Propositional Schemata [PDF]
Journal of Artificial Intelligence Research, 2014 We define a logic of propositional formula schemata adding to the syntax of propositional logic indexed propositions (e.g., pi) and iterated connectives ∨ or ∧ ranging over intervals parameterized by arithmetic variables (e.g., ∧i-1n pi, where n is a ...
Vincent Aravantinos +2 more
semanticscholar +1 more source
Trees over Infinite Structures and Path Logics with Synchronization [PDF]
Electronic Proceedings in Theoretical Computer Science, 2011 We provide decidability and undecidability results on the model-checking problem for infinite tree structures. These tree structures are built from sequences of elements of infinite relational structures.
Alex Spelten +2 more
doaj +1 more source
The Complexity of Combinations of Qualitative Constraint Satisfaction Problems [PDF]
Logical Methods in Computer Science, 2020 The CSP of a first-order theory $T$ is the problem of deciding for a given finite set $S$ of atomic formulas whether $T \cup S$ is satisfiable. Let $T_1$ and $T_2$ be two theories with countably infinite models and disjoint signatures.
Manuel Bodirsky, Johannes Greiner
doaj +1 more source
Recent Developments on Insertion-Deletion Systems [PDF]
Computer Science Journal of Moldova, 2010 This article gives an overview of the recent developments in the study of the operations of insertion and deletion. It presents the origin of these operations, their formal definition and a series of results concerning language properties, decidability ...
Sergey Verlan
doaj