Theoretical Computer Science

article

Compact and tractable automaton-based representations of time granularities

Ugo Dal Lago, Angelo Montanari, Gabriele Puppis

Theoretical Computer Science > 2007 > 373 > 1-2 > 115-141

Most approaches to time granularity proposed in the literature are based on algebraic and logical formalisms [J. Euzenat, A. Montanari, Time granularity, in: M. Fisher, D. Gabbay, L. Vila (Eds.), Handbook of Temporal Reasoning in Artificial Intelligence, Elsevier, 2005, pp. 59–118]. Here we follow an alternative automaton-based approach, originally outlined in [U. Dal Lago, A. Montanari, Calendars,...

article

Editorial Board

Theoretical Computer Science > 2007 > 373 > 1-2 > v-ix

article

Space-aware ambients and processes

Franco Barbanera, Michele Bugliesi, Mariangiola Dezani-Ciancaglini, Vladimiro Sassone

Theoretical Computer Science > 2007 > 373 > 1-2 > 41-69

Resource control has attracted increasing interest in foundational research on distributed systems. This paper focuses on space control and develops an analysis of space usage in the context of an ambient calculus with bounded capacities and weighed processes, where migration and activation require space. A type system controls the dynamics of the calculus by providing static guarantees that the intended...

article

Conjunction on processes: Full abstraction via ready-tree semantics

Gerald Lüttgen, Walter Vogler

Theoretical Computer Science > 2007 > 373 > 1-2 > 19-40

A key problem in mixing operational (e.g. process-algebraic) and declarative (e.g. logical) styles of specification is how to deal with inconsistencies arising when composing processes under conjunction. This article introduces a conjunction operator on labelled transition systems capturing the basic intuition of ‘a and b = false’, and considers a naive preorder that demands that an inconsistent specification...

article

Equivalence of linear, free, liberal, structured program schemas is decidable in polynomial time

Sebastian Danicic, Mark Harman, Rob Hierons, John Howroyd, more

Theoretical Computer Science > 2007 > 373 > 1-2 > 1-18

A program schema defines a class of programs, all of which have identical statement structure, but whose expressions may differ. We define a class of syntactic similarity binary relations between linear structured schemas, which characterise schema equivalence for structured schemas that are linear, free and liberal. In this paper we report that similarity implies equivalence for linear schemas, and...

article

Axiomatizations for probabilistic finite-state behaviors

Yuxin Deng, Catuscia Palamidessi

Theoretical Computer Science > 2007 > 373 > 1-2 > 92-114

We study a process calculus which combines both nondeterministic and probabilistic behavior in the style of Segala and Lynch’s probabilistic automata. We consider various strong and weak behavioral equivalences, and we provide complete axiomatizations for finite-state processes, restricted to guarded recursion in case of the weak equivalences. We conjecture that in the general case of unguarded recursion...

article

Towards “dynamic domains”: Totally continuous cocomplete Q-categories

Isar Stubbe

Theoretical Computer Science > 2007 > 373 > 1-2 > 142-160

It is common practice in both theoretical computer science and theoretical physics to describe the (static) logic of a system by means of a complete lattice. When formalizing the dynamics of such a system, the updates of that system organize themselves quite naturally in a quantale, or more generally, a quantaloid. In fact, we are led to consider cocomplete quantaloid-enriched categories as a fundamental...

article

Reflection in membership equational logic, many-sorted equational logic, Horn logic with equality, and rewriting logic

Manuel Clavel, José Meseguer, Miguel Palomino

Theoretical Computer Science > 2007 > 373 > 1-2 > 70-91

We show that the generalized variant of formal systems where the underlying equational specifications are membership equational theories, and where the rules are conditional and can have equations, memberships and rewrites in the conditions is reflective. We also show that membership equational logic, many-sorted equational logic, and Horn logic with equality are likewise reflective. These results...

INFONA - science communication portal

Theoretical Computer Science

Compact and tractable automaton-based representations of time granularities

Editorial Board

Space-aware ambients and processes

Conjunction on processes: Full abstraction via ready-tree semantics

Equivalence of linear, free, liberal, structured program schemas is decidable in polynomial time

Axiomatizations for probabilistic finite-state behaviors

Towards “dynamic domains”: Totally continuous cocomplete Q-categories

Reflection in membership equational logic, many-sorted equational logic, Horn logic with equality, and rewriting logic

Filter options

Publication date

Keywords

INFONA - science communication portal

Theoretical Computer Science

Add recipient

Sending message cancelled

Are you sure you want to cancel sending this message?

Send message

Filter options

Publication date

Date range setting

Set the date range to filter the displayed results. You can set a starting date, ending date or both. You can enter the dates manually or choose them from the calendar.

Keywords

Reporting an error / abuse

Sending the report failed

Accessibility options