CNR Author
operator:
and / or
Typology
operator:
and / or
Language
operator:
and / or
Rights
operator:
and / or
2004
Journal article
Open Access
Composing event constraints in state-based specification
Bolognesi T.
Event-based process algebraic specification languages support an elegant specification technique by which system behaviours are described as compositions of constraints on event occurrences and event parameters. This paper investigates the possibility to export this specification paradigm to a state-based formalism, and discusses some deriving advantages in terms of verification.
Bolognesi T.
Event-based process algebraic specification languages support an elegant specification technique by which system behaviours are described as compositions of constraints on event occurrences and event parameters. This paper investigates the possibility to export this specification paradigm to a state-based formalism, and discusses some deriving advantages in terms of verification.
See at:
CNR IRIS 
| www.springerlink.com | CNR IRIS 
2007
Journal article
Restricted
Behavioral complexity indicators for process algebra: the NKS approach
Bolognesi T
Several techniques for the experimental investigation of the computing power of various formal models, from cellular automata to Turing machines, have been proposed by S.Wolfram with his NKS (New Kind of Science). Visual complexity indicators reveal the 'internal shapes' of computations, and may expose constant, periodic, nested/fractal, pseudo-random, and even more sophisticated dynamics. In this paper we investigate visual complexity indicators for process algebra. With its emphasis on reactive, continuously observable behavior, as opposed to input/output behavior, process algebra might appear as an ideal candidate for NKS-style investigations; however, this formal model is in some sense more elaborate than the simple formalisms addressed in NKS, and poses specific problems, such as the presence of both events and states, and the explosive nature of non-determinism. We consider a set of process algebraic operators and prove its Turing universality by showing that they can emulate any elementary cellular automaton, including n. 110, which is itself universal. The correctness of the emulation is supported by an original visual indicator, which is then used for exploring various subclasses of algebraic expressions and their emergent features. Based on this indicator, and even by restricting to deterministic computations, we have detected and measured, by a data compression technique, the emergence of randomness in a subclass of expressions which is provably not universal. Besides providing a suggestive visualization of the relative strengths of operator subsets, we believe that results of this type, both of theoretical and of experimental nature, are desirable in light of one of the key NKS conjectures, according to which random-like behavior would be a witness of computational universality.Source: JOURNAL OF LOGIC AND ALGEBRAIC PROGRAMMING, vol. 72 (issue 1), pp. 50-77
Bolognesi T
Several techniques for the experimental investigation of the computing power of various formal models, from cellular automata to Turing machines, have been proposed by S.Wolfram with his NKS (New Kind of Science). Visual complexity indicators reveal the 'internal shapes' of computations, and may expose constant, periodic, nested/fractal, pseudo-random, and even more sophisticated dynamics. In this paper we investigate visual complexity indicators for process algebra. With its emphasis on reactive, continuously observable behavior, as opposed to input/output behavior, process algebra might appear as an ideal candidate for NKS-style investigations; however, this formal model is in some sense more elaborate than the simple formalisms addressed in NKS, and poses specific problems, such as the presence of both events and states, and the explosive nature of non-determinism. We consider a set of process algebraic operators and prove its Turing universality by showing that they can emulate any elementary cellular automaton, including n. 110, which is itself universal. The correctness of the emulation is supported by an original visual indicator, which is then used for exploring various subclasses of algebraic expressions and their emergent features. Based on this indicator, and even by restricting to deterministic computations, we have detected and measured, by a data compression technique, the emergence of randomness in a subclass of expressions which is provably not universal. Besides providing a suggestive visualization of the relative strengths of operator subsets, we believe that results of this type, both of theoretical and of experimental nature, are desirable in light of one of the key NKS conjectures, according to which random-like behavior would be a witness of computational universality.Source: JOURNAL OF LOGIC AND ALGEBRAIC PROGRAMMING, vol. 72 (issue 1), pp. 50-77
See at:
biblioproxy.cnr.it | CNR IRIS | CNR IRIS
2007
Journal article
Metadata Only Access
Planar trivalent network computation
Bolognesi T.
Confluent rewrite systems for giant trivalent networks have been investigated by S. Wolfram as possible models of space and spacetime, in the ambitious search for the most fundamental, computational laws of physics. We restrict here to planar trivalent nets, which are shown to support Turing-complete computations, and take an even more radical, approach: while operating on network duals, we use just one elementary rewrite rule and drive its application by a simple, fully deterministic algorithm, rather than by pattern-matching. We devise effective visual indicators for exploring the complexity of computations with elementary initial conditions, consisting of thousands of graphs, and expose a rich variety of behaviors, from regular to random-like. Among their features we study, in particular, the dimensionality of the emergent space.
Bolognesi T.
Confluent rewrite systems for giant trivalent networks have been investigated by S. Wolfram as possible models of space and spacetime, in the ambitious search for the most fundamental, computational laws of physics. We restrict here to planar trivalent nets, which are shown to support Turing-complete computations, and take an even more radical, approach: while operating on network duals, we use just one elementary rewrite rule and drive its application by a simple, fully deterministic algorithm, rather than by pattern-matching. We devise effective visual indicators for exploring the complexity of computations with elementary initial conditions, consisting of thousands of graphs, and expose a rich variety of behaviors, from regular to random-like. Among their features we study, in particular, the dimensionality of the emergent space.
See at:
CNR IRIS
2003
Conference article
Restricted
Remarks on Turbo ASMs for Functional Equations and Recursion Schemes
Boerger E, Bolognesi T
The question raised in [15] is answered how to naturally model widely used forms of recursion by abstract machines. We show that turbo ASMs as defined in [7] allow one to faithfully reflect the common intuitive single-agent understanding of recursion. The argument is illustrated by turbo ASMs for Mergesort and Quicksort. Using turbo ASMs for returning function values allows one to seamlessly integrate functional description and programming techniques into the high-level 'abstract programming' by state transforming ASM rules.
Boerger E, Bolognesi T
The question raised in [15] is answered how to naturally model widely used forms of recursion by abstract machines. We show that turbo ASMs as defined in [7] allow one to faithfully reflect the common intuitive single-agent understanding of recursion. The argument is illustrated by turbo ASMs for Mergesort and Quicksort. Using turbo ASMs for returning function values allows one to seamlessly integrate functional description and programming techniques into the high-level 'abstract programming' by state transforming ASM rules.
2009
Journal article
Restricted
A pseudo-random network mobile automaton with linear growth
Bolognesi T
Based on the mobile automaton model, an algorithm is introduced that grows planar, tri-valent graphs by exhibiting a peculiar, twofold dynamics. In a first phase, graph growth appears to be pseudo-random and O(n); then it settles to a very regular behavior and O(Sqrt(n)) rate. A pseudo-random O(Sqrt(n)) mobile automaton is already known; the new automaton provides now a finite, but surprisingly long, pseudo-random, linear growth process. Applications of mobile automata to fundamental physics and quantum gravity have been recently suggested.Source: INFORMATION PROCESSING LETTERS, vol. 109 (issue 13), pp. 668-674
Bolognesi T
Based on the mobile automaton model, an algorithm is introduced that grows planar, tri-valent graphs by exhibiting a peculiar, twofold dynamics. In a first phase, graph growth appears to be pseudo-random and O(n); then it settles to a very regular behavior and O(Sqrt(n)) rate. A pseudo-random O(Sqrt(n)) mobile automaton is already known; the new automaton provides now a finite, but surprisingly long, pseudo-random, linear growth process. Applications of mobile automata to fundamental physics and quantum gravity have been recently suggested.Source: INFORMATION PROCESSING LETTERS, vol. 109 (issue 13), pp. 668-674
See at:
biblioproxy.cnr.it | CNR IRIS | CNR IRIS | CNR IRIS
2010
Journal article
Restricted
Causal sets from simple models of computation
Bolognesi T
Causality among events is widely recognized as a most fundamental structure of spacetime, and causal sets have been proposed as discrete models of the latter in the context of quantum gravity theories, notably in the Causal Set Programme. In the rather different context of what might be called the 'Computational Universe Programme' -- one which associates the complexity of physical phenomena to the emergent features of models such as cellular automata -- a choice problem arises with respect to the variety of formal systems that, in virtue of their computational universality (Turing-completeness), qualify as equally good candidates for a computational, unified theory of physics. We address this problem by proposing Causal Sets to be the only objects of physical significance under the computational universe perspective. At the same time, we propose a fully deterministic, radical alternative to the probabilistic techniques considered in the Causal Set Programme for growing discrete spacetime instances. We investigate a number of computation models, all operating on a one-dimensional support like a tape or a string of symbols, we identify the causality relation among their computation events, implement it, and conduct a possibly exhaustive exploration of the associated causal set space, while examining quantitative and qualitative features such as dimensionality, curvature, planarity, emergence of pseudo-randomness and particles.Source: INTERNATIONAL JOURNAL OF UNCONVENTIONAL COMPUTING, vol. 6, pp. 489-524
Bolognesi T
Causality among events is widely recognized as a most fundamental structure of spacetime, and causal sets have been proposed as discrete models of the latter in the context of quantum gravity theories, notably in the Causal Set Programme. In the rather different context of what might be called the 'Computational Universe Programme' -- one which associates the complexity of physical phenomena to the emergent features of models such as cellular automata -- a choice problem arises with respect to the variety of formal systems that, in virtue of their computational universality (Turing-completeness), qualify as equally good candidates for a computational, unified theory of physics. We address this problem by proposing Causal Sets to be the only objects of physical significance under the computational universe perspective. At the same time, we propose a fully deterministic, radical alternative to the probabilistic techniques considered in the Causal Set Programme for growing discrete spacetime instances. We investigate a number of computation models, all operating on a one-dimensional support like a tape or a string of symbols, we identify the causality relation among their computation events, implement it, and conduct a possibly exhaustive exploration of the associated causal set space, while examining quantitative and qualitative features such as dimensionality, curvature, planarity, emergence of pseudo-randomness and particles.Source: INTERNATIONAL JOURNAL OF UNCONVENTIONAL COMPUTING, vol. 6, pp. 489-524
See at:
CNR IRIS | CNR IRIS | www.oldcitypublishing.com
2004
Journal article
Open Access
Predicates for state changes vs. processes for event patterns
Bolognesi T
The two informal 'mental landscapes' that provide the intuitive substratum for state- oriented and event-oriented formal specifications are discussed, and abstractly characterised as net- works of constraints. The structuring facilities offered by the two approaches are contrasted. A technique is introduced for expanding an event-oriented specification consisting of a fixed pattern of interacting processes into a state-oriented specification formed by a complex 'action predicate' manipulating a set of state variables. Although by this transformation the event and process con- cepts can be absorbed into the state-based conceptual framework, we discuss some good reasons for regarding these concepts as primitive expressive tools, and for structuring specifications around them.Source: STUDIA INFORMATICA UNIVERSALIS. HORS SEĢRIE, vol. 3 (issue 1), pp. 85-124
Bolognesi T
The two informal 'mental landscapes' that provide the intuitive substratum for state- oriented and event-oriented formal specifications are discussed, and abstractly characterised as net- works of constraints. The structuring facilities offered by the two approaches are contrasted. A technique is introduced for expanding an event-oriented specification consisting of a fixed pattern of interacting processes into a state-oriented specification formed by a complex 'action predicate' manipulating a set of state variables. Although by this transformation the event and process con- cepts can be absorbed into the state-based conceptual framework, we discuss some good reasons for regarding these concepts as primitive expressive tools, and for structuring specifications around them.Source: STUDIA INFORMATICA UNIVERSALIS. HORS SEĢRIE, vol. 3 (issue 1), pp. 85-124
See at:
CNR IRIS | studia.complexica.net | CNR IRIS
2006
Journal article
Metadata Only Access
Process algebra under the light of Wolfram's NKS
Bolognesi T.
The strong intellectual investment behind the definition of process algebras and the high abstraction level they can attain in formal specification still contrasts with their degree of penetration into software engineering practice, but also with the relatively limited number of other fields of fundamental science where these models have played some role. An emerging area in which process algebras might lend themselves to attractive investigations is Wolfram's 'New Kind of Science' (NKS). In this short note we start discussing possible motivations and preliminary steps for placing process algebra under this new light, and for exploring its versatility by NKS-style experiments.
Bolognesi T.
The strong intellectual investment behind the definition of process algebras and the high abstraction level they can attain in formal specification still contrasts with their degree of penetration into software engineering practice, but also with the relatively limited number of other fields of fundamental science where these models have played some role. An emerging area in which process algebras might lend themselves to attractive investigations is Wolfram's 'New Kind of Science' (NKS). In this short note we start discussing possible motivations and preliminary steps for placing process algebra under this new light, and for exploring its versatility by NKS-style experiments.
See at:
CNR IRIS
2008
Journal article
Restricted
Planar trinet dynamics with two rewrite rules
Bolognesi T
We propose a deterministic network mobile automaton for the creation of planar trivalent networks (trinets) based on the application of only two simple rewrite rules, and we enumerate and explore the possible brownian dynamics of the control point. A useful behavioral complexity indicator is introduced, called revisit indicator, exposing a variety of emergent features, involving periodic, nested and random like dynamics. Regular structures obtained include 1-D graphs, oscillating rings, and the 2-D, hexagonal grid. In two cases only, out of over a thousand we have inspected, a remarkably fair, random-like revisit indicator is found, whose trinets exhibit a slow, square-root growth rate; some properties of these surprising computations are investigated. Finally, one 2-D case is found that seems to be unique in the way regularity and randomness are mixed.Source: COMPLEX SYSTEMS, vol. 18, pp. 1-41
Bolognesi T
We propose a deterministic network mobile automaton for the creation of planar trivalent networks (trinets) based on the application of only two simple rewrite rules, and we enumerate and explore the possible brownian dynamics of the control point. A useful behavioral complexity indicator is introduced, called revisit indicator, exposing a variety of emergent features, involving periodic, nested and random like dynamics. Regular structures obtained include 1-D graphs, oscillating rings, and the 2-D, hexagonal grid. In two cases only, out of over a thousand we have inspected, a remarkably fair, random-like revisit indicator is found, whose trinets exhibit a slow, square-root growth rate; some properties of these surprising computations are investigated. Finally, one 2-D case is found that seems to be unique in the way regularity and randomness are mixed.Source: COMPLEX SYSTEMS, vol. 18, pp. 1-41
See at:
CNR IRIS | CNR IRIS | CNR IRIS | CNR IRIS | CNR IRIS | CNR IRIS
2004
Conference article
Restricted
A conceptual framework for state-based and event-based formal behavioural specification languages
Bolognesi T
We introduce a simple conceptual framework for assessing a number of well known formal specification techniques w.r.t. their ability to model state-oriented and/or event-oriented aspects of system behaviour. By attributing a-priori equal importance to the notions of event and state, by explicitly recognizing the two derived, fundamental ways of thinking about system behaviours, and by assessing the bias of existing formal methods towards one or the other, one can make more conscious choices in the upper phases of software development, that is, in requirements elicitation and analysis, in the construction of abstract system models, and in the choice of formal languages for high- and low-level design. In particular, we assess the recently introduced model of Abstract State Processes, and the design choices behind its definition, in light of the introduced state-event framework.
Bolognesi T
We introduce a simple conceptual framework for assessing a number of well known formal specification techniques w.r.t. their ability to model state-oriented and/or event-oriented aspects of system behaviour. By attributing a-priori equal importance to the notions of event and state, by explicitly recognizing the two derived, fundamental ways of thinking about system behaviours, and by assessing the bias of existing formal methods towards one or the other, one can make more conscious choices in the upper phases of software development, that is, in requirements elicitation and analysis, in the construction of abstract system models, and in the choice of formal languages for high- and low-level design. In particular, we assess the recently introduced model of Abstract State Processes, and the design choices behind its definition, in light of the introduced state-event framework.
See at:
CNR IRIS | ieeexplore.ieee.org | CNR IRIS | CNR IRIS
2005
Conference article
Restricted
Process algebra under the light of Wolfram's NKS
Bolognesi T
The strong intellectual investment behind the definition of process algebras and the high abstraction level they can attain in formal specification still contrasts with their degree of penetration into software engineering practice, but also with the relatively limited number of other fields of fundamental science where these models have played some role. An emerging area in which process algebras might lend themselves to attractive investigations is Wolfram's 'New Kind of Science' (NKS). In this short note we start discussing possible motivations and preliminary steps for placing process algebra under this new light, and for exploring its versatility by NKS-style experiments.
Bolognesi T
The strong intellectual investment behind the definition of process algebras and the high abstraction level they can attain in formal specification still contrasts with their degree of penetration into software engineering practice, but also with the relatively limited number of other fields of fundamental science where these models have played some role. An emerging area in which process algebras might lend themselves to attractive investigations is Wolfram's 'New Kind of Science' (NKS). In this short note we start discussing possible motivations and preliminary steps for placing process algebra under this new light, and for exploring its versatility by NKS-style experiments.
See at:
CNR IRIS | CNR IRIS | www.brics.dk
2002
Conference article
Metadata Only Access
See at:
CNR IRIS
2002
Contribution to conference
Metadata Only Access
See at:
CNR IRIS
2014
Journal article
Open Access
Teilhard de Chardin e Wolfram: modelli di universo computazionale ed emergenza del foglietto interno delle cose
Bolognesi T
The ambitious goal of 'The Human Phenomenon' by Teilhard de Chardin is to describe the Cosmos and its evolution in a way that integrates the outside and the inside of things - the material world and the dimensions of psyche and consciousness - while preserving the character of a scientific investigation. By following the teilhardian steps of Prelife-Life-Though, and by using results that were still largely unknown during Teilhard's lifespan, due, in particular, to Wolfram, Chaitin and Tononi, in this short essay we show that it is possible and useful to try and understand the ultimate fabric of the universe, some phenomena in the biosphere, and the notion of consciousness itself, in terms of the concept of computation, that is, as phenomena emerging from information processing.
Bolognesi T
The ambitious goal of 'The Human Phenomenon' by Teilhard de Chardin is to describe the Cosmos and its evolution in a way that integrates the outside and the inside of things - the material world and the dimensions of psyche and consciousness - while preserving the character of a scientific investigation. By following the teilhardian steps of Prelife-Life-Though, and by using results that were still largely unknown during Teilhard's lifespan, due, in particular, to Wolfram, Chaitin and Tononi, in this short essay we show that it is possible and useful to try and understand the ultimate fabric of the universe, some phenomena in the biosphere, and the notion of consciousness itself, in terms of the concept of computation, that is, as phenomena emerging from information processing.
See at:
CNR IRIS | www.edizionistudium.it | CNR IRIS
2003
Other
Open Access
On state-oriented vs. event-oriented thinking in formal behavioural specifications
Bolognesi T
In this paper an extension of a behavioural subset of UML Statecharts for modeling mobility issues is proposed. The extension builds on the notion of Multicharts, as proposed by the authors in previous work. A Multichart is a collection of Statecharts, where each Statechart is associated with a unique input queue. In a Multichart each Statechart can address its output events directly to each (other) Statechart of the Multichart by explicitly mentioning the name of (the unique queue of) such Statechart in its output actions. The extension we present consists in relaxing the unique association between each Statechart and its input-queue and in allowing the the use of (queue) name variables in communication actions. The resulting communication paradigm is much more flexible than the standard asymmetric one and is well suited for the modelling of mobility-oriented as well as fault tolerant systems.
Bolognesi T
In this paper an extension of a behavioural subset of UML Statecharts for modeling mobility issues is proposed. The extension builds on the notion of Multicharts, as proposed by the authors in previous work. A Multichart is a collection of Statecharts, where each Statechart is associated with a unique input queue. In a Multichart each Statechart can address its output events directly to each (other) Statechart of the Multichart by explicitly mentioning the name of (the unique queue of) such Statechart in its output actions. The extension we present consists in relaxing the unique association between each Statechart and its input-queue and in allowing the the use of (queue) name variables in communication actions. The resulting communication paradigm is much more flexible than the standard asymmetric one and is well suited for the modelling of mobility-oriented as well as fault tolerant systems.
See at:
CNR IRIS | ISTI Repository | CNR IRIS
2006
Other
Open Access
Formalizing uncertainty in service request/offer description and matching
Bolognesi T
This paper discusses the problem of describing and matching service requests and offers, that appears as central and characteristic in the context of the Service Oriented Computing (SOC) paradigm. Service descriptions, be they requests or offers, are seen as a mix of detailed, local state information, and fuzzy information, or speculation, about remote partners. Service fruition is represented, at a very high abstraction level, as an atomic interaction among two or more parties, each providing a partial view about a global state change. We propose here four formal solutions of increasing complexity; the first three of them are conveniently formalized in TLA+ and illustrated by simple examples. The use of a logic-based approach should favor the integration with current Semantic Web technologies, and with Description Logics, and at the same time it should help reducing the gap between formal and informal (natural language) descriptions of services.
Bolognesi T
This paper discusses the problem of describing and matching service requests and offers, that appears as central and characteristic in the context of the Service Oriented Computing (SOC) paradigm. Service descriptions, be they requests or offers, are seen as a mix of detailed, local state information, and fuzzy information, or speculation, about remote partners. Service fruition is represented, at a very high abstraction level, as an atomic interaction among two or more parties, each providing a partial view about a global state change. We propose here four formal solutions of increasing complexity; the first three of them are conveniently formalized in TLA+ and illustrated by simple examples. The use of a logic-based approach should favor the integration with current Semantic Web technologies, and with Description Logics, and at the same time it should help reducing the gap between formal and informal (natural language) descriptions of services.
See at:
CNR IRIS | ISTI Repository | CNR IRIS
2006
Other
Open Access
Planar trivalent network computation
Bolognesi T
Confluent rewrite systems for giant trivalent networks of unstructured nodes have been investigated by S. Wolfram as possible models of space and spacetime, in the ambitious search for the most fundamental, computational laws of physics. We restrict here to planar trivalent nets, which are shown to support Turing-complete computations, and take an even more radical, approach: while operating on network duals, we use just {em one} elementary rewrite rule -- which is singled out also by Loop Quantum Gravity -- and drive its application by (two variants of) a simple, fully deterministic algorithm, rather than by pattern-matching. We devise effective visual indicators for exploring the complexity of computations with elementary initial conditions, consisting of thousands of graphs, and expose a rich variety of behaviors, from regular to random-like. Among their features we study, in particular, the dimensionality of the emergent space.
Bolognesi T
Confluent rewrite systems for giant trivalent networks of unstructured nodes have been investigated by S. Wolfram as possible models of space and spacetime, in the ambitious search for the most fundamental, computational laws of physics. We restrict here to planar trivalent nets, which are shown to support Turing-complete computations, and take an even more radical, approach: while operating on network duals, we use just {em one} elementary rewrite rule -- which is singled out also by Loop Quantum Gravity -- and drive its application by (two variants of) a simple, fully deterministic algorithm, rather than by pattern-matching. We devise effective visual indicators for exploring the complexity of computations with elementary initial conditions, consisting of thousands of graphs, and expose a rich variety of behaviors, from regular to random-like. Among their features we study, in particular, the dimensionality of the emergent space.
See at:
CNR IRIS | ISTI Repository | CNR IRIS
2007
Other
Open Access
See at:
ISTI Repository | CNR IRIS
2005
Other
Open Access
Introductory paper - Special section on St.Eve workshop
Bolognesi T., Derrick J.
An abstract is not available
Bolognesi T., Derrick J.
An abstract is not available
See at:
CNR IRIS | ISTI Repository | CNR IRIS
2008
Other
Open Access
A pseudo-random network mobile automaton with linear growth
Bolognesi T
Based on the mobile automaton computational paradigm, a (fully deterministic) algorithm is introduced that grows planar graphs while exhibiting surprisingly uniform pseudo-random dynamics. The graph growth rate, as a function of the automaton steps, is O(n), and nicely combines with the O(Sqrt[n]) of a previously introduced algorithm of ours: these two rates are also achieved by two most elementary visit-and-grow procedures with regular dynamics, of which our automata can be viewed as randomized versions. Applications of mobile automata to fundamental physics and quantum gravity have been recently suggested, but other application areas are envisaged as well.
Bolognesi T
Based on the mobile automaton computational paradigm, a (fully deterministic) algorithm is introduced that grows planar graphs while exhibiting surprisingly uniform pseudo-random dynamics. The graph growth rate, as a function of the automaton steps, is O(n), and nicely combines with the O(Sqrt[n]) of a previously introduced algorithm of ours: these two rates are also achieved by two most elementary visit-and-grow procedures with regular dynamics, of which our automata can be viewed as randomized versions. Applications of mobile automata to fundamental physics and quantum gravity have been recently suggested, but other application areas are envisaged as well.
See at:
CNR IRIS | ISTI Repository | CNR IRIS