A FRAGMENT OF 1ST-ORDER LOGIC ADEQUATE FOR OBSERVATION EQUIVALENCE

1992-01-01
We present a logical characterization of the Milner's notion of observation equivalence of processes (''at most one observable action at a time'' variant) by using a restricted class of first order formulas. We use the game technique due to Ehrenfeucht as a means to achieve this characterization. First we extend the Ehrenfeucht game by introducing a pair of compatibility relations as a parameter to the game so that we can restrict the moves of the players on the basis of the previous moves. We then define the logic which corresponds to the extended game. Second we characterize the observation equivalence on a restricted class of labelled transition systems (with tau moves), called trace-unique labelled transition systems (t-taults's), as the equivalence induced by the games played on certain reducts of the given t-taults's where the compatibility relations are defined in terms of bounded reachability in the t-taults's. Combining these two characterizations we get our main result.
LECTURE NOTES IN COMPUTER SCIENCE

Suggestions

A fragment of first order logic adequate for observation equivalence
Oğuztüzün, Mehmet Halit S. (1992-01-01)
© Springer-Verlag Berlin Heidelberg 1992.We present a logical characterization of the Milner’s notion of observation equivalence of processes (“at most one observable action at a time” variant) by using a restricted class of first order formulas. We use the game technique due to Ehrenfeucht as a means to achieve this characterization. First we extend the Ehrenfeucht game by introducing a pair of compatibility relations as a parameter to the game so that we can restrict the moves of the players on the basis ...
Fusion of Image Segmentations under Markov Random Fields
Karadag, Ozge Oztimur; Yarman Vural, Fatoş Tunay (2014-08-28)
In this study, a fast and efficient consensus segmentation method is proposed which fuses a set of baseline segmentation maps under an unsupervised Markov Random Fields (MRF) framework. The degree of consensus among the segmentation maps are estimated as the relative frequency of co-occurrences among the adjacent segments. Then, these relative frequencies are used to construct the energy function of an unsupervised MRF model. It is well-known that MRF framework is commonly used for formulating the spatial r...
A SPINOR MODEL FOR QUANTUM COSMOLOGY
DERELI, T; ONDER, M; TUCKER, RW (1994-03-31)
The question of the interpretation of Wheeler-DeWitt solutions in the context of cosmological models is addressed by implementing the Hamiltonian constraint as a spinor wave equation in minisuperspace. We offer a relative probability interpretation based on a non-closed vector current in this space and a prescription for a parametrisation of classical solutions in terms of classical time. Such a prescription can accommodate classically degenerate metrics describing manifolds with signature change. The relat...
Sphere-packing bound for block-codes with feedback and finite memory
Giacomo, Como; Nakiboğlu, Barış (2010-07-23)
A lower bound bound is established on the error probability of fixed-length block-coding systems with finite memory feedback, which can be described in terms of a time dependent finite state machine. It is shown that the reliability function of such coding systems over discrete memoryless channels is upper-bounded by the sphere-packing exponent.
A Favorable Weight-Based Evolutionary Algorithm for Multiple Criteria Problems
SOYLU, Banu; Köksalan, Mustafa Murat (Institute of Electrical and Electronics Engineers (IEEE), 2010-04-01)
In this paper, we present a favorable weight-based evolutionary algorithm for multiple criteria problems. The algorithm tries to both approximate the Pareto frontier and evenly distribute the solutions over the frontier. These two goals are common for many multiobjective evolutionary algorithms. To achieve these goals in our algorithm, each member selects its own weights for a weighted Tchebycheff distance function to define its fitness score. The fitness scores favor solutions that are closer to the Pareto...
Citation Formats
M. H. S. Oğuztüzün, “A FRAGMENT OF 1ST-ORDER LOGIC ADEQUATE FOR OBSERVATION EQUIVALENCE,” LECTURE NOTES IN COMPUTER SCIENCE, pp. 278–292, 1992, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/55197.