Results 11 to 20 of about 882,949 (238)
A rich hierarchy of functionals of finite types [PDF]
Logical Methods in Computer Science, 2009 We are considering typed hierarchies of total, continuous functionals using complete, separable metric spaces at the base types. We pay special attention to the so called Urysohn space constructed by P. Urysohn. One of the properties of the Urysohn space
Dag Normann
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
Coalgebraic Automata Theory: Basic Results [PDF]
Logical Methods in Computer Science, 2008 We generalize some of the central results in automata theory to the abstraction level of coalgebras and thus lay out the foundations of a universal theory of automata operating on infinite objects. Let F be any set functor that preserves weak pullbacks.
C. Kupke, Y. Venema
doaj +1 more source
First-Order and Temporal Logics for Nested Words [PDF]
Logical Methods in Computer Science, 2008 Nested words are a structured model of execution paths in procedural programs, reflecting their call and return nesting structure. Finite nested words also capture the structure of parse trees and other tree-structured data, such as XML.
Rajeev Alur +5 more
doaj +1 more source
Interactive Small-Step Algorithms I: Axiomatization [PDF]
Logical Methods in Computer Science, 2007 In earlier work, the Abstract State Machine Thesis -- that arbitrary algorithms are behaviorally equivalent to abstract state machines -- was established for several classes of algorithms, including ordinary, interactive, small-step algorithms.
Andreas Blass +3 more
doaj +1 more source
Weak Alternating Timed Automata [PDF]
Logical Methods in Computer Science, 2012 Alternating timed automata on infinite words are considered. The main result is a characterization of acceptance conditions for which the emptiness problem for these automata is decidable.
Pawel Parys, Igor Walukiewicz
doaj +1 more source
Petri Net Reachability Graphs: Decidability Status of First Order Properties [PDF]
Logical Methods in Computer Science, 2012 We investigate the decidability and complexity status of model-checking problems on unlabelled reachability graphs of Petri nets by considering first-order and modal languages without labels on transitions or atomic propositions on markings.
Philippe Darondeau +3 more
doaj +1 more source
Automata with Nested Pebbles Capture First-Order Logic with Transitive Closure [PDF]
Logical Methods in Computer Science, 2007 String languages recognizable in (deterministic) log-space are characterized either by two-way (deterministic) multi-head automata, or following Immerman, by first-order logic with (deterministic) transitive closure.
Joost Engelfriet, Hendrik Jan Hoogeboom
doaj +1 more source
Interactive Small-Step Algorithms II: Abstract State Machines and the Characterization Theorem [PDF]
Logical Methods in Computer Science, 2007 In earlier work, the Abstract State Machine Thesis -- that arbitrary algorithms are behaviorally equivalent to abstract state machines -- was established for several classes of algorithms, including ordinary, interactive, small-step algorithms.
Andreas Blass +3 more
doaj +1 more source
Dense-Timed Petri Nets: Checking Zenoness, Token liveness and Boundedness [PDF]
Logical Methods in Computer Science, 2007 We consider Dense-Timed Petri Nets (TPN), an extension of Petri nets in which each token is equipped with a real-valued clock and where the semantics is lazy (i.e., enabled transitions need not fire; time can pass and disable transitions).
Parosh Abdulla +2 more
doaj +1 more source