JUCS - Journal of Universal Computer Science - Mathematics of Computing
http://www.jucs.org/jucs_articles_by_category/G.
JUCS Topic G. - Mathematics of ComputingVerlag der Technischen Universität GrazUniversiti Malaysia Sarawak2011-07-28T11:21:46+02:00Coordinated System for Real Time Muscle Deformation during Locomotion
http://www.jucs.org/jucs_17_3/coordinated_system_for_real
This paper presents a system that simulates, in real time, the volumetric deformation of muscles during human locomotion. We propose a two-layered motion model. The requirements of realism and real time computation lead to a hybrid locomotion system that uses a skeleton as first layer. The muscles, represented by an anatomical surface model, constitute the second layer, whose deformations are simulated with a finite element method (FEM). The FEM subsystem is fed by the torques and forces got from the locomotion system, through a line of action model, and takes into account the geometry and material properties of the muscles. High level parameters (like height, weight, physical constitution, step frequency, step length or speed) allow to customize the individuals and the locomotion and therefore, the deformation of the persons' muscles.Seron, Francisco; Baldassarri, Sandra2011-04-24T11:14:51+02:00animationfinite element methodhuman locomotionmuscle deformationCoordinated System for Real Time Muscle Deformation during LocomotionSeron, FranciscoBaldassarri, Sandraanimation,finite element method,human locomotion,muscle deformationJUCS - Journal of Universal Computer Science Vol. 17201102349-376Verlag der Technischen Universität GrazUniversiti Malaysia SarawakGraz, AustriaColor Image Restoration Using Neural Network Model
http://www.jucs.org/jucs_17_1/color_image_restoration_using
Neural network learning approach for color image restoration has been discussed in this paper and one of the possible solutions for restoring images has been presented. Here neural network weights are considered as regularization parameter values instead of explicitly specifying them. The weights are modified during the training through the supply of training set data. The desired response of the network is in the form of estimated value of the current pixel. This estimated value is used to modify the network weights such that the restored value produced by the network for a pixel is as close as to this desired response. One of the advantages of the proposed approach is that, once the neural network is trained, images can be restored without having prior information about the model of noise/blurring with which the image is corrupted.M, Aswatha Kumar; Chickerur, Satyadhyan2011-04-07T14:38:54+02:00Ill Posed ProblemRegularizationcolor image restorationneural networksColor Image Restoration Using Neural Network ModelM, Aswatha KumarChickerur, SatyadhyanIll Posed Problem,Regularization,color image restoration,neural networksJUCS - Journal of Universal Computer Science Vol. 17201101107-125Verlag der Technischen Universität GrazUniversiti Malaysia SarawakGraz, AustriaComputable Separation in Topology, from <I>T</I><sub>0</sub> to <I>T</I><sub>2</sub>
http://www.jucs.org/jucs_16_18/computable_separation_in_topology
This article continues the study of computable elementary topology started in [Weihrauch and Grubba 2009]. For computable topological spaces we introduce a number of computable versions of the topological separation axioms <I>T</I><sub>0</sub>, <I>T</I><sub>1</sub> and <I>T</I><sub>2</sub>. The axioms form an implication chain with many equivalences. By counterexamples we show that most of the remaining implications are proper. In particular, it turns out that computable <I>T</I><sub>1</sub> is equivalent to computable <I>T</I><sub>2</sub> and that for spaces without isolated points the hierarchy collapses, that is, the weakest computable <I>T</I><sub>0</sub> axiom WCT<sub>0</sub> is equivalent to the strongest computable <I>T</I><sub>2</sub> axiom SCT<sub>2</sub>. The <I>SCT</I><sub>2</sub>-spaces are closed under Cartesian product, this is not true for most of the other classes of spaces. Finally we show that the computable version of a basic axiom for an effective topology in intuitionistic topology is equivalent to SCT<sub>2</sub>.Weihrauch, Klaus2011-01-20T15:13:28+01:00axioms of separationcomputable analysiscomputable topologyComputable Separation in Topology, from <I>T</I><sub>0</sub> to <I>T</I><sub>2</sub>Weihrauch, Klausaxioms of separation,computable analysis,computable topologyJUCS - Journal of Universal Computer Science Vol. 162010092733-2753Verlag der Technischen Universität GrazUniversiti Malaysia SarawakGraz, AustriaFrom Computing Sets of Optima, Pareto Sets, and Sets of Nash Equilibria to General Decision-Related Set Computations
http://www.jucs.org/jucs_16_18/from_computing_sets_of
Several algorithms have been proposed to compute sets of optima, Pareto sets, and sets of Nash equilibria. In this paper, we present a general algorithm for decision-related set computations that includes all these algorithms as particular cases.</P> <P> To make our algorithm understandable to people working in optimization and in game theory, we also provide motivations and explanations for our formalizations of the corresponding problems and for the related notions of computable mathematics.Kubica, Bartlomiej Jacek; Kreinovich, Vladik2011-01-20T15:13:15+01:00Nash equilibriaPareto setscomputing setssets of optimaFrom Computing Sets of Optima, Pareto Sets, and Sets of Nash Equilibria to General Decision-Related Set ComputationsKubica, Bartlomiej JacekKreinovich, VladikNash equilibria,Pareto sets,computing sets,sets of optimaJUCS - Journal of Universal Computer Science Vol. 162010092657-2685Verlag der Technischen Universität GrazUniversiti Malaysia SarawakGraz, AustriaCompositional Semantics of Dataflow Networks with Query-Driven Communication of Exact Values
http://www.jucs.org/jucs_16_18/compositional_semantics_of_dataflow
We develop and study the concept of <I>dataflow process networks</I> as used for exampleby Kahn to suit exact computation over data types related to real numbers, such as continuous functions and geometrical solids. Furthermore, we consider communicating these exact objectsamong processes using protocols of a query-answer nature as introduced in our earlier work. This enables processes to provide valid approximations with certain accuracy and focusing on certainlocality as demanded by the receiving processes through queries.</P> <P>We define domain-theoretical denotational semantics of our networks in two ways: (1) <I>directly</I>, i. e. by viewing the whole network as a composite process and applying the process semantics introduced in our earlier work; and (2) <I>compositionally</I>, i. e. by a fixed-point construction similarto that used by Kahn from the denotational semantics of individual processes in the network. The direct semantics closely corresponds to the operational semantics of the network (i. e. it iscorrect) but very difficult to study for concrete networks. The compositional semantics enablescompositional analysis of concrete networks, assuming it is correct.</P> <P>We prove that the compositional semantics is a <I>safe</I> approximation of the direct semantics. Wealso provide a method that can be used in many cases to establish that the two semantics <I>fully coincide</I>, i. e. safety is not achieved through inactivity or meaningless answers. The results are extended to cover recursively-defined infinite networks as well as nested finitenetworks.</P> <P>A robust prototype implementation of our model is available.Farjudian, Amin; Konečný, Michal2011-01-20T15:13:10+01:00dataflow networksdenotational semanticsdistributed computationdomain theoryexact real computationCompositional Semantics of Dataflow Networks with Query-Driven Communication of Exact ValuesFarjudian, AminKonečný, Michaldataflow networks,denotational semantics,distributed computation,domain theory,exact real computationJUCS - Journal of Universal Computer Science Vol. 162010092629-2656Verlag der Technischen Universität GrazUniversiti Malaysia SarawakGraz, AustriaOn Choice Principles and Fan Theorems
http://www.jucs.org/jucs_16_18/on_choice_principles_and
Veldman proved that the contrapositive of countable binary choice is a theorem of full-fledged intuitionism, to which end he used a principle of continuous choice and the fan theorem. It has turned out that continuous choice is unnecessary in this context, and that a weak form of the fan theorem suffices which holds in the presence of countable choice. In particular, the contrapositive of countable binary choice is valid in Bishop-style constructive mathematics. We further discuss a generalisation of this result and link it to Ishihara's boundedness principle BD-N.Diener, Hannes; Schuster, Peter2011-01-20T15:13:01+01:00constructive mathematicscountable choicefan theoremOn Choice Principles and Fan TheoremsDiener, HannesSchuster, Peterconstructive mathematics,countable choice,fan theoremJUCS - Journal of Universal Computer Science Vol. 162010092556-2562Verlag der Technischen Universität GrazUniversiti Malaysia SarawakGraz, AustriaIsometries and Computability Structures
http://www.jucs.org/jucs_16_18/isometries_and_computability_structures
We investigate the relationship between computable metric spaces (Χ, <I>d</I>, α) and (Χ, <I>d</I>, β), where (Χ, <I>d</I>) is a given metric space. In the case of Euclidean space, α and β are equivalent up to isometry, which does not hold in general. We introduce the notion of effectively dispersed metric space and we use it in the proof of the following result: if (Χ, <I>d</I>, α) is effectively totally bounded, then (Χ, <I>d</I>, β) is also effectively totally bounded. This means that the property that a computable metric space is effectively totally bounded (and in particular effectively compact) depends only on the underlying metric space. In the final section of this paper we examine compact metric spaces (Χ, <I>d</I>) such that there are only finitely many isometries Χ → Χ. We prove that in this case a stronger result holds than the previous one: if (Χ, <I>d</I>, α) is effectively totally bounded, then α and β are equivalent. Hence if (Χ, <I>d</I>, α) is effectively totally bounded, then (Χ, <I>d</I>) has a unique computability structure.Iljazović, Zvonko2011-01-20T15:12:52+01:00computability structurecomputable metric spaceeffective compactnesseffective dispersioneffective total boundednessisometryIsometries and Computability StructuresIljazović, Zvonkocomputability structure,computable metric space,effective compactness,effective dispersion,effective total boundedness,isometryJUCS - Journal of Universal Computer Science Vol. 162010092569-2596Verlag der Technischen Universität GrazUniversiti Malaysia SarawakGraz, AustriaSemantics of Query-Driven Communication of Exact Values
http://www.jucs.org/jucs_16_18/semantics_of_query_driven
We address the question of how to communicate among distributed processes valuessuch as real numbers, continuous functions and geometrical solids with arbitrary precision, yet efficiently. We extend the established concept of lazy communication using streams of approximants by introducing explicit queries. We formalise this approach using protocols of a <I>query-answer</I> nature. Such protocols enable processes to provide valid approximations with certain accuracy and focusing on certain locality as demanded by the receiving processes through queries.</P> <P> A lattice-theoretic denotational semantics of channel and process behaviour is developed. Thequery space is modelled as a continuous lattice in which the top element denotes the query demanding <I>all the information</I>, whereas other elements denote queries demanding partial and/or local information. Answers are interpreted as elements of lattices constructed over suitable domains of approximations to the exact objects. An unanswered query is treated as an error anddenoted using the top element. <P></P> The major novel characteristic of our semantic model is that it reflects the dependency of answerson queries. This enables the definition and analysis of an appropriate concept of <I>convergence rate</I>, by assigning an <I>effort indicator</I> to each query and a measure of information content to eachanswer. Thus we capture not only what function a process computes, but also how a process transforms the convergence rates from its inputs to its outputs. In future work these indicatorscan be used to capture further computational complexity measures.</P> <P> A robust prototype implementation of our model is available.Farjudian, Amin; Konečný, Michal2011-01-20T15:12:46+01:00dataflow networksdenotational semanticsdistributed computationdomain theoryexact real computationSemantics of Query-Driven Communication of Exact ValuesFarjudian, AminKonečný, Michaldataflow networks,denotational semantics,distributed computation,domain theory,exact real computationJUCS - Journal of Universal Computer Science Vol. 162010092597-2628Verlag der Technischen Universität GrazUniversiti Malaysia SarawakGraz, AustriaCanonical Effective Subalgebras of Classical Algebras as Constructive Metric Completions
http://www.jucs.org/jucs_16_18/canonical_effective_subalgebras_of
We prove general theorems about unique existence of effective subalgebras of classical algebras. The theorems are consequences of standard facts about completions of metric spaces within the framework of constructive mathematics, suitably interpreted in realizability models. We work with general realizability models rather than with a particular model of computation. Consequently, all the results are applicable in various established schools of computability, such as type 1 and type 2 effectivity, domain representations, equilogical spaces, and others.Bauer, Andrej; Blanck, Jens2011-01-20T15:12:38+01:00computable and effective algebraconstructive metric spacesrealizabilityCanonical Effective Subalgebras of Classical Algebras as Constructive Metric CompletionsBauer, AndrejBlanck, Jenscomputable and effective algebra,constructive metric spaces,realizabilityJUCS - Journal of Universal Computer Science Vol. 162010092496-2522Verlag der Technischen Universität GrazUniversiti Malaysia SarawakGraz, AustriaApplying RFD to Construct Optimal Quality-Investment Trees
http://www.jucs.org/jucs_16_14/applying_rfd_to_construct
River Formation Dynamics (RFD) is an evolutionary computation methodbased on copying how drops form rivers by eroding the ground and depositing sediments. Given a cost-evaluated graph, we apply RFD to find a way to connect a givenset of origins with a given destination in such a way that distances from origins to the destination are minimized (thus improving the quality of service) but costs to build theconnecting infrastructure are minimized (thus reducing investment expenses). After we prove the NP-completeness of this problem, we apply both RFD and an Ant ColonyOptimization (ACO) approach to heuristically solve it, and some experimental results are reported.Rubio, Fernando; Rodríguez, Ismael; Rabanal, Pablo2010-10-18T09:27:12+02:00Ant Colony Optimization AlgorithmsHeuristic AlgorithmsNP-hard problemsRiver Formation DynamicsApplying RFD to Construct Optimal Quality-Investment TreesRubio, FernandoRodríguez, IsmaelRabanal, PabloAnt Colony Optimization Algorithms,Heuristic Algorithms,NP-hard problems,River Formation DynamicsJUCS - Journal of Universal Computer Science Vol. 162010051882-1901Verlag der Technischen Universität GrazUniversiti Malaysia SarawakGraz, AustriaA Heuristic Approach to Positive Root Isolation for Multiple Power Sums
http://www.jucs.org/jucs_16_14/a_heuristic_approach_to
Given a multiple power sum (extending polynomial's exponents to real numbers), the positive root isolation problem is to find a list of disjoint intervals, satisfying that they contain all positive roots and each of them contains exactly distinct one. In this paper, we develop the pseudo-derivative sequences for multiple power sums, then generalize Fourier's theorem and Descartes' sign rule for them to overestimate the number of their positive roots. Furthermore we bring up some formulas of linear and quadratic complexity to compute complex root bounds and positive root bounds based on Descartes' sign rule and Cauchy's theorem. Besides, we advance a factorization method for multiple power sums with rational coefficients utilizing Q-linear independence, thus reduce the computational complexity in the isolation process. Finally we present an efficient algorithm to isolate all positive roots under any given minimum root separation.Mu, Chuandong; Xu, Ming; Zeng, Zhenbing; Li, Zhi-bin2010-10-18T09:27:01+02:00Descartes' sign ruleFourier's theoremmultiple power sumsroot boundsroot isolationA Heuristic Approach to Positive Root Isolation for Multiple Power SumsMu, ChuandongXu, MingZeng, ZhenbingLi, Zhi-binDescartes' sign rule,Fourier's theorem,multiple power sums,root bounds,root isolationJUCS - Journal of Universal Computer Science Vol. 162010071912-1926Verlag der Technischen Universität GrazUniversiti Malaysia SarawakGraz, AustriaNewton Method for Nonlinear Dynamic Systems with Adaptive Time Stepping
http://www.jucs.org/jucs_16_6/newton_method_for_nonlinear
This paper presents a nonlinear solver based on the Newton-Krylov methods, where the Newton equations are solved by Krylov-subspace type approaches. We focus on the solution of unsteady systems, in which the temporal terms are discretized by the backward Euler method using finite difference. To save computational cost, an adaptive time stepping is used to minimize the number of time steps. The developed program can be applied to solve any nonlinear equations, provided the users could supply the discrete form of the equations. In particular, the nonlinear solver is implemented to solve unsteady reacting flows.Zhang, Changjiang; Zhang, Jun; Shen, Wensheng; Ma, Xiaoqian2011-07-20T09:17:56+02:00Newton-Krylov methoddiffusion flameiterative solvernonlinear dynamicsNewton Method for Nonlinear Dynamic Systems with Adaptive Time SteppingZhang, ChangjiangZhang, JunShen, WenshengMa, XiaoqianNewton-Krylov method,diffusion flame,iterative solver,nonlinear dynamicsJUCS - Journal of Universal Computer Science Vol. 16201003891-902Verlag der Technischen Universität GrazUniversiti Malaysia SarawakGraz, AustriaEntropy Optimization of Social Networks Using an Evolutionary Algorithm
http://www.jucs.org/jucs_16_6/entropy_optimization_of_social
Recent work on social networks has tackled the measurement and optimization of these networks' robustness and resilience to both failures and attacks. Different metrics have been used to quantitatively measure the robustness of a social network. In this work, we design and apply a Genetic Algorithm that maximizes the cyclic entropy of a social network model, hence optimizing its robustness to failures. Our social network model is a scale-free network created using Barabási and Albert's generative model, since it has been demonstrated recently that many large complex networks display a scale-free structure. We compare the cycles distribution of the optimally robust network generated by our algorithm to that belonging to a fully connected network. Moreover, we optimize the robustness of a scale-free network based on the links-degree entropy, and compare the outcomes to that which is based on cycles-entropy. We show that both cyclic and degree entropy optimization are equivalent and provide the same final optimal distribution. Hence, cyclic entropy optimization is justified in the search for the optimal network distribution.Taniar, David; Mahdi, Khaled; Safar, Maytham; El-Sayed, Nosayba2011-07-20T09:17:49+02:00entropyevolutionary algorithmgenetic algorithmsocial networksEntropy Optimization of Social Networks Using an Evolutionary AlgorithmTaniar, DavidMahdi, KhaledSafar, MaythamEl-Sayed, Nosaybaentropy,evolutionary algorithm,genetic algorithm,social networksJUCS - Journal of Universal Computer Science Vol. 16201003983-1003Verlag der Technischen Universität GrazUniversiti Malaysia SarawakGraz, AustriaThe Tourist in the Shopping Arcade
http://www.jucs.org/jucs_16_5/the_tourist_in_the
A tourist is searching for a gift and moves along a shopping arcade until the desired object gets into sight. The location of the corresponding shop is not known in advance. Therefore in this on-line setting the tourist has to make a detour in comparison to an optimal off-line straight line path to the desired object. We can show that there is a strategy for the tourist, so that the path length is never greater than <I>C</I>* times the optimal off-line path length, where <I>C</I>* = 1.059401 . . . holds. Furthermore, there is no strategy that attains a <I>competitive factor</I> smaller than C*.Langetepe, Elmar; Trippen, Gerhard; Klein, Rolf; Fleischer, Rudolf; Kamphans, Tom2010-07-04T18:33:10+02:00computational geometryon-line algorithmson-line navigationThe Tourist in the Shopping ArcadeLangetepe, ElmarTrippen, GerhardKlein, RolfFleischer, RudolfKamphans, Tomcomputational geometry,on-line algorithms,on-line navigationJUCS - Journal of Universal Computer Science Vol. 16201003676-685Verlag der Technischen Universität GrazUniversiti Malaysia SarawakGraz, AustriaReachability in Restricted Walk on Integers
http://www.jucs.org/jucs_16_5/reachability_in_restricted_walk
We prove that two conditions are sufficient, and with three exceptions also necessary, for reachability of any position in restricted walk on integers in which the sizes of the moves to the left and to the right are constant but need not be equal. A method to compute the length of the shortest path between any two positions, as well as a shortest path algorithm when the reachability conditions are true are given. Also a complete characterization for Hamiltonian restricted walks between absorbing boundaries is given.Ginzboorg, Philip; Niemi, Valtteri2010-07-04T18:33:03+02:00Hamiltonian pathrandom walkreachabilityshortest pathstrong connectivityReachability in Restricted Walk on IntegersGinzboorg, PhilipNiemi, ValtteriHamiltonian path,random walk,reachability,shortest path,strong connectivityJUCS - Journal of Universal Computer Science Vol. 16201003686-714Verlag der Technischen Universität GrazUniversiti Malaysia SarawakGraz, AustriaMobile Agent Routing with Time Constraints: A Resource Constrained Longest-Path Approach
http://www.jucs.org/jucs_16_3/mobile_agent_routing_with
Mobile agent technology advocates the mobility of code rather than the transfer of data. As data is found in several sites, a mobile agent has to plan an itinerary to visit several sites where it collects resources to accomplish its mission. This gives rise to the mobile-agent itinerary problem (MIP) which seeks a route maximizing overall benefit from the resources while meeting a deadline. This paper formalizes MIP and develops a reduction to the resource constrained longest-path problem (CLPP) in acyclic graphs. A dynamic programming (DP) algorithm was designed to produce a family of optimal routes, allowing a mobile agent to dynamically revise its route. A fully-polynomial approximation scheme was developed to reduce the pseudo-polynomial running time of DP, whereby the distance to the optimal is controlled by a parameter ffl and the running time is limited by a polynomial on problem size and 1/ffl. The paper reports results from experiments assessing the performance of the algorithms and discusses extensions to handle non-additive objectives, non-additive constraints, and probabilistic resource constraints.Camponogara, Eduardo; Shima, Ricardo Boveto2011-04-18T12:31:50+02:00approximation algorithmsconstrained longest-pathconstrained routingdynamic programmingmobile agentsMobile Agent Routing with Time Constraints: A Resource Constrained Longest-Path ApproachCamponogara, EduardoShima, Ricardo Bovetoapproximation algorithms,constrained longest-path,constrained routing,dynamic programming,mobile agentsJUCS - Journal of Universal Computer Science Vol. 16201002372-401Verlag der Technischen Universität GrazUniversiti Malaysia SarawakGraz, AustriaA Demand Forecasting Methodology for Fuzzy Environments
http://www.jucs.org/jucs_16_1/a_demand_forecasting_methodology
Several supply chain and production planning models in the literature assume the demands are fuzzy but most of them do not offer a specific technique to derive the fuzzy demands. In this study, we propose a methodology to obtain a fuzzy-demand forecast that is represented by a possibilistic distribution. The fuzzy-demand forecast is found by aggregating forecasts based on different sources; namely statistical forecasting methods and experts' judgments. In the methodology, initially, the forecast derived from the statistical forecasting techniques and experts' judgments are represented by triangular possibilistic distributions. Subsequently, those results are combined by using weights assigned to each of them. A new objective weighting approach is used to find the weights. The proposed methodology is illustrated by an example and a sensitivity analysis is provided.Ülengin, Füsun; Kabak, Özgür2011-07-20T09:12:17+02:00Fuzzy-demand forecastaggregationobjective weightsA Demand Forecasting Methodology for Fuzzy EnvironmentsÜlengin, FüsunKabak, ÖzgürFuzzy-demand forecast,aggregation,objective weightsJUCS - Journal of Universal Computer Science Vol. 16201001121-139Verlag der Technischen Universität GrazUniversiti Malaysia SarawakGraz, AustriaModeling of Robustness Margins of the Control of a Predictive Control-Supervisory Architecture
http://www.jucs.org/jucs_15_17/modeling_of_robustness_margins
In this article a new Control-Supervisory architecture of Flexible Manufacturing Systems (FMS) is presented. We are interested particularly in construction and modelling of FMS robust control of flow-shop type to time constraints. Other than the control of production system, the goal is to observe and interpreted the robustness of resources and of manufacturing system. The P-time Petri Nets which is used for modeling of the time constraints. A methodology of construction of a robust control system generating the margins of passive and active robustness is elaborated. The redundancy of the robustness of the elementary parameters between passive and active leads us to define the ways ensuring the total robus tness of the system. To do so, a set of definitions lemmas and theorems are developed and affirmed by examples of applications.Telmoudi, Achraf Jabeur; Nabli, Lotfi; M'hiri, Radhi2010-11-25T12:34:16+01:00FMSP-time Petri Netscontrol-supervisory architecturemodelingrobustnesstime constraintsModeling of Robustness Margins of the Control of a Predictive Control-Supervisory ArchitectureTelmoudi, Achraf JabeurNabli, LotfiM'hiri, RadhiFMS,P-time Petri Nets,control-supervisory architecture,modeling,robustness,time constraintsJUCS - Journal of Universal Computer Science Vol. 152009113231-3245Verlag der Technischen Universität GrazUniversiti Malaysia SarawakGraz, AustriaRearranging Series Constructively
http://www.jucs.org/jucs_15_17/rearranging_series_constructively
Riemann's theorems on the rearrangement of absolutely convergent and conditionally convergent series of real numbers are analysed within Bishop-style constructive mathematics. The constructive proof that every rearrangement of an absolutely convergent series has the same sum is relatively straightforward; but the proof that a conditionally convergent series can be rearranged to converge to whatsoever we please is a good deal more delicate in the constructive framework. The work in the paper answers affirmatively a question posed many years ago by Beeson.Bridges, Douglas S.; Berger, Josef2010-11-25T12:34:00+01:00Rieman's theoremsconstructive analysisRearranging Series ConstructivelyBridges, Douglas S.Berger, JosefRieman's theorems,constructive analysisJUCS - Journal of Universal Computer Science Vol. 152009113160-3168Verlag der Technischen Universität GrazUniversiti Malaysia SarawakGraz, AustriaInformation Theoretically Secure Encryption with Almost Free Authentication
http://www.jucs.org/jucs_15_15/information_theoretically_secure_encryption
In cryptology, secure channels enable the exchange of messages in a confidential andauthenticated manner. The literature of cryptology is rich with proposals and analysis that address the secure communication over public (insecure) channels. In this work, we propose an informa-tion theoretically secure direction for the construction of secure channels. First, we propose a method of achieving unconditionally secure authentication with half the amount of key materialrequired by traditional unconditionally secure message authentication codes (MACs). Key reduction is achieved by utilizing the special structure of the authenticated encryption system. That is,authentication exploits the secrecy of the message to reduce the key material required for authentication. After the description of our method, since key material is the most important concernin unconditionally secure authentication, given the message is encrypted with a perfectly secret one-time pad cipher, we extend our method to achieve unconditionally secure authentication withalmost free key material. That is, we propose a method for unconditionally authenticating arbitrarily long messages with much shorter keys. Finally, we will show how the special structure ofthe authenticated encryption systems can be exploited to achieve provably secure authentication that is very efficient for the authentication of short messages.Alomair, Basel; Poovendran, Radha2010-11-25T11:07:05+01:00authenticationencryptionunconditional securityInformation Theoretically Secure Encryption with Almost Free AuthenticationAlomair, BaselPoovendran, Radhaauthentication,encryption,unconditional securityJUCS - Journal of Universal Computer Science Vol. 152009092937-2956Verlag der Technischen Universität GrazUniversiti Malaysia SarawakGraz, AustriaIdeal Homogeneous Access Structures Constructed from Graphs
http://www.jucs.org/jucs_15_14/ideal_homogeneous_access_structures
Starting from a new relation between graphs and secret sharing schemes introduced by Xiao, Liu and Zhang, we show a method to construct more general ideal homogeneous access structures. The method has some advantages: it efficiently gives an ideal homogeneous access structure for the desired rank, and some conditions can be imposed (such as forbidden or necessary subsets of players), even if the exact composition of the resulting access structure cannot be fully controlled. The number of homogeneous access structures that can be constructed in this way is quite limited; for example, we show that (<I>t</I>, <I>l</I>)-threshold access structures can be constructed from a graph only when <I>t</I> = 1, <I>t</I> = <I>l</I> - 1 or <I>t</I> = <I>l</I>.Herranz, Javier2010-11-15T11:10:43+01:00cryptographygraph connectivityideal secret sharingIdeal Homogeneous Access Structures Constructed from GraphsHerranz, Javiercryptography,graph connectivity,ideal secret sharingJUCS - Journal of Universal Computer Science Vol. 152009052881-2893Verlag der Technischen Universität GrazUniversiti Malaysia SarawakGraz, AustriaOptimal Serverless Networks Attacks, Complexity and some Approximate Algorithms
http://www.jucs.org/jucs_15_14/optimal_serverless_networks_attacks
A network attack is a set of network elements that are disabled by an adversary. The goal for the attack is to produce the most possible damage to the network in terms of network connectivity by disabling the least possible number of network elements. We show that the problem of finding the optimal attack in a serverless network is NP-Complete even when only edges or nodes are considered for disabling. We study a node attack policy with polynomial complexity based on shorter paths and show that this attack policy outperforms in most cases classical attacks policies such as random attack or maximum degree attack. We also study the behavior of different network topologies under these attack policies.Aguirre, Carlos; Tsimring, Lev; Huerta, Ramon2010-11-15T11:10:15+01:00NP-complete attack strategiesnetwork connectivityoptimal attack problemOptimal Serverless Networks Attacks, Complexity and some Approximate AlgorithmsAguirre, CarlosTsimring, LevHuerta, RamonNP-complete attack strategies,network connectivity,optimal attack problemJUCS - Journal of Universal Computer Science Vol. 152009082747-2764Verlag der Technischen Universität GrazUniversiti Malaysia SarawakGraz, AustriaA Comparison Between a Geometrical and an ANN Based Method for Retinal Bifurcation Points Extraction
http://www.jucs.org/jucs_15_13/a_comparison_between_a
This paper describes a comparative study between an Artificial Neural Network (ANN) and a geometric technique to detect for biometric applications,the bifurcation points of blood vessels in the retinal fundus. The first step is an image preprocessing phase to extract retina blood vessels. The contrast of the blood vessels from the retinal image background is enhanced in order to extract the blood vessels skeleton. Successively, candidate points of bifurcation are individualized by approximating the skeleton lines in segments. The distinction between bifurcations and vessel bends is carried out through the employment of two methods: geometric (through the study of intersections within the region obtained thresholding the image portion inside a circle centered around the junctions point and the circumference of the same circle) and an ANN. The results obtained are compared and discussed.Troccoli, Antonella; Mastronardi, Giuseppe; Cariello, Lucia; Giannini, Marco; Scaramuzzi, Rocco; Santarcangelo, Vito; Bevilacqua, Vitoantonio2010-11-24T16:39:41+01:00ANNblood vessels detectionblood vessels skeletoncrossover points extractiongaussian derivationpersonal identificationpreprocessingretinal fundusA Comparison Between a Geometrical and an ANN Based Method for Retinal Bifurcation Points ExtractionTroccoli, AntonellaMastronardi, GiuseppeCariello, LuciaGiannini, MarcoScaramuzzi, RoccoSantarcangelo, VitoBevilacqua, VitoantonioANN,blood vessels detection,blood vessels skeleton,crossover points extraction,gaussian derivation,personal identification,preprocessing,retinal fundusJUCS - Journal of Universal Computer Science Vol. 152009072608-2621Verlag der Technischen Universität GrazUniversiti Malaysia SarawakGraz, AustriaInteractive Genetic Algorithms with Individual Fitness Not Assigned by Human
http://www.jucs.org/jucs_15_13/interactive_genetic_algorithms_with
Interactive genetic algorithms (IGAs) are effective methods to solve optimization problems with implicit or fuzzy indices. But human fatigue problem, resulting from evaluation on individuals and assignment of their fitness, is very important and hard to solve in IGAs. Aiming at solving the above problem, an interactive genetic algorithm with an individual fitness not assigned by human is proposed in this paper. Instead of assigning an individual fitness directly, we record time to choose an individual from a population as a satisfactory or unsatisfactory one according to sensitiveness to it, and its fitness is automatically calculated by a transformation from time space to fitness space. Then subsequent genetic operation is performed based on this fitness, and offspring is generated. We apply this algorithm to fashion design, and the experimental results validate its efficiency.Gong, Dunwei; Yuan, Jie; Yao, Xin2010-11-24T16:39:02+01:00genetic algorithmhuman fatigueindividual fitnessinteractive genetic algorithmoptimizationInteractive Genetic Algorithms with Individual Fitness Not Assigned by HumanGong, DunweiYuan, JieYao, Xingenetic algorithm,human fatigue,individual fitness,interactive genetic algorithm,optimizationJUCS - Journal of Universal Computer Science Vol. 152009072446-2462Verlag der Technischen Universität GrazUniversiti Malaysia SarawakGraz, AustriaOn the Effective Existence of Schauder Bases
http://www.jucs.org/jucs_15_6/on_the_effective_existence
We construct a computable Banach space which possesses a Schauder basis, but does not possess any computable Schauder basis.Bosserhoff, Volker2010-11-18T10:42:43+01:00Schauder basiscomputatable functional analysisOn the Effective Existence of Schauder BasesBosserhoff, VolkerSchauder basis,computatable functional analysisJUCS - Journal of Universal Computer Science Vol. 152009031145-1161Verlag der Technischen Universität GrazUniversiti Malaysia SarawakGraz, AustriaEffective Computability of Solutions of Differential Inclusions The Ten Thousand Monkeys Approach
http://www.jucs.org/jucs_15_6/effective_computability_of_solutions
In this paper we consider the computability of the solution of the initialvalue problem for differential equations and for differential inclusions with semicontinuous right-hand side. We present algorithms for the computation of the solution using the "ten thousand monkeys" approach, in which we generate all possible solution tubes, and then check which are valid. In this way, we show that the solution of a locally Lipschitz differential equation is computable even if the function is not effectively locally Lipschitz, and recover a result of Ruohonen, in which it is shown that if the solution is unique, then it is computable. We give an example of a computable locally Lipschitz function which is not effectively locally Lipschitz. We also show that the solutions of a convex-valued upper-semicontinuous differential inclusion are upper-semicomputable, and the solutions of a lower-semicontinuous one-sided Lipschitz differential inclusion are lower-semicomputable.Graça, Daniel S.; Collins, Pieter2010-11-18T10:42:39+01:00Lipschitz conditioncomputable analysisdifferential inclusionsordinary differential equationssemicomputabilityEffective Computability of Solutions of Differential Inclusions The Ten Thousand Monkeys ApproachGraça, Daniel S.Collins, PieterLipschitz condition,computable analysis,differential inclusions,ordinary differential equations,semicomputabilityJUCS - Journal of Universal Computer Science Vol. 152009031162-1185Verlag der Technischen Universität GrazUniversiti Malaysia SarawakGraz, AustriaChainable and Circularly Chainable Co-r.e. Sets in Computable Metric Spaces
http://www.jucs.org/jucs_15_6/chainable_and_circularly_chainable
We investigate under what conditions a co-recursively enumerable set <I>S</I> in a computable metric space (Χ, <I>d</I>, α) is recursive. The topological properties of <I>S</I> play an important role in view of this task. We first study some properties of computable metric spaces such as the effective covering property. Then we examine co-r.e. sets with disconnected complement, and finally we focus on study of chainable and circularly chainable continua which are co-r.e. as subsets of Χ. We prove that, under some assumptions on Χ, each co-r.e. circularly chainable continuum which is not chainable must be recursive. This means, for example, that each co-r.e. set in <b>R</b><I><sup>n</sup></I> or in the Hilbert cube which has topological type of the Warsaw circle or the dyadic solenoid must be recursive. We also prove that for each chainable continuum <I>S</I> which is decomposable and each ε > 0 there exists a recursive subcontinuum of <I>S</I> which is ε-close to <I>S</I>.Iljazović, Zvonko2010-11-18T10:42:30+01:00chainable continuumcircularly chainable continuumco-r.e. setcomputable metric spacerecursive setthe effective covering propertyChainable and Circularly Chainable Co-r.e. Sets in Computable Metric SpacesIljazović, Zvonkochainable continuum,circularly chainable continuum,co-r.e. set,computable metric space,recursive set,the effective covering propertyJUCS - Journal of Universal Computer Science Vol. 152009031206-1235Verlag der Technischen Universität GrazUniversiti Malaysia SarawakGraz, AustriaConstructive Urysohn Universal Metric Space
http://www.jucs.org/jucs_15_6/constructive_urysohn_universal_metric
We construct the Urysohn metric space in constructive setting without choice principles. The Urysohn space is a complete separable metric space which contains an isometric copy of every separable metric space, and any isometric embedding into it from a finite subspace of a separable metric space extends to the whole domain.Lešnik, Davorin2010-11-18T10:42:26+01:00Urysohn universal spaceconstructive mathematicsmetric spaceConstructive Urysohn Universal Metric SpaceLešnik, DavorinUrysohn universal space,constructive mathematics,metric spaceJUCS - Journal of Universal Computer Science Vol. 152009031236-1263Verlag der Technischen Universität GrazUniversiti Malaysia SarawakGraz, AustriaOn Finite-time Computability Preserving Conversions
http://www.jucs.org/jucs_15_6/on_finite_time_computability
A finite-time computable function is a partial function from ∑<sup>ω</sup> to ∑ <sup>ω</sup> whose value is constructed by concatenating a finite list with a suffix of the argument. A finite-time computability preserving conversion α : <I>X</I> → <I>Y</I> for <I>X</I>, <I>Y</I> ⊂ ∑<sup>ω</sup> is a bijection which preserves finite-time computability. We show that all the finite-time computability preserving conversions with the domain ∑<sup>ω</sup> are extended sliding block functions.Tsuiki, Hideki; Yamada, Shuji2010-11-18T10:41:54+01:00computable analysisconstant-time computable functionsdomain theoryfinite-time computable functionssliding block functionsOn Finite-time Computability Preserving ConversionsTsuiki, HidekiYamada, Shujicomputable analysis,constant-time computable functions,domain theory,finite-time computable functions,sliding block functionsJUCS - Journal of Universal Computer Science Vol. 152009031365-1380Verlag der Technischen Universität GrazUniversiti Malaysia SarawakGraz, AustriaElementary Computable Topology
http://www.jucs.org/jucs_15_6/elementary_computable_topology
We revise and extend the foundation of computable topology in the framework of Type-2 theory of effectivity, TTE, where continuity and computability on finite and infinite sequences of symbols are defined canonically and transferred to abstract sets by means of notations and representations. We start from a computable topological space, which is a T0-space with a notation of a base such that intersection is computable, and define a number of multi-representations of the points and of the open, the closed and the compact sets and study their properties and relations. We study computability of boolean operations. By merely requiring "provability" of suitable relations (element, non-empty intersection, subset) we characterize in turn computability on the points, the open sets (!), computability on the open sets, computability on the closed sets, the compact sets(!), and computability on the compact sets. We study modifications of the definition of a computable topological space that do not change the derived computability concepts. We study subspaces and products and compare a number of representations of the space of partial continuous functions. Since we are operating mainly with the base elements, which can be considered as regions for points ("pointless topology"), we study to which extent these regions can be filled with points (completions). We conclude with some simple applications including Dini's Theorem as an example.Weihrauch, Klaus; Grubba, Tanja2010-11-18T10:41:50+01:00computabilitycomputable analysistopologyElementary Computable TopologyWeihrauch, KlausGrubba, Tanjacomputability,computable analysis,topologyJUCS - Journal of Universal Computer Science Vol. 152009031381-1422Verlag der Technischen Universität GrazUniversiti Malaysia SarawakGraz, AustriaBayesian Gene Regulatory Network Inference Optimization by means of Genetic Algorithms
http://www.jucs.org/jucs_15_4/bayesian_gene_regulatory_network
Inferring gene regulatory networks from data requires the development of algorithms devoted to structure extraction. When time-course data is available, gene interactions may be modeled by a Bayesian Network (BN). Given a structure, that models the conditional independence between genes, we can tune the parameters in a way that maximize the likelihood of the observed data. The structure that best fit the observed data reflects the real gene network's connections. Well known learning algorithms (greedy search and simulated annealing) devoted to BN structure learning have been used in literature. We enhanced the fundamental step of structure learning by means of a classical evolutionary algorithm, named GA (Genetic algorithm), to evolve a set of candidate BN structures and found the model that best fits data, without prior knowledge of such structure. In the context of genetic algorithms, we proposed various initialization and evolutionary strategies suitable for the task. We tested our choices using simulated data drawn from a gene simulator, which has been used in the literature for benchmarking [Yu et al. (2002)]. We assessed the inferred models against this reference, calculating the performance indicators used for network reconstruction. The performances of the different evolutionary algorithms have been compared against the traditional search algorithms used so far (greedy search and simulated annealing). Finally we individuated as best candidate an evolutionary approach enhanced by Crossover-Two Point and Selection Roulette Wheel for the learning of gene regulatory networks with BN. We show that this approach outperforms classical structure learning methods in elucidating the original model of the simulated dataset. Finally we tested the GA approach on a real dataset where it reach 62% of recovered connections (sensitivity) and 64% of direct connections (precision), outperforming the other algorithms.Menolascina, Filippo; Mastronardi, Giuseppe; Romanazzi, Giuseppe; Pannarale, Paolo; Bevilacqua, Vitoantonio2010-11-15T15:59:50+01:00Bayesian networkgene networksgenetic algorithmsBayesian Gene Regulatory Network Inference Optimization by means of Genetic AlgorithmsMenolascina, FilippoMastronardi, GiuseppeRomanazzi, GiuseppePannarale, PaoloBevilacqua, VitoantonioBayesian network,gene networks,genetic algorithmsJUCS - Journal of Universal Computer Science Vol. 15200902826-839Verlag der Technischen Universität GrazUniversiti Malaysia SarawakGraz, AustriaPDE-PEDA: A New Pareto-Based Multi-objective Optimization Algorithm
http://www.jucs.org/jucs_15_4/pde_peda_a_new
Differential evolution (DE) algorithm puts emphasis particularly on imitating the microscopic behavior of individuals, while estimation of distribution algorithm (EDA) tries to estimate the probabilistic distribution of the entire population. DE and EDA can be extended to multi-objective optimization problems by using a Pareto-based approach, called Pareto DE (PDE) and Pareto EDA (PEDA) respectively. In this study, we describe a novel combination of PDE and PEDA (PDE-PEDA) for multi-objective optimization problems by taking advantage of the global searching ability of PEDA and the local optimizing ability of PDE, which can, effectively, maintain the balance between exploration and exploitation. The basic idea is that the offspring population of PDE-PEDA is composed of two parts, one part of the trial solution generated originates from PDE and the other part is sampled in the search space from the constructed probabilistic distribution model of PEDA. A scaling factor Pr used to balance contributions of PDE and PEDA can be adjusted in an on-line manner using a simulated annealing method. At an early evolutionary stage, a larger Pr should be adopted to ensure PEDA is used more frequently, whereas at later stage, a smaller Pr should be adopted to ensure that offspring is generated more often using PDE. The hybrid algorithm is evaluated on a set of benchmark problems and the experimental results show that PDE-PEDA outperforms the NSGA-II and PDE algorithms.Hao, Minglin; Lei, Ruhai; Wang, Xuesong; Cheng, Yuhu2010-11-15T15:59:21+01:00Pareto differential evolutionPareto estimation of distribution algorithmmulti-objective optimizationoffspring generation schemePDE-PEDA: A New Pareto-Based Multi-objective Optimization AlgorithmHao, MinglinLei, RuhaiWang, XuesongCheng, YuhuPareto differential evolution,Pareto estimation of distribution algorithm,multi-objective optimization,offspring generation schemeJUCS - Journal of Universal Computer Science Vol. 15200902722-741Verlag der Technischen Universität GrazUniversiti Malaysia SarawakGraz, AustriaLinear and Quadratic Complexity Bounds on the Values of the Positive Roots of Polynomials
http://www.jucs.org/jucs_15_3/linear_and_quadratic_complexity
In this paper we review the existing <I>linear</I> and <I>quadratic</I> complexity (upper) bounds on the values of the positive roots of polynomials and their impact on the performance of the Vincent-Akritas-Strzeboński (<tt>VAS</tt>) continued fractions method for the isolation of real roots of polynomials. We first present the following four linear complexity bounds (two "old" and two "<I>new</I>" ones, respectively): <I>C</I>auchy's, (<I>C</I>), <I>K</I>ioustelidis', (<I>K</I>), <I>F</I>irst-Lambda, (<I>FL</I>) and <I>L</I>ocal-<I>M</I>ax, (<I>LM</I>); we then state the quadratic complexity extensions of these four bounds, namely: <I>CQ</I>, <I>KQ</I>, <I>FLQ</I>, and <I>LMQ</I> — the second, (<I>KQ</I>), having being presented by Hong back in 1998. <I>All</I> eight bounds are derived from Theorem 5 below. The estimates computed by the quadratic complexity bounds are less than or equal to those computed by their linear complexity counterparts. Moreover, it turns out that <tt>VAS(lmq)</tt> — the <tt>VAS</tt> method implementing <I>LMQ</I> — is 40% faster than the original version <tt>VAS(cauchy)</tt>.Akritas, Alkiviadis G.2010-11-15T15:16:19+01:00Vincent's theorempositive rootsreal root isolationupper boundsLinear and Quadratic Complexity Bounds on the Values of the Positive Roots of PolynomialsAkritas, Alkiviadis G.Vincent's theorem,positive roots,real root isolation,upper boundsJUCS - Journal of Universal Computer Science Vol. 15200902523-537Verlag der Technischen Universität GrazUniversiti Malaysia SarawakGraz, AustriaA New Detection Method for Distributed Denial-of-Service Attack Traffic based on Statistical Test
http://www.jucs.org/jucs_15_2/a_new_detection_method
This study has proposed a new detection method for DDoS attack traffic based on two-sample t-test. We first investigate the statistics of normal SYN arrival rate (SAR) and confirm it follows normal distribution. The proposed method identifies the attack by testing 1) the difference between incoming SAR and normal SAR, and 2) the difference between the number of SYN and ACK packets. The experiment results show that the possibilities of both false positives and false negatives are very low. The proposed mechanism is also demonstrated to have the capability of detecting DDoS attack quickly.Chen, Chin-Ling2010-11-15T12:51:22+01:00network monitoringsecurity and protectionstatistical computingA New Detection Method for Distributed Denial-of-Service Attack Traffic based on Statistical TestChen, Chin-Lingnetwork monitoring,security and protection,statistical computingJUCS - Journal of Universal Computer Science Vol. 15200801488-504Verlag der Technischen Universität GrazUniversiti Malaysia SarawakGraz, AustriaConstructive Notions of Maximality for Ideals
http://www.jucs.org/jucs_14_22/constructive_notions_of_maximality
Working constructively, we discuss two types of maximality for ideals in a commutative ring with identity, showing also that the results are the best possible.Bridges, Douglas S.; Havea, Robin S.2009-08-07T09:14:54+02:00constructiveidealmaximalConstructive Notions of Maximality for IdealsBridges, Douglas S.Havea, Robin S.constructive,ideal,maximalJUCS - Journal of Universal Computer Science Vol. 142008123648-3657Verlag der Technischen Universität GrazUniversiti Malaysia SarawakGraz, AustriaSHARP Online: An Adaptive Hypermedia System Applied to Mathematical Problem Solving
http://www.jucs.org/jucs_14_19/sharp_online_an_adaptive
In this article we present the development of a web application called SHARP Online: An Adaptive Hypermedia System Applied to Mathematical Problem Solving. The pedagogical basis of this application is found in the support techniques for heuristic learning in mathematical problem solving developed according to the Schoenfeld model. The adaptivity of this tool is achieved by way of the utilization of an adaptive algorithm which has been developed for it and is described in this article. This algorithm implements mechanisms that make it possible for the user to construct mathematical knowledge adaptively using training methods. This application also provides the teacher with the following complete set of tools for managing the entire process: the inclusion of contents through a collaborative application with support; a shared work space; the adaptivity of the algorithm variables; and the supervision of the students' progress, etc. through specific modules. This application was originally developed for educational contexts in the area of teaching mathematics, and therefore includes a module for editing and visualizing mathematical formulas for a Web environment.Gil, Ana-Belén; García-Peñalvo, Francisco J.; Rodríguez, Raquel; López, Ricardo2009-08-06T15:11:30+02:00adaptive hypermediaheuristic thoughtinteractive learning environmentsteaching/learning strategiesuser-computer interactionSHARP Online: An Adaptive Hypermedia System Applied to Mathematical Problem SolvingGil, Ana-BelénGarcía-Peñalvo, Francisco J.Rodríguez, RaquelLópez, Ricardoadaptive hypermedia,heuristic thought,interactive learning environments,teaching/learning strategies,user-computer interactionJUCS - Journal of Universal Computer Science Vol. 142008113099-3113Verlag der Technischen Universität GrazUniversiti Malaysia SarawakGraz, AustriaGADYM - A Novel Genetic Algorithm in Mechanical Design Problems
http://www.jucs.org/jucs_14_15/gadym_a_novel_genetic
T his paper proposes a variant of genetic algorithm - GADYM, Genetic Algorithm with <I>Gender-Age structure, DYnamic parameter tuning and Mandatory self perfection scheme</I>. The motivation of this algorithm is to increase the diversity throughout the search procedure and to ease the difficulties associated with the tuning of GA parameters and operators. To promote diversity , GADYM combines the concept of gender and age in individuals of a traditional Genetic Algorithm and implements the self perfection scheme through sharing. To ease the parameter tuning process, the proposed algorithm uses dynamic environment in which heterogeneous crossover and selection techniques are used and parameters are updated based on deterministic rules. Thus, GADYM uses a combination of genetic operators and variable parameter values whereas a traditional GA uses fixed values of those. The experim ental results of the proposed algorithm based on a mechanical design problem show promising result.Tahera, Khadiza; Lochert, Paul B.; Ibrahim, Raafat N.2009-08-04T17:33:05+02:00genetic algorithmoptimizationsearchGADYM - A Novel Genetic Algorithm in Mechanical Design ProblemsTahera, KhadizaLochert, Paul B.Ibrahim, Raafat N.genetic algorithm,optimization,searchJUCS - Journal of Universal Computer Science Vol. 142008082566-2581Verlag der Technischen Universität GrazUniversiti Malaysia SarawakGraz, AustriaOptimal Sensor Network Layout Using Multi-Objective Metaheuristics
http://www.jucs.org/jucs_14_15/optimal_sensor_network_layout
Wireless Sensor Networks (WSN) allow, thanks to the use of small wireless devices known as sensor nodes, the monitorization of wide and remote areas with precision and liveness unseen to the date without the intervention of a human operator. For many WSN applications it is fundamental to achieve full coverage of the terrain monitored, known as <I>sensor field</I>. The next major concerns are the energetic efficiency of the network, in order to increase its lifetime, and having the minimum possible number of sensor nodes, in order to reduce the network cost. The task of placing the sensor nodes while addressing these objectives is known as WSN layout problem. In this paper we address a WSN layout problem instance in which full coverage is treated as a constraint while the other two objectives are optimized using a multiobjective approach. We employ a set of multi-objective optimization algorithms for this problem where we define the energy efficiency and the number of nodes as the independent optimization objectives. Our results prove the efficiency of multi-objective metaheuristics to solve this kind of problem and encourage further research on more realistic instances and more constrained scenarios.Talbi, El-Ghazali; Alba, Enrique; Molina, Guillermo2009-08-04T17:33:00+02:00metaheuristicsmultiobjective optimizationsensor networksOptimal Sensor Network Layout Using Multi-Objective MetaheuristicsTalbi, El-GhazaliAlba, EnriqueMolina, Guillermometaheuristics,multiobjective optimization,sensor networksJUCS - Journal of Universal Computer Science Vol. 142008082549-2565Verlag der Technischen Universität GrazUniversiti Malaysia SarawakGraz, AustriaA Hybrid Transgenetic Algorithm for the Prize Collecting Steiner Tree Problem
http://www.jucs.org/jucs_14_15/a_hybrid_transgenetic_algorithm
Evolutionary algorithms are effective search tools for tackling difficult optimization problems. In this paper an algorithm based on living processes where cooperation is the main evolutionary strategy is applied to the Prize Collecting Steiner Tree Problem, an NP-hard combinatorial optimization problem. The Transgenetic Algorithm presented here is hybridized with path-relinking. Computational results of an experiment performed with benchmark instances are reported. The results obtained for the Prize Collecting Steiner Tree Problem with the application of the hybrid Transgenetic Algorithm are compared with the results of three effective approaches presented previously. The computational experiment shows that the proposed approach is very competitive concerning both quality of solution and processing time.Schmidt, Cristine Cunha; Goldbarg, Elizabeth Ferreira Gouvêa; Goldbarg, Marco César2009-08-04T17:32:45+02:00Prize Collecting Steiner Tree Problemevolutionary algorithmpath-relinkingtransgenetic algorithmA Hybrid Transgenetic Algorithm for the Prize Collecting Steiner Tree ProblemSchmidt, Cristine CunhaGoldbarg, Elizabeth Ferreira GouvêaGoldbarg, Marco CésarPrize Collecting Steiner Tree Problem,evolutionary algorithm,path-relinking,transgenetic algorithmJUCS - Journal of Universal Computer Science Vol. 142008082491-2511Verlag der Technischen Universität GrazUniversiti Malaysia SarawakGraz, AustriaA Novel Multi-Layer Level Set Method for Image Segmentation
http://www.jucs.org/jucs_14_14/a_novel_multi_layer
In this paper, a new multi-layer level set method is proposed for multi-phase image segmentation. The proposed method is based on the conception of image layer and improved numerical solution of bimodal Chan-Vese model. One level set function is employed for curve evolution with a hierarchical form in sequential image layers. In addition, new initialization method and more efficient computational method for signed distance function are introduced. Moreover, the evolving curve can automatically stop on true boundaries in single image layer according to a termination criterion which is based on the length change of evolving curve. Specially, an adaptive improvement scheme is designed to speed up curve evolution process in a queue of sequential image layers, and the detection of background image layer is used to confirm the termination of the whole multi-layer level set evolution procedure. Finally, numerical experiments on some synthetic and real images have demonstrated the efficiency and robustness of our method. And the comparisons with multi-phase Chan-Vese method also show that our method has a less time-consuming computation and much faster convergence.Huang, De-Shuang; Wang, Xiao-Feng2009-10-23T13:30:06+02:00curve evolutionimage layerlevel setmulti-layersegmentationtermination criterionA Novel Multi-Layer Level Set Method for Image SegmentationHuang, De-ShuangWang, Xiao-Fengcurve evolution,image layer,level set,multi-layer,segmentation,termination criterionJUCS - Journal of Universal Computer Science Vol. 142008072427-2451Verlag der Technischen Universität GrazUniversiti Malaysia SarawakGraz, AustriaOn the Relationship between Filter Spaces and Weak Limit Spaces
http://www.jucs.org/jucs_14_6/on_the_relationship_between
Countably based filter spaces have been suggested in the 1970's as a model for recursion theory on higher types. Weak limit spaces with a countable base are known to be the class of spaces which can be handled by the Type-2 Model of Effectivity (TTE). We prove that the category of countably based proper filter spaces is equivalent to the category of countably based weak limit spaces. This result implies that filter spaces form yet another category from which the category of qcb-spaces inherits its cartesian closed structure. Moreover, we compare the aforementioned categories to other categories of spaces relevant to computability theory.Schröder, Matthias2008-09-18T13:07:38+02:00QCB-spacesconvenient categoriesequilogical spacesfilter spaceshigher type computationtopological spacesweak limit spacesOn the Relationship between Filter Spaces and Weak Limit SpacesSchröder, MatthiasQCB-spaces,convenient categories,equilogical spaces,filter spaces,higher type computation,topological spaces,weak limit spacesJUCS - Journal of Universal Computer Science Vol. 14200803996-1015Verlag der Technischen Universität GrazUniversiti Malaysia SarawakGraz, AustriaThe Bit-Complexity of Finding Nearly Optimal Quadrature Rules for Weighted Integration
http://www.jucs.org/jucs_14_6/the_bit_complexity_of
Given a probability measure ν and a positive integer <I>n</I>. How to choose <I>n</I> knots and <I>n</I> weights such that the corresponding quadrature rule has the minimum worst-case error when applied to approximate the ν-integral of Lipschitz functions? This question has been considered by several authors. We study this question whithin the framework of <I>Turing machine-based real computability and complexity theory</I> as put forward by [Ko 1991] and others. After having defined the notion of a <I>polynomialtime computable probability measure</I> on the unit interval, we will show that there are measures of this type for which there is no computable optimal rule with two knots. We furthermore characterize - in terms of difficult open questions in discrete complexity theory - the complexity of computing rules whose worst-case error is arbitrarily close to optimal.Bosserhoff, Volker2008-09-18T13:07:29+02:00quadrature rulesreal computational complexityThe Bit-Complexity of Finding Nearly Optimal Quadrature Rules for Weighted IntegrationBosserhoff, Volkerquadrature rules,real computational complexityJUCS - Journal of Universal Computer Science Vol. 14200803938-955Verlag der Technischen Universität GrazUniversiti Malaysia SarawakGraz, AustriaComputability of Topological Pressure for Sofic Shifts with Applications in Statistical Physics
http://www.jucs.org/jucs_14_6/computability_of_topological_pressure
The topological pressure of dynamical systems theory is examined from a computability theoretic point of view. It is shown that for sofic shift dynamical systems, the topological pressure is a computable function. This result is applied to a certain class of one dimensional spin systems in statistical physics. As a consequence, the specific free energy of these spin systems is computable. Finally, phase transitions of these systems are considered. It turns out that the critical temperature is recursively approximable.Spandl, Christoph2008-09-18T13:07:17+02:00Type-2 computabilityhift dynamical systemsstatistical physicstopological pressureComputability of Topological Pressure for Sofic Shifts with Applications in Statistical PhysicsSpandl, ChristophType-2 computability,hift dynamical systems,statistical physics,topological pressureJUCS - Journal of Universal Computer Science Vol. 14200803876-895Verlag der Technischen Universität GrazUniversiti Malaysia SarawakGraz, AustriaOn the Subrecursive Computability of Several Famous Constants
http://www.jucs.org/jucs_14_6/on_the_subrecursive_computability
For any class <I>F</I> of total functions in the set <B>N</B> of the natural numbers, we define the notion of <I>F</I>-computable real number. A real number α is called <I>F</I>-computable if there exist one-argument functions <I>f</I>, <I>g</I> and <I>h</I> in <I>F</I> such that for any <I>n</I> in <B>N</B> the distance between the rational number <I>f</I>(<I>n</I>) - <I>g</I>(<I>n</I>) over <I>h</I>(<I>n</I>) + 1 and the number α is not greater than the reciprocal of <I>n</I> + 1. Most concrete real numbers playing a role in analysis can be easily shown to be <I>E</I><sup>3</sup>-computable (as usually, <I>E</I><sup><I>m</I></sup> denotes the <I>m</I>-th Grzegorczyk class). Although (as it is proved in Section 5 of this paper) there exist <I>E</I><sup>3</sup>-computable real numbers that are not <I>E</I><sup>2</sup>-computable, we prove that π, <I>e</I> and other remarkable real numbers are <I>E</I><sup>2</sup>-computable (the number π proves to be even <I>L</I>-computable, where <I>L</I> is the class of Skolem's lower elementary functions). However, only the rational numbers would turn out to be <I>E</I><sup>2</sup>-computable according to a definition of <I>F</I>-computability using 2<sup><I>n</I></sup> instead of <I>n</I> + 1.Skordev, Dimiter2008-09-18T13:07:12+02:00Euler's constantGrzegorczyk classesLiouville's numbercomputable real numberlower elementary functionssecond Grzegorczyk classπ, eOn the Subrecursive Computability of Several Famous ConstantsSkordev, DimiterEuler's constant,Grzegorczyk classes,Liouville's number,computable real number,lower elementary functions,second Grzegorczyk class,π, eJUCS - Journal of Universal Computer Science Vol. 14200803861-875Verlag der Technischen Universität GrazUniversiti Malaysia SarawakGraz, AustriaDynamic Bandwidth Pricing: Provision Cost, Market Size, Effective Bandwidths and Price Games
http://www.jucs.org/jucs_14_5/dynamic_bandwidth_pricing_provision
Nowadays, in the markets of broadband access services, traditional contracts are of "static" type. Customers buy the right to use a specific amount of resources for a specific period of time. On the other hand, modern services and applications render the demand for bandwidth highly variable and bursty. New types of contracts emerge ("dynamic contracts") which allow customers to dynamically adjust their bandwidth demand. In such an environment, we study the case of a price competition situation between two providers of static and dynamic contracts. We investigate the resulting reaction curves, search for the existence of an equilibrium point and examine if and how the market is segmented between the two providers. Our first model considers simple, constant provision costs. We then extend the model to include costs that depend on the multiplexing capabilities that the contracts offer to the providers, taking into consideration the size of the market. We base our analysis on the theory of effective bandwidths and investigate the new conditions that allow the provider of dynamic contracts to enter the market.Courcoubetis, Costas; Weber, Richard; Soursos, Sergios2008-09-17T15:04:38+02:00bandwidth on demandcompetitioncontractseffective bandwidthsnetwork economicspricingprovision costreaction curvesstatistical multiplexingDynamic Bandwidth Pricing: Provision Cost, Market Size, Effective Bandwidths and Price GamesCourcoubetis, CostasWeber, RichardSoursos, Sergiosbandwidth on demand,competition,contracts,effective bandwidths,network economics,pricing,provision cost,reaction curves,statistical multiplexingJUCS - Journal of Universal Computer Science Vol. 14200803766-785Verlag der Technischen Universität GrazUniversiti Malaysia SarawakGraz, AustriaOptimal Transit Price Negotiation: The Distributed Learning Perspective
http://www.jucs.org/jucs_14_5/optimal_transit_price_negotiation
We present a distributed learning algorithm for optimizing transit prices in the inter-domain routing framework. We present a combined game theoretical and distributed algorithmic analysis, where the notion of Nash equilibrium with the first approach meets the notion of stability in the second. We show that providers can learn how to strategically set their prices according to a Nash equilibrium; even when assuming incomplete information. We validate our theoretical model by simulations confirming the expected outcome. Moreover, we observe that some unilateral deviations from the proposed rule do not seem to affect the dynamic of the system.Hamlaoui, Chahinez; Barth, Dominique; Echabbi, Loubna2008-09-17T15:04:34+02:00games with incomplete informationinterdomain priceslearningstabilityOptimal Transit Price Negotiation: The Distributed Learning PerspectiveHamlaoui, ChahinezBarth, DominiqueEchabbi, Loubnagames with incomplete information,interdomain prices,learning,stabilityJUCS - Journal of Universal Computer Science Vol. 14200803745-765Verlag der Technischen Universität GrazUniversiti Malaysia SarawakGraz, AustriaA Linear Time Approximation Algorithm for Ruler Folding Problem
http://www.jucs.org/jucs_14_4/a_linear_time_approximation
A chain or <I>n</I>-link is a sequence of n links whose lengths are fixed and are joined together from their endpoints, free to turn about their endpoints, which act as joints. "<I>Ruler Folding Problem</I>", which is NP-Complete is to find the minimum length of the folded chain. The best linear approximation algorithm for it were proposed by Hopcroft et al. Their algorithm folds any open chain in the interval whose length is less than 2<I>m</I><sub>1</sub>, where <I>m</I><sub>1</sub> is the length of the longest link in the chain. We propose a linear time approximation algorithm using <I>O</I>(1) additional space. Our algorithm has lower upper bound for the length of the folded chain which is max<img height=23 width=186 src="/jucs_14_4/a_linear_time_approximation/images/img1.jpg">, where <I>m</I><sub>1</sub> and <I>m</I><sub>2</sub>are the lengths of the two distinct maximum length links in the chain respectively, and <I>k</I> is the number of links whose lengths are <I>m</I><sub>1</sub> in the chain. Hence it is the best known approximation algorithm for "<I>Ruler Folding Problem</I>".Nourollah, Ali; Razzazi, Mohammadreza2008-09-17T14:40:05+02:00Carpenter's RulerRuler Folding Problemapproximation algorithmsA Linear Time Approximation Algorithm for Ruler Folding ProblemNourollah, AliRazzazi, MohammadrezaCarpenter's Ruler,Ruler Folding Problem,approximation algorithmsJUCS - Journal of Universal Computer Science Vol. 14200802566-574Verlag der Technischen Universität GrazUniversiti Malaysia SarawakGraz, AustriaOptimizing Assignment of Knowledge Workers to Office Space Using Knowledge Management Criteria<BR>The Flexible Office Case
http://www.jucs.org/jucs_14_4/optimizing_assignment_of_knowledge
Even though knowledge management has been around for more than a decade, so far concrete instruments that can be systematically deployed are still rare. This paper presents an optimization solution targeted at flexible management of office space considering knowledge management criteria in order to enhance knowledge work productivity. The paper presents the Flexible Office conceptual model and optimization solution. It discusses the theoretical foundation, assumptions and reasoning. A corresponding prototype was field-tested, successfully introduced, evaluated with the help of a series of interviews with users and improved according to their requirements. The paper also reflects on the organizational impact and lessons learned from field test and practical experience.Sandow, Alexander; Bayer, Florian; Nitz, Hendrik; Krüger, Michael; Maier, Ronald; Thalmann, Stefan2008-09-17T14:39:23+02:00flexibility, hypertext organizationknowledge managementknowledge workoffice spaceoptimizationOptimizing Assignment of Knowledge Workers to Office Space Using Knowledge Management Criteria<BR>The Flexible Office CaseSandow, AlexanderBayer, FlorianNitz, HendrikKrüger, MichaelMaier, RonaldThalmann, Stefanflexibility, hypertext organization,knowledge management,knowledge work,office space,optimizationJUCS - Journal of Universal Computer Science Vol. 14200802508-525Verlag der Technischen Universität GrazUniversiti Malaysia SarawakGraz, Austria