Results 21 to 30 of about 49,212 (323)
Knowledge to Manage the Knowledge Society: The Concept of Theoretical Incompleteness
Systems, 2016 After having outlined the essential differences between non-complex systems and complex systems we briefly recall the conceptual approaches considered by the pre-complexity General Systems Theory introduced by Von Bertalanffy in 1968 and those of the ...
Gianfranco Minati
doaj +1 more source
Undecidable problems concerning densities of languages [PDF]
Discrete Mathematics & Theoretical Computer Science, 2005 In this paper we prove that the question whether a language presented by a context free grammar has density, is undecidable. Moreover we show that there is no algorithm which, given two unambiguous context free grammars on input, decides whether the ...
Jakub Kozik
doaj +1 more source
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
The Polyhedron-Hitting Problem [PDF]
, 2014 We consider polyhedral versions of Kannan and Lipton's Orbit Problem (STOC '80 and JACM '86)---determining whether a target polyhedron V may be reached from a starting point x under repeated applications of a linear transformation A in an ambient vector ...
Chonev, Ventsislav +2 more
core +2 more sources
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 Optimal Decision Procedure for MPNL over the Integers [PDF]
, 2011 Interval temporal logics provide a natural framework for qualitative and quantitative temporal reason- ing over interval structures, where the truth of formulae is defined over intervals rather than points.
Angelo Montanari +19 more
core +3 more sources
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
Completing the picture for the Skolem Problem on order-4 linear recurrence sequences [PDF]
TheoretiCSFor almost a century, the decidability of the Skolem Problem - that is, the problem of finding whether a given linear recurrence sequence (LRS) has a zero term - has remained open. A breakthrough in the 1980s established that the Skolem Problem is indeed
Piotr Bacik
doaj +1 more source
Efficient Algorithms for Membership in Boolean Hierarchies of Regular Languages [PDF]
, 2007 The purpose of this paper is to provide efficient algorithms that decide membership for classes of several Boolean hierarchies for which efficiency (or even decidability) were previously not known. We develop new forbidden-chain characterizations for the
Glasser, Christian +2 more
core +7 more sources
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