JUCS - Journal of Universal Computer Science - Theory of Computation
http://www.jucs.org/jucs_articles_by_category/F.
JUCS Topic F. - Theory of ComputationVerlag der Technischen Universität GrazUniversiti Malaysia Sarawak2011-07-28T11:21:46+02:00Hierarchical Graph-Grammar Model for Secure and Efficient Handwritten Signatures Classification
http://www.jucs.org/jucs_17_6/hierarchical_graph_grammar_model
One important subject associated with personal authentication capabilities is the analysis of handwritten signatures. Among the many known techniques, algorithms based on linguistic formalisms are also possible. However, such techniques require a number of algorithms for intelligent image analysis to be applied, allowing the development of new solutions in the field of personal authentication and building modern security systems based on the advanced recognition of such patterns. The article presents the approach based on the usage of syntactic methods for the static analysis of handwritten signatures. The graph linguistic formalisms applied, such as the IE graph and ETPL(k) grammar, are characterised by considerable descriptive strength and a polynomial membership problem of the syntactic analysis. For the purposes of representing the analysed handwritten signatures, new hierarchical (two-layer) HIE graph structures based on IE graphs have been defined. The two-layer graph description makes it possible to take into consideration both local and global features of the signature. The usage of attributed graphs enables the storage of additional semantic information describing the properties of individual signature strokes. The verification and recognition of a signature consists in analysing the affiliation of its graph description to the language describing the specimen database. Initial assessments display a precision of the method at a average level of under 75%.Piekarczyk, Marcin; Ogiela, Marek R.2011-07-04T16:04:47+02:00biometric securityhandwritten signature verificationhierarchical attributed random graphintelligent computingsecure verificationsignature-based authenticationHierarchical Graph-Grammar Model for Secure and Efficient Handwritten Signatures ClassificationPiekarczyk, MarcinOgiela, Marek R.biometric security,handwritten signature verification,hierarchical attributed random graph,intelligent computing,secure verification,signature-based authenticationJUCS - Journal of Universal Computer Science Vol. 17201103926-943Verlag der Technischen Universität GrazUniversiti Malaysia SarawakGraz, AustriaDescriptional Complexity of Ambiguity in Symmetric Difference NFAs
http://www.jucs.org/jucs_17_6/descriptional_complexity_of_ambiguity
We investigate ambiguity for symmetric difference nondeterministic finite automata. We show the existence of unambiguous, finitely ambiguous, polynomially ambiguous and exponentially ambiguous symmetric difference nondeterministic finite automata. We show that, for each of these classes, there is a family of n-state nondeterministic finite automata such that the smallest equivalent deterministic finite automata have <I>O</I>(2<I><sup>n</sup></I>) states.Geldenhuys, Jaco; Zijl, Lynette van2011-07-04T16:04:44+02:00ambiguitynondeterminismsuccinctnessDescriptional Complexity of Ambiguity in Symmetric Difference NFAsGeldenhuys, JacoZijl, Lynette vanambiguity,nondeterminism,succinctnessJUCS - Journal of Universal Computer Science Vol. 17201103874-890Verlag der Technischen Universität GrazUniversiti Malaysia SarawakGraz, AustriaNondeterministic Query Algorithms
http://www.jucs.org/jucs_17_6/nondeterministic_query_algorithms
Query algorithms are used to compute Boolean functions. The definition of the function is known, but input is hidden in a black box. The aim is to compute the function value using as few queries to the black box as possible. As in other computational models, different kinds of query algorithms are possible: deterministic, probabilistic, as well as nondeterministic. In this paper, we present a new alternative definition of nondeterministic query algorithms and study algorithm complexity in this model. We demonstrate the power of our model with an example of computing the Fano plane Boolean function. We show that for this function the difference between deterministic and nondeterministic query complexity is 7<I><sup>N</sup></I> versus <I>O</I>(3<I><sup>N</sup></I>).Vasilieva, Alina; Freivalds, Rūsiņš2011-07-04T16:04:43+02:00Boolean functionalgorithm complexitydecision treenondeterministic query algorithmNondeterministic Query AlgorithmsVasilieva, AlinaFreivalds, RūsiņšBoolean function,algorithm complexity,decision tree,nondeterministic query algorithmJUCS - Journal of Universal Computer Science Vol. 17201103859-873Verlag der Technischen Universität GrazUniversiti Malaysia SarawakGraz, AustriaXML Database Transformations
http://www.jucs.org/jucs_16_20/xml_database_transformations
Database transformations provide a unifying umbrella for queries and updates. In general, they can be characterised by five postulates, which constitute the database analogue of Gurevich's sequential ASM thesis. Among these postulates the background postulate supposedly captures the particularities of data models and schemata. For the characterisation of XML database transformations the natural first step is therefore to define the appropriate tree-based backgrounds, which draw on hereditarily finite trees, tree algebra operations, and extended document type definitions. This defines a computational model for XML database transformation using a variant of Abstract State Machines. Then the incorporation of weak monadic second-order logic provides an alternative computational model called XML machines. The main result is that these two computational models for XML database transformations are equivalent.Schewe, Klaus-Dieter; Wang, Qing2011-01-31T10:32:41+01:00Abstract State MachineMonadic Second-order LogicTree Algebracomputation backgrounddatabase transformationeXtensible Markup LanguageXML Database TransformationsSchewe, Klaus-DieterWang, QingAbstract State Machine,Monadic Second-order Logic,Tree Algebra,computation background,database transformation,eXtensible Markup LanguageJUCS - Journal of Universal Computer Science Vol. 162010113043-3072Verlag der Technischen Universität GrazUniversiti Malaysia SarawakGraz, AustriaProviding a Proof-Theoretical Basis for Explanation: A Case Study on UML and <I>ALCQI</I> Reasoning
http://www.jucs.org/jucs_16_20/providing_a_proof_theoretical
In this article we argue in favour of Natural Deduction Systems as a basis for formal proof explanations. We illustrate our choice presenting a Natural Deduction for <I>ALCQI</I> and use it to help explain UML reasoning.Rademaker, Alexandre; Haeusler, Edward Hermann2011-01-31T10:32:36+01:00ALCALCQIDescription LogicsProof TheorySequent CalculusUMLnatural deductionProviding a Proof-Theoretical Basis for Explanation: A Case Study on UML and <I>ALCQI</I> ReasoningRademaker, AlexandreHaeusler, Edward HermannALC,ALCQI,Description Logics,Proof Theory,Sequent Calculus,UML,natural deductionJUCS - Journal of Universal Computer Science Vol. 162010113016-3042Verlag 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, AustriaA Note on Closed Subsets in Quasi-zero-dimensional Qcb-spaces
http://www.jucs.org/jucs_16_18/a_note_on_closed
We introduce the notion of quasi-zero-dimensionality as a substitute for the notion of zero-dimensionality, motivated by the fact that the latter behaves badly in the realm of qcb-spaces. We prove that the category <B>QZ</B> of quasi-zero-dimensional qcblt;sub>0lt;/sub>-spaces is cartesian closed. Prominent examples of spaces in <B>QZ</B> are the spaces of the Kleene-Kreisel continuous functionals equipped with the respective sequential topology. Moreover, we characterise some types of closed subsets of <B>QZ</B>-spaces in terms of their ability to allow extendability of continuous functions. These results are related to a problem in Computable Analysis.Schröder, Matthias2011-01-20T15:13:23+01:00Computable AnalysisExtendabilityQcb-spacesA Note on Closed Subsets in Quasi-zero-dimensional Qcb-spacesSchröder, MatthiasComputable Analysis,Extendability,Qcb-spacesJUCS - Journal of Universal Computer Science Vol. 162010092711-2732Verlag der Technischen Universität GrazUniversiti Malaysia SarawakGraz, AustriaHow Incomputable is Finding Nash Equilibria?
http://www.jucs.org/jucs_16_18/how_incomputable_is_finding
We investigate the Weihrauch-degree of several solution concepts from noncooperative game theory. While the consideration of Nash equilibria forms the core of our work, also pure and correlated equilibria, as well as various concepts of iterated strategy elimination, are dealt with. As a side result, the Weihrauch-degree of solving systems of linear inequalities is settled.Pauly, Arno2011-01-20T15:13:20+01:00Computable AnalysisDiscontinuityGame TheoryNash Equilibrium,Weihrauch-degreeHow Incomputable is Finding Nash Equilibria?Pauly, ArnoComputable Analysis,Discontinuity,Game Theory,Nash Equilibrium,,Weihrauch-degreeJUCS - Journal of Universal Computer Science Vol. 162010092686-2710Verlag 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, AustriaRealisability for Induction and Coinduction with Applications to Constructive Analysis
http://www.jucs.org/jucs_16_18/realisability_for_induction_and
We prove the correctness of a formalised realisability interpretation of extensions of first-order theories by inductive and coinductive definitions in an untyped λ-calculus with fixed-points. We illustrate the use of this interpretation for program extraction by some simple examples in the area of exact real number computation and hint at further non-trivial applications in computable analysis.Berger, Ulrich2011-01-20T15:13:05+01:00coinductionconstructive analysisprogram extractionrealisabilityRealisability for Induction and Coinduction with Applications to Constructive AnalysisBerger, Ulrichcoinduction,constructive analysis,program extraction,realisabilityJUCS - Journal of Universal Computer Science Vol. 162010092535-2555Verlag der Technischen Universität GrazUniversiti Malaysia SarawakGraz, AustriaThe Separation of Relativized Versions of P and DNP for the Ring of the Reals
http://www.jucs.org/jucs_16_18/the_separation_of_relativized
We consider the uniform BSS model of computation where the machines can perform additions, multiplications, and tests of the form <I>x</I> ≥ 0. The oracle machines can also check whether a tuple of real numbers belongs to a given oracle set or not. We present oracle sets containing positive integers and pairs of numbers, respectively, such that the classes P and DNP relative to these oracles are not equal. The first set is constructed by diagonalization techniques and the second one is derived from the Knapsack Problem.Gaßner, Christine2011-01-20T15:12:56+01:00BSS modelbinary non-determinismdigital non-determinismoracle machinerelativizationsThe Separation of Relativized Versions of P and DNP for the Ring of the RealsGaßner, ChristineBSS model,binary non-determinism,digital non-determinism,oracle machine,relativizationsJUCS - Journal of Universal Computer Science Vol. 162010092563-2568Verlag 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, AustriaA Constructive Study of Landau's Summability Theorem
http://www.jucs.org/jucs_16_18/a_constructive_study_of
A summability theorem of Landau, which classically is a simple consequence of the uniform boundedness theorem, is examined within Bishop-style constructive mathematics. It is shown that the original theorem is nonconstructive, and that a natural weakening of the theorem is constructively equivalent to Ishihara's principle <B>BD-N</B>. The paper ends with a number of results that, while not as strong as Landau's theorem, nevertheless contain positive computational information related to its conclusion.Bridges, Douglas S.; Berger, Josef2011-01-20T15:12:42+01:00l_{p} spaceLandauconstructivesummabilityA Constructive Study of Landau's Summability TheoremBridges, Douglas S.Berger, Josefl_{p} space,Landau,constructive,summabilityJUCS - Journal of Universal Computer Science Vol. 162010092523-2534Verlag der Technischen Universität GrazUniversiti Malaysia SarawakGraz, AustriaMobile Agent-based Context-aware Services
http://www.jucs.org/jucs_16_15/mobile_agent_based_context
This paper presents an agent-based system for building and operating agent-basedcontext-aware services in public spaces, including museums. The system provides users with agents and detects the locations of users and deploys location-aware user-assistant agents at com-puters near the their current locations by using active RFID-tags. When a visitor moves between exhibits in a museum, this dynamically deploys his/her agent at the computers close to the ex-hibits by using mobile agent technology. It annotates the exhibits in his/her personalized form and navigate him/her user to the next exhibits along his/her routes. It also introduces user move-ment as a natural approach to interacting between users and agents. To demonstrate the utility and effectiveness of the system, we constructed location/user-aware visitor-guide services andexperimented them for two weeks in a public museum.Satoh, Ichiro2010-12-10T12:22:15+01:00RFIDcontext-aware servicemobile agentuser navigationMobile Agent-based Context-aware ServicesSatoh, IchiroRFID,context-aware service,mobile agent,user navigationJUCS - Journal of Universal Computer Science Vol. 162010081929-1952Verlag 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, AustriaGeometric Point Pattern Matching in the Knuth-Morris-Pratt Way
http://www.jucs.org/jucs_16_14/geometric_point_pattern_matching
Given finite sets <I>P</I> and <I>T</I> of points in the Euclidean space <B>R</B><I><sup>d</sup></I>, the point pattern matching problem studied in this paper is to find all translations <I>f</I> ∈ <B>R</B><I><sup>d</sup></I> such that <I>P</I> + <I>f</I> ⊆ <I>T</I>. A fast search algorithm with some variants is presented for point patterns <I>P</I> that have regular grid-like geometric shape. The algorithm is analogous to the Knuth-Morris-Pratt algorithm of string matching. The time requirement of the search is <I>O</I>(<I>r</I>|<I>T</I>|) where <I>r</I> is the grid dimension of <I>P</I>. Pattern <I>P</I> has grid dimension <I>r</I> = 1 if it consists of evenly spaced points on a line. In general, a pattern <I>P</I> is an <I>r</I>-dimensional grid if it has for some <I>p</I> ∈ <I>P</I> and <I>e</I>1, ... , <I>e<sub>r</sub></I> ∈ <B>R</B><I><sup>d</sup></I> and positive integers <I>m</I><sub>1</sub>, ... , <I>m<sub>r</sub></I> a representation <I>P</I> = {<I>p</I> + <I>i</I><sub>1</sub><I>e</I><sub>1</sub> + ⋅⋅⋅ + <I>i<sub>r</sub>e<sub>r</sub></I> | 0 ≤ <I>i<sub>j</sub></I> ≤ <I>m<sub>j</sub></I>} where the <I>i<sub>j</sub></I>'s are integers. Both <I>P</I> and <I>T</I> are given to the search algorithm in the lexicographic order.Ukkonen, Esko2010-10-18T09:27:07+02:00Knuth-Morris-Pratt algorithmpattern matchingpoint setstranslation,Geometric Point Pattern Matching in the Knuth-Morris-Pratt WayUkkonen, EskoKnuth-Morris-Pratt algorithm,pattern matching,point sets,translation,JUCS - Journal of Universal Computer Science Vol. 162010071902-1911Verlag 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, AustriaPICTAC: A Model for Perceiving Touch Interaction through Tagging Context
http://www.jucs.org/jucs_16_12/pictac_a_model_for
A natural interface is one of three key technologies of Ambient Intelligence (AmI); one of its main objectives is to minimize the user's interactive effort, which is the difficulty level that depends on the diversity and quantity of devices that surround people in existing environments. The worldwide penetration of mobile phones at present makes mobile phones excellent devices for delivering new services to users without requiring learning effort. An NFC-enabled mobile phone will allow a user to demand and obtain services by touching its different elements in a given smart environment. In this paper, we present a proposal in which we analyze the scope of touch interaction and develop a perceived touch interaction through tagging context (PICTAC) model.Chavira, Gabriel; Bravo, José; Rolón, Julio C.; Nava-Díaz, Salvador W.2010-09-17T17:52:43+02:00context awaretagging contexttouch interaction,ubiquitous computingPICTAC: A Model for Perceiving Touch Interaction through Tagging ContextChavira, GabrielBravo, JoséRolón, Julio C.Nava-Díaz, Salvador W.context aware,tagging context,touch interaction,,ubiquitous computingJUCS - Journal of Universal Computer Science Vol. 162010061577-1591Verlag der Technischen Universität GrazUniversiti Malaysia SarawakGraz, AustriaAn Axiomatization of a First-order Branching Time Temporal Logic
http://www.jucs.org/jucs_16_11/an_axiomatization_of_a
We introduce a first-order temporal logic for reasoning about branching time. It is well known that the set of valid formulas is not recursively enumerable and there is no finitary axiomatization. We offer a sound and strongly complete axiomatization for the considered logic.Doder, Dragan; Marković, Zoran; Ognjanović, Zoran2010-08-15T12:41:35+02:00branching time logicfirst order logicstrong completenessAn Axiomatization of a First-order Branching Time Temporal LogicDoder, DraganMarković, ZoranOgnjanović, Zoranbranching time logic,first order logic,strong completenessJUCS - Journal of Universal Computer Science Vol. 162010061439-1451Verlag der Technischen Universität GrazUniversiti Malaysia SarawakGraz, AustriaOn Succinct Representations of Textured Surfaces by Weighted Finite Automata
http://www.jucs.org/jucs_16_5/on_succinct_representations_of
Generalized finite automata with weights for states and transitions have been successfully applied to image generation for more than a decade now. Bilevel images (black and white), grayscale- or color-images and even video sequences can be effectively coded as weighted finite automata. Since each state represents a subimage within those automata the weighted transitions can exploit self-similarities for image compression. These "fractal" approaches yield remarkable results in comparison to the well-known standard JPEG- or MPEG-encodings and frequently provide advantages for images with strong contrasts. Here we will study the combination of these highly effective compression techniques with a generalization of weighted finite automata to higher dimensions, which establish d-dimensional relations between resultsets of ordinary weighted automata. For the applications we will restrict ourselves to three-dimensional Bezier spline-patches and to grayscale images as textures.Tischler, German; Albert, Jürgen2010-07-04T18:33:46+02:00Bezier splinesParametric Weighted Finite AutomataWeighted Finite Automatabicubic Bezier patchesimage compressionpolynomialsself-similaritytextured surfacesOn Succinct Representations of Textured Surfaces by Weighted Finite AutomataTischler, GermanAlbert, JürgenBezier splines,Parametric Weighted Finite Automata,Weighted Finite Automata,bicubic Bezier patches,image compression,polynomials,self-similarity,textured surfacesJUCS - Journal of Universal Computer Science Vol. 16201003586-603Verlag der Technischen Universität GrazUniversiti Malaysia SarawakGraz, AustriaNP-completeness and FPT Results for Rectilinear Covering Problems
http://www.jucs.org/jucs_16_5/np_completeness_and_ftp
This paper discusses three rectilinear (that is, axis-parallel) covering problems in <I>d</I> dimensions and their variants. The first problem is the RECTILINEAR LINE COVER where the inputs are <I>n</I> points in ℝ<I><sup>d</sup></I> and a positive integer <I>k</I>, and we are asked to answer if we can cover these <I>n</I> points with at most <I>k</I> lines where these lines are restricted to be axis parallel. We show that this problem has efficient fixed-parameter tractable (FPT) algorithms. The second problem is the RECTILINEAR <I>k</I>-LINKS SPANNING PATH PROBLEM where the inputs are also <I>n</I> points in ℝ<I><sup>d</sup></I> and a positive integer <I>k</I> but here we are asked to answer if there is a piecewise linear path through these <I>n</I> points having at most <I>k</I> line-segments (links) where these line-segments are axisparallel. We prove that this second problem is FPT under the assumption that no two line-segments share the same line. The third problem is the RECTILINEAR HYPERPLANE COVER problem and we are asked to cover a set of <I>n</I> points in <I>d</I> dimensions with <I>k</I> axis-parallel hyperplanes of <I>d</I> - 1 dimensions. We also demonstrate this has an FPT-algorithm. Previous to the results above, only conjectures were enunciated over several years on the NP-completeness of the RECTILINEAR MINIMUM LINK TRAVELING SALESMAN PROBLEM, the MINIMUM LINK SPANNING PATH PROBLEM and the RECTILINEAR HYPERPLANE COVER. We provide the proof that the RECTILINEAR MINIMUM LINK TRAVELING SALESMAN PROBLEM and the RECTILINEAR MINIMUM LINK SPANNING PATH PROBLEM are NP-complete by a reduction from the ONE-IN-THREE 3-SAT problem. The NP-completeness of the RECTILINEAR HYPERPLANE COVER problem is proved by a reduction from 3-SAT. This suggests dealing with the intractability just discovered with fixed-parameter tractability. Moreover, if we extend our problems to a finite set of orientations, our approach proves these problems remain FPT.Heednacram, Apichat; Suraweera, Francis; Estivill-Castro, Vladimir2010-07-04T18:33:26+02:00computational geometryparameterized complexityrestricted orientationsNP-completeness and FPT Results for Rectilinear Covering ProblemsHeednacram, ApichatSuraweera, FrancisEstivill-Castro, Vladimircomputational geometry,parameterized complexity,restricted orientationsJUCS - Journal of Universal Computer Science Vol. 16201003622-652Verlag der Technischen Universität GrazUniversiti Malaysia SarawakGraz, AustriaOrthogonal Concatenation: Language Equations and State Complexity
http://www.jucs.org/jucs_16_5/orthogonal_concatenation_language_equations
A language <I>L</I> is the orthogonal concatenation of languages <I>L</I><sub>1</sub> and <I>L</I><sub>2</sub> if every word of <I>L</I> can be written in a unique way as a concatenation of a word in <I>L</I><sub>1</sub> and a word in <I>L</I><sub>2</sub>. The notion can be generalized for arbitrary language operations. We consider decidability properties of language orthogonality and the solvability of language equations involving the orthogonal concatenation operation. We establish a tight bound for the state complexity of orthogonal concatenation of regular languages.Salomaa, Kai; Daley, Mark; Domaratzki, Michael2010-07-04T18:33:17+02:00decidabilitylanguage equationslanguage operationsregular languagesstate complexityOrthogonal Concatenation: Language Equations and State ComplexitySalomaa, KaiDaley, MarkDomaratzki, Michaeldecidability,language equations,language operations,regular languages,state complexityJUCS - Journal of Universal Computer Science Vol. 16201003653-675Verlag 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, AustriaOn the Linear Number of Matching Substrings
http://www.jucs.org/jucs_16_5/on_the_linear_number
We study the number of matching substrings in the pattern matching problem. In general, there can be a quadratic number of matching substrings in the size of a given text. The linearizing restriction enables to find at most a linear number of matching substrings. We first explore two well-known linearizing restriction rules, the <I>longest-match</I> rule and the <I>shortest-match substring</I> search rule, and show that both rules give the same result when a pattern is an infix-free set even though they have different semantics. Then, we introduce a new linearizing restriction, the <I>leftmost nonoverlapping match</I> rule that is suitable for find-and-replace operations in text searching, and propose an efficient algorithm for the new rule when a pattern is described by a regular expression. We also examine the problem of obtaining the maximal number of non-overlapping matching substrings.Han, Yo-Sub2010-07-04T18:32:57+02:00Thompson automatalinearizing restrictionregular expression searchingstring pattern matchingOn the Linear Number of Matching SubstringsHan, Yo-SubThompson automata,linearizing restriction,regular expression searching,string pattern matchingJUCS - Journal of Universal Computer Science Vol. 16201003715-728Verlag der Technischen Universität GrazUniversiti Malaysia SarawakGraz, AustriaEntropy and Higher Moments of Information
http://www.jucs.org/jucs_16_5/entropy_and_higher_moments
The entropy of a finite probability space or, equivalently, a memoryless source is the average information content of an event. The fact that entropy is an expectation suggests that it could be quite important in certain applications to take into account higher moments of information and parameters derived from these like the variance or skewness. In this paper we initiate a study of the higher moments of information for sources without memory and sources with memory. We derive properties of these moments for information defined in the sense of Shannon and indicate how these considerations can be extended to include the concepts of information in the sense of Aczél or Rényi. For memoryless sources, these concepts are immediately supported by the usual definitions of moments; for general stationary sources, let alone general sources, no such applicable framework seems to exist; on the other hand, the special properties of stationary Markov sources suggest such definitions which are both, well-motivated and mathematically meaningful.Matthews, David E.; Jürgensen, Helmut2010-07-04T18:32:34+02:00entropyinformationmoments of informationvariance of informationEntropy and Higher Moments of InformationMatthews, David E.Jürgensen, Helmutentropy,information,moments of information,variance of informationJUCS - Journal of Universal Computer Science Vol. 16201003749-794Verlag der Technischen Universität GrazUniversiti Malaysia SarawakGraz, AustriaA Note on the P-completeness of Deterministic One-way Stack Language
http://www.jucs.org/jucs_16_5/a_note_on_the
The membership problems of both stack automata and nonerasing stack automata are shown to be complete for polynomial time.Lange, Klaus-Jörn2010-07-04T18:32:26+02:00automatacompletenesscomplexity classesgrammarsA Note on the P-completeness of Deterministic One-way Stack LanguageLange, Klaus-Jörnautomata,completeness,complexity classes,grammarsJUCS - Journal of Universal Computer Science Vol. 16201003795-799Verlag der Technischen Universität GrazUniversiti Malaysia SarawakGraz, AustriaOrdered Catenation Closures and Decompositions of Languages Related to a Language of Derick Wood
http://www.jucs.org/jucs_16_5/ordered_catenation_closures_and
We investigate the problem of decomposing a language into a catenation of nontrivial languages, none of which can be decomposed further. In many cases this leads to the operation of an <I>ordered catenation closure</I>, introduced in this paper. We study properties of this operation, as well as its iterations. Special emphasis is on laid on ordered catenation closures of finite languages. It is also shown that if an infinite language is a code or a length code, then its ordered catenation closure does not possess a finite decomposition of indecomposable factors.Salomaa, Arto2010-07-04T18:32:11+02:00codedecomposition of languagesfinite languageindecomposable languagelength codeordered catenation closureOrdered Catenation Closures and Decompositions of Languages Related to a Language of Derick WoodSalomaa, Artocode,decomposition of languages,finite language,indecomposable language,length code,ordered catenation closureJUCS - Journal of Universal Computer Science Vol. 16201003821-832Verlag der Technischen Universität GrazUniversiti Malaysia SarawakGraz, AustriaDetecting Market Trends by Ignoring It, Some Days
http://www.jucs.org/jucs_16_5/detecting_market_trends_by
The last k days of trading together tell the financial market trends. It may be inconceivable if we are told to ignore the 3rd, 6th, and 8th day, <I>a priori</I>. We introduce a novel approach to show exactly that - it pays to ignore some fixed days among the recent <I>k</I> days, fixed <I>a priori</I>,in order to minimize risk and maximize profit simultaneously. The theory developed here has direct implications to our common senses on how we should look at the financial market trends.Zou, Jessie Wenhui; (II), Ming Li; Deng, Xiaotie2010-07-04T18:31:45+02:00market trend predictionoptimal spaced seedsDetecting Market Trends by Ignoring It, Some DaysZou, Jessie Wenhui(II), Ming LiDeng, Xiaotiemarket trend prediction,optimal spaced seedsJUCS - Journal of Universal Computer Science Vol. 16201003852-861Verlag der Technischen Universität GrazUniversiti Malaysia SarawakGraz, AustriaDerick Wood's Publications
http://www.jucs.org/jucs_16_5/derick_woods_publications
This list of Derick Wood's publications has been collected from several sources; the bibliographic data have been verified and corrected or completed whenever possible. Technical reports or similar internal publications are not listed if the results of these were also published elsewhere; to generate a complete list of Derick's technical reports would be a major task. Electronic addresses of publications are only provided when the only means by which to access such a work is the internet.</P> <P>We thank Tom Neumann and Jasna Todorovic, students of Helmut Jürgensen, for compiling the initial lists. We also thank Maia Hoeberechts, then PhD student of Helmut Jürgensen, for her help with many aspects of the whole project.</P> <P>As Derick's publications span a vast variety of fields, we could not rely on just a few obvious sources, like the <I>Mathematical Reviews</I>, the <I>Zentralblatt für Mathematik und ihre Grenzgebiete</I> or the database at http://www.informatik.unitrier.de/~ley/db/index.html, but needed to search many other printed and electronic sources as well.Jürgensen, Helmut2010-07-04T18:31:32+02:00theory of computationDerick Wood's PublicationsJürgensen, Helmuttheory of computationJUCS - Journal of Universal Computer Science Vol. 16201003862-888Verlag 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, AustriaMulti-criteria Group Decision Support with Linguistic Variables in Long-term Scenarios for Belgian Energy Policy
http://www.jucs.org/jucs_16_1/multi_criteria_group_decision
Real world decisions often made in the presence of multiple, conflicting, and incommensurate criteria. Decision making requires multiple perspectives of different individuals as more decisions are made now in groups than ever before. This is particularly true when the decision environment becomes more complex such as sustainability policies study in environmental and energy sectors. Group decision making processes judgments or solutions for decision problems based on the input and feedback of multiple individuals. Multi-criteria decision and evaluation problems at tactical and strategic levels in practice involve fuzziness in terms of linguistic variables vis-à-vis criteria, weights, and decision maker judgments. Relevant alternatives or scenarios are evaluated according to a number of desired criteria. A fuzzy multi-criteria group decision software tool is developed to analyze long-term scenarios for Belgian energy policy in this paper.Ruan, Da; Laes, Erik; Meskens, Gaston; Zhang, Guangquan; Lu, Jie; Ma, Jun2011-07-20T09:12:16+02:00Fuzzy numbersenergy policyevaluation modelgroup decision supportlinguistic variablesmulti-criteria decision making (MCDM)Multi-criteria Group Decision Support with Linguistic Variables in Long-term Scenarios for Belgian Energy PolicyRuan, DaLaes, ErikMeskens, GastonZhang, GuangquanLu, JieMa, JunFuzzy numbers,energy policy,evaluation model,group decision support,linguistic variables,multi-criteria decision making (MCDM)JUCS - Journal of Universal Computer Science Vol. 16201001103-120Verlag der Technischen Universität GrazUniversiti Malaysia SarawakGraz, AustriaSome Views on Information Fusion and Logic Based Approaches in Decision Making under Uncertainty
http://www.jucs.org/jucs_16_1/some_views_on_information
Decision making under uncertainty is a key issue in information fusion and logic based reasoning approaches. The aim of this paper is to show noteworthy theoretical and applicational issues in the area of decision making under uncertainty that have been already done and raise new open research related to these topics pointing out promising and challenging research gaps that should be addressed in the coming future in order to improve the resolution of decision making problems under uncertainty.Ruan, Da; Liu, Jun; Martínez, Luis; Xu, Yang2011-07-20T09:12:09+02:00computing with wordsdecision makinginformation fusionlogicsuncertain information processinguncertaintySome Views on Information Fusion and Logic Based Approaches in Decision Making under UncertaintyRuan, DaLiu, JunMartínez, LuisXu, Yangcomputing with words,decision making,information fusion,logics,uncertain information processing,uncertaintyJUCS - Journal of Universal Computer Science Vol. 162010013-19Verlag 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, AustriaA Debugging System Based on Natural Semantics
http://www.jucs.org/jucs_15_14/a_debugging_system_based
Due to the absence of side effects, reasoning about functional programsis simpler than reasoning about their imperative counterparts. However, because of the absence of practical debuggers, finding bugs in lazy functional languages has beenmore complex until quite recently. One of the easiest to use Haskell debuggers is Hood. Its behavior is based on the concept of observation of intermediate data structures.However, although using Hood can be simple when observing some structures, it is known that it can be hard to understand how it works when dealing with complexsituations. In fact, the author of Hood recognizes that it is necessary to formalize its behavior to explain better what should be expected, and also to allow to check whetherthe different implementations work properly. </P><P> In this paper, we formalize the behavior of the Hood debugger by extending Sestoft'snatural semantics. Moreover, we also show how to derive an abstract machine including such debugging information. By doing so, we do not only provide a formal foundation,but we also provide an alternative method to implement debuggers. In fact, we have already made a prototype of the abstract machine presented in this paper.Encina, Alberto de la; Rubio, Fernando; Llana, Luis2010-11-15T11:10:37+01:00abstract machinesdebuggingparallel functional programmingsemanticsA Debugging System Based on Natural SemanticsEncina, Alberto de laRubio, FernandoLlana, Luisabstract machines,debugging,parallel functional programming,semanticsJUCS - Journal of Universal Computer Science Vol. 152009082836-2880Verlag der Technischen Universität GrazUniversiti Malaysia SarawakGraz, AustriaPetri Net Controlled Grammars: the Case of Special Petri Nets
http://www.jucs.org/jucs_15_14/petri_net_controlled_grammars
A <I>Petri net controlled grammar</I> is a context-free grammar equipped with a Petri net, whose transitions are labeled with rules of the grammar or the empty string, and the associated language consists of all terminal strings which can be derived in the grammar and the the sequence of rules in every terminal derivation corresponds to some occurrence sequence of transitions of the Petri net which is enabled at the initial marking and finished at a final marking of the net. We present some results on the generative capacity of such grammars so that the associated Petri nets are restricted to some known special classes of Petri nets.Dassow, Jürgen; Turaev, Sherzod2010-11-15T11:10:32+01:00Petri net controlled grammarsPetri netsgrammarsgrammars with regulated rewritingPetri Net Controlled Grammars: the Case of Special Petri NetsDassow, JürgenTuraev, SherzodPetri net controlled grammars,Petri nets,grammars,grammars with regulated rewritingJUCS - Journal of Universal Computer Science Vol. 152009082808-2835Verlag 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 New Short-term Power Load Forecasting Model Based on Chaotic Time Series and SVM
http://www.jucs.org/jucs_15_13/a_new_short_term
This paper presents a model for power load forecasting using support vector machine and chaotic time series. The new model can make more accurate prediction. In the past few years, along with power system privatization and deregulation, accurate forecast of electricity load has received increasing attention. According to the chaotic and non-linear characters of power load data, the model of support vector machines (SVM) based on chaotic time series has been established. The time series matrix has also been established according to the theory of phase-space reconstruction. The Lyapunov exponents, one important component of chaotic time series, are used to determine time delay and embedding dimension, the decisive parameters for SVM. Then support vector machines algorithm is used to predict power load. In order to prove the rationality of chosen dimension, another two random dimensions are selected to compare with the calculated dimension. And to prove the effectiveness of the model, BP algorithm is used to compare with the results of SVM. Findings show that the model is effective and highly accurate in the forecasting of short-term power load. It means that the model combined with SVM and chaotic time series learning system have more advantage than other models.Duan, Chunming; Niu, Dongxiao; Xing, Mian; Wang, Yongli2010-11-24T16:40:12+01:00Lyapunov exponentschaotic time seriesload forecastingparameter selectionsupport vector machineA New Short-term Power Load Forecasting Model Based on Chaotic Time Series and SVMDuan, ChunmingNiu, DongxiaoXing, MianWang, YongliLyapunov exponents,chaotic time series,load forecasting,parameter selection,support vector machineJUCS - Journal of Universal Computer Science Vol. 152009072726-2745Verlag der Technischen Universität GrazUniversiti Malaysia SarawakGraz, AustriaA Hammerstein-Wiener Recurrent Neural Network with Frequency-Domain Eigensystem Realization Algorithm for Unknown System Identification
http://www.jucs.org/jucs_15_13/a_hammerstein_wiener_recurrent
This paper presents a Hammerstein-Wiener recurrent neural network (HWRNN) with a systematic identification algorithm for identifying unknown dynamic nonlinear systems. The proposed HWRNN resembles the conventional Hammerstein-Wiener model that consists of a linear dynamic subsystem that is sandwiched in between two nonlinear static subsystems. The static nonlinear parts are constituted by feedforward neural networks with nonlinear functions and the dynamic linear part is approximated by a recurrent network with linear activation functions. The novelties of our network include: 1) the structure of the proposed recurrent neural network can be mapped into a state-space equation; and 2) the state-space equation can be used to analyze the characteristics of the identified network. To efficiently identify an unknown system from its input-output measurements, we have developed a systematic identification algorithm that consists of parameter initialization and online learning procedures. Computer simulations and comparisons with some existing models have been conducted to demonstrate the effectiveness of the proposed network and its identification algorithm.Wang, Jeen-Shing; Chen, Yi-Chung2010-11-24T16:39:30+01:00Hammerstein-Wiener modelparameter initializationparameter optimizationrecurrent neural networksA Hammerstein-Wiener Recurrent Neural Network with Frequency-Domain Eigensystem Realization Algorithm for Unknown System IdentificationWang, Jeen-ShingChen, Yi-ChungHammerstein-Wiener model,parameter initialization,parameter optimization,recurrent neural networksJUCS - Journal of Universal Computer Science Vol. 152009072547-2565Verlag der Technischen Universität GrazUniversiti Malaysia SarawakGraz, AustriaChecking Semantics Equivalence of MDA Transformations in Concurrent Systems
http://www.jucs.org/jucs_15_11/checking_semantics_equivalence_of
In a previous work we have proposed an extension to the four-layer MDAarchitecture promoting formal verification for semantics preserving model transformations. We analyzed semantics equivalence in transformations involving Platform Specific Models (PSM s). In this paper, considering concurrent systems domain, we show how this extended MDA architecture copes with the correctness verification of horizontal model transformations involving Platform Independent Models (PIM s). Our approach is supported by four formal techniques: behavioral equivalence relation, category the-ory, bisimulation and model-checking. This set of techniques allows the analysis of semantics equivalence between system model before and after transformation enablingthe decomposition of the system model into a set of concurrent sub-models, considered as components. The validation of our approach occurs in a net splitting operation,where PIM s are defined as Petri nets models according to the PNML metamodel with transformations representing formal operations in this domain.Costa, Aniko; Júnior, Antonio; Ramalho, Franklin; Figueiredo, Jorge; Gomes, Luis; Barbosa, Paulo2011-05-03T15:04:18+02:00MDAconcurrent systemsformal semanticspetri netstransformationsChecking Semantics Equivalence of MDA Transformations in Concurrent SystemsCosta, AnikoJúnior, AntonioRamalho, FranklinFigueiredo, JorgeGomes, LuisBarbosa, PauloMDA,concurrent systems,formal semantics,petri nets,transformationsJUCS - Journal of Universal Computer Science Vol. 152009062196-2224Verlag 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, AustriaOracles and Relativizations of the P =? NP Question for Several Structures
http://www.jucs.org/jucs_15_6/oracles_and_relativizations_of
We consider the uniform model of computation over any structure with two constants. For several structures, we construct oracles which imply that the relativized versions of P and NP are equal or are not equal. We construct universal oracles which imply the equality of the relativized versions of P and NP and we show that we lose the possibility to define these oracles recursively if we try to compress their elements to tuples of fixed length. Moreover we give new oracles for the BSS model in order to separate the classes P and NP relative to these oracles.Gaßner, Christine2010-11-18T10:42:34+01:00BSS machinesHalting ProblemP-NP problemoracle machinesrelativizationsOracles and Relativizations of the P =? NP Question for Several StructuresGaßner, ChristineBSS machines,Halting Problem,P-NP problem,oracle machines,relativizationsJUCS - Journal of Universal Computer Science Vol. 152009031186-1205Verlag 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, AustriaFine-computable Functions on the Unit Square and their Integral
http://www.jucs.org/jucs_15_6/fine_computable_functions_on
We discuss the integral and Fubini's Theorem for a Fine-computable function <I>F</I>(<I>x, y</I>) on the upper-right open unit square [0, 1) x [0,1). The core objective is Fine-computability of <I>f</I>(<I>x</I>) = ∫<sub> [0,1)</sub> <I>F</I>(<I>x,y</I>)<I>dy</I> as a function of <I>x</I> ∈ [0,1).Yasugi, Mariko; Mori, Takakazu; Tsujii, Yoshiki2010-11-18T10:42:22+01:00Fine-computable functionFubini's Theoremintegral operatorFine-computable Functions on the Unit Square and their IntegralYasugi, MarikoMori, TakakazuTsujii, YoshikiFine-computable function,Fubini's Theorem,integral operatorJUCS - Journal of Universal Computer Science Vol. 152009031264-1279Verlag der Technischen Universität GrazUniversiti Malaysia SarawakGraz, AustriaRepresenting Measurement Results
http://www.jucs.org/jucs_15_6/representing_measurement_results
To gain insight into the relationship between physical theories and computation, we examine the link between measurement devices and computers in the framework of TTE. Starting from a formal definition of a measurement procedure, different approaches to associate a representation with a measurement procedure are studied, and an equivalence class of representations suitable for representing the results of a measurement is defined for each measurement procedure.Pauly, Arno2010-11-18T10:42:18+01:00admissible representationcomputable analysiscomputation by physical devicesmeasurementnormal distributionRepresenting Measurement ResultsPauly, Arnoadmissible representation,computable analysis,computation by physical devices,measurement,normal distributionJUCS - Journal of Universal Computer Science Vol. 152009031280-1300Verlag der Technischen Universität GrazUniversiti Malaysia SarawakGraz, AustriaTopological Complexity of Blowup Problems
http://www.jucs.org/jucs_15_6/topological_complexity_of_blowup
Consider the initial value problem of the first-order ordinary differential equation <br> <IMG SRC="topological_complexity_of_blowup/images/img1.jpg"> <br> where the locally Lipschitz continuous function <IMG SRC="topological_complexity_of_blowup/images/img2.jpg"> with open domain and the initial datum (<I>t</I><sub>0</sub>, <I>x</I><sub>0</sub>) ∈ <IMG SRC="topological_complexity_of_blowup/images/img4.jpg"> are given. It is shown that the solution operator producing the maximal "time" interval of existence and the solution on it is computable. Furthermore, the topological complexity of the blowup problem is studied for functions <I>f</I> defined on the whole space. For each such function <I>f</I> the set <I>Z</I> of initial conditions (<I>t</I><sub>0</sub>, x<sub>0</sub>) for which the positive solution does not blow up in finite time is a <IMG SRC="topological_complexity_of_blowup/images/img3.jpg">-set. There is even a computable operator determining <I>Z</I> from <I>f</I>. For <I>l</I> ≥ 2 this upper <IMG SRC="topological_complexity_of_blowup/images/img3.jpg">-complexity bound is sharp. For <I>l</I> = 1 the blowup problem is simpler.Weihrauch, Klaus; Zhong, Ning; Rettinger, Robert2010-11-18T10:42:09+01:00Type-2 theoryblowupdifferential equationTopological Complexity of Blowup ProblemsWeihrauch, KlausZhong, NingRettinger, RobertType-2 theory,blowup,differential equationJUCS - Journal of Universal Computer Science Vol. 152009031301-1316Verlag der Technischen Universität GrazUniversiti Malaysia SarawakGraz, AustriaAn Effective Tietze-Urysohn Theorem for QCB-Spaces
http://www.jucs.org/jucs_15_6/an_effective_tietze_urysohn
The Tietze-Urysohn Theorem states that every continuous real-valued function defined on a closed subspace of a normal space can be extended to a continuous function on the whole space. We prove an effective version of this theorem in the Type Two Model of Effectivity (TTE). Moreover, we introduce for qcb-spaces a slightly weaker notion of normality than the classical one and show that this property suffices to establish an Extension Theorem for continuous functions defined on functionally closed subspaces. Qcb-spaces are known to form an important subcategory of the category <tt>Top</tt> of topological spaces. <tt>QCB</tt> is cartesian closed in contrast to <tt>Top</tt>.Schröder, Matthias2010-11-18T10:42:06+01:00Qcb-spacescomputable Analysistopological spacesAn Effective Tietze-Urysohn Theorem for QCB-SpacesSchröder, MatthiasQcb-spaces,computable Analysis,topological spacesJUCS - Journal of Universal Computer Science Vol. 152009031317-1336Verlag der Technischen Universität GrazUniversiti Malaysia SarawakGraz, AustriaComputing the Solution Operators of Symmetric Hyperbolic Systems of PDE
http://www.jucs.org/jucs_15_6/computing_the_solution_operators
We study the computability properties of symmetric hyperbolic systems of PDE <IMG SRC="computing_the_solution_operators/images/img1.jpg">, with the initial condition <IMG SRC="computing_the_solution_operators/images/img2.jpg"> = φ(<I>x</I><sub>1</sub>,...,<I>x<sub>m</sub></I>). Such systems first considered by K.O. Friedrichs can be used to describe a wide variety of physical processes. Using the difference equations approach, we prove computability of the operator that sends (for any fixed computable matrices <I>A</I>, <I>B</I><sub>1</sub>, ..., <I>B<sub>m</sub></I> satisfying certain conditions) any initial function φ ∈ <I>C<sup>p</I>+1</sup>(<I>Q</I>, ℝ<I><sup>n</sup></I>) (satisfying certain conditions), <I>p</I> ≥ 2, to the unique solution <B>u</B> ∈ <I>C</I><sup><I>p</sup></I>(<I>H</I>, ℝ<I><sup>n</sup></I>), where <I>Q</I> = [0,1]<sup><I>m</I></sup> and <I>H</I> is the nonempty domain of correctness of the system.Selivanova, Svetlana; Selivanov, Victor2010-11-18T10:41:59+01:00PDEcomputabilitydifference schemefinite-dimensional approximationhyperbolic systemmatrix pencilmetric spacenormstabilityComputing the Solution Operators of Symmetric Hyperbolic Systems of PDESelivanova, SvetlanaSelivanov, VictorPDE,computability,difference scheme,finite-dimensional approximation,hyperbolic system,matrix pencil,metric space,norm,stabilityJUCS - Journal of Universal Computer Science Vol. 152009031337-1364Verlag 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, AustriaA Quantum-Inspired Immune Algorithm for Hybrid Flow Shop with Makespan Criterion
http://www.jucs.org/jucs_15_4/a_quantum_inspired_immune
This paper presents a quantum-inspired immune algorithm (QIA) for Hybrid flow shop problems (HFSP) to minimize makespan. Since HFSP have been proved to be NP-hard in a strong sense when the objective is to minimize the makespan, an effective immune algorithm (IA) is used to solve the problems. IA is a kind of evolutional computation strategies, which is developed on the basis of a real immune mechanism in the human body, and has been employed to tackle complex scheduling problems and produce a reasonable manufacturing schedule. In order to achieve better results, the standard IA is combined with quantum algorithm (QA), which is based on Q-bit and uses quantum rotation gate to update. A real number representation is proposed to convert the Q-bit representation to job permutation for evaluating value of solutions. The proposed QIA can overcome the limitations of IA, quicken up convergence speed and improve the solution. Forty one benchmarks are examined to validate the efficiency of the proposed algorithm. The computational experiments show that the proposed QIA can also obtain both better and more robust results than IA and QA.Niu, Qun; Ma, Shiwei; Zhou, Taijin2010-11-15T15:59:34+01:00hybrid flow shop schedulingimmune algorithmquantum algorithmquantum rotation gateA Quantum-Inspired Immune Algorithm for Hybrid Flow Shop with Makespan CriterionNiu, QunMa, ShiweiZhou, Taijinhybrid flow shop scheduling,immune algorithm,quantum algorithm,quantum rotation gateJUCS - Journal of Universal Computer Science Vol. 15200902765-785Verlag 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 Characterisation of Coincidence Ideals for Complex Values
http://www.jucs.org/jucs_15_1/a_characterisation_of_coincidence
We investigate properties of coincidence ideals in subattribute lattices that occur in complex value datamodels, i.e. sets of subattributes, on which two complex values coincide. We let complex values be defined by constructors for records, sets, multisets, lists, disjoint union and optionality, i.e. the constructors cover the gist of all complex value data models. Such lattices carry the structure of a Brouwer algebra as long as the union-constructor is absent, and for this case sufficient and necessary conditions for coincidence ideals are already known. In this paper, we extend the characterisation of coincidence ideals to the most general case. The presence of the disjoint union constructor complicates all results and proofs significantly. The reason for this is that the union-constructor causes non-trivial restructuring rules to hold. The characterisation of coincidence ideal is of decisive importance for the axiomatisation of (weak) functional dependencies.Sali, Attila; Schewe, Klaus-Dieter2009-08-11T09:45:06+02:00coincidence idealcomplex valuesrestructuringA Characterisation of Coincidence Ideals for Complex ValuesSali, AttilaSchewe, Klaus-Dietercoincidence ideal,complex values,restructuringJUCS - Journal of Universal Computer Science Vol. 15200901304-354Verlag der Technischen Universität GrazUniversiti Malaysia SarawakGraz, AustriaGlobal Database Design based on Storage Space and Update Time Minimization
http://www.jucs.org/jucs_15_1/global_database_design_based
A common approach in designing relational databases is to start with a universal relation schema, which is then decomposed into multiple subschemas. A good choice of subschemas can be determined using integrity constraints defined on the schema, such as functional, multivalued or join dependencies.</P> <P>In this paper we propose and analyze a new normal form based on the idea of minimizing overall storage space and update costs, and as a consequence redundancy as well. This is in contrast to existing normal forms such as BCNF, 4NF or KCNF, which only characterize the absence of redundancy (and thus space and update time minimality) for a single schema. We show that our new normal form naturally extendexisting normal forms to multiple schemas, and provide an algorithm for computing decompositions.Köhler, Henning2009-08-11T09:44:53+02:00database designdependenciesnormal formuniversal relationGlobal Database Design based on Storage Space and Update Time MinimizationKöhler, Henningdatabase design,dependencies,normal form,universal relationJUCS - Journal of Universal Computer Science Vol. 15200901195-240Verlag der Technischen Universität GrazUniversiti Malaysia SarawakGraz, AustriaWeak Functional Dependencies: Full Propositional Expressiveness for the Database Practitioner
http://www.jucs.org/jucs_15_1/weak_functional_dependencies_full
We study inference systems of weak functional dependencies in relational and complex-value databases. Functional dependencies form a very common class of database constraints. Designers and administrators proficiently utilise them in everyday database practice. Functional dependencies correspond to the linear-time decidable fragment of Horn clauses in propositional logic. Weak functional dependencies take advantage of arbitrary clauses, and therefore represent full propositional reasoning about data in databases. Moreover, they can be specified in a way that is very similar to functional dependencies.</P> <P>In relational databases the class of weak functional dependencies is finitely axiomatisable and the associated implication problem is <I>coNP</I>-complete in general. Our first main result extends this axiomatisation to databases in which complex elements can be derived from atomic ones by finitely many nestings of record, list and disjoint union constructors. In particular, we construct two nested tuples that can serve as a counterexample relation for the implication of weak functional dependencies. We further apply this construction to show an equivalence to truth assignments that serve as counterexamples for the implication of propositional clauses. Hence, we characterise the implication of weak functional dependencies in complex-value databases in completely logical terms. Consequently, state-of-the-art SAT solvers can be applied to reason about weak functional dependencies in relational and complex-value databases.Link, Sebastian; Hartmann, Sven2009-08-11T09:44:44+02:00axiomatisationcomplex-value databasepropositional logicrelational databaseweak functional dependencyWeak Functional Dependencies: Full Propositional Expressiveness for the Database PractitionerLink, SebastianHartmann, Svenaxiomatisation,complex-value database,propositional logic,relational database,weak functional dependencyJUCS - Journal of Universal Computer Science Vol. 15200901112-156Verlag der Technischen Universität GrazUniversiti Malaysia SarawakGraz, AustriaReasoning about Nonblocking Concurrency
http://www.jucs.org/jucs_15_1/reasoning_about_nonblocking_concurrency
Verification of concurrent algorithms has been the focus of much research over a considerable period of time, and a variety of techniques have been developed that are suited to particular classes of algorithm, for example algorithms based on message passing or mutual exclusion. The development of <I>nonblocking</I> or <I>lock-free</I> algorithms, which rely only on hardware primitives such as Compare And Swap, present new challenges for verification, as they allow greater levels of currency and more complex interactions between processes. </P> <P>In this paper, we describe and compare two approaches to reasoning about nonblocking algorithms. We give a brief overview of the <I>simulation</I> approach we have used in previous work. We then give a more detailed description of an approach based on Lipton's <I>reduction</I> method, and illustrate it by verifying two versions of a shared counter and two versions of a shared stack. Both approaches work by transforming a concurrent execution into an equivalent sequentia-execution, but they differ in the way that executions are transformed and the way that transformations are justified.Groves, Lindsay2009-08-11T09:44:40+02:00atomicityconcurrencylinearisabilitylock-free algorithmsnonblocking algorithmsreductionshared memorysimulation relationverificationReasoning about Nonblocking ConcurrencyGroves, Lindsayatomicity,concurrency,linearisability,lock-free algorithms,nonblocking algorithms,reduction,shared memory,simulation relation,verificationJUCS - Journal of Universal Computer Science Vol. 1520090172-111Verlag der Technischen Universität GrazUniversiti Malaysia SarawakGraz, AustriaNon-Denumerable Infinitary Modal Logic
http://www.jucs.org/jucs_15_1/non_denumerable_infinitary_modal
Segerberg established an analogue of the canonical model theorem in modal logic for infinitary modal logic. However, the logics studied by Segerberg and Goldblatt are based on denumerable sets of pairs ‹Γ, α› of sets Γ of well-formed formulae and well-formed formulae α. In this paper I show how a generalisation of the infinite cut-rule used by Segerberg and Goldblatt enables the removal of the limitation to denumerable sets of sequents.Cresswell, Max J.2009-08-11T09:44:36+02:00canonical modelcut-ruleinfinitary modal logicuniform substitutionNon-Denumerable Infinitary Modal LogicCresswell, Max J.canonical model,cut-rule,infinitary modal logic,uniform substitutionJUCS - Journal of Universal Computer Science Vol. 1520090163-71Verlag der Technischen Universität GrazUniversiti Malaysia SarawakGraz, AustriaOn BCK Algebras - Part I.b: An Attempt to Treat Unitarily the Algebras of Logic. New Algebras
http://www.jucs.org/jucs_14_22/on_bck_algebras
Since all the algebras connected to logic have, more or less explicitely, an associated order relation, it follows that they have two presentations, dual to each other. We classify these dual presentations in "left" and "right" ones and we consider that, when dealing with several algebras in the same research, it is useful to present them unitarily, either as "left" algebras or as "right" algebras. In some circumstances, this choice is essential, for instance if we want to build the ordinal sum (product) between a BL algebra and an MV algebra. We have chosen the "left" presentation and several algebras of logic have been redefined as particular cases of BCK algebras.</P> <P>We introduce several new properties of algebras of logic, besides those usually existing in the literature, which generate a more refined classification, depending on the properties satisfied. In this work (Parts I-V) we make an exhaustive study of these algebras - with two bounds and with one bound - and we present classes of finite examples, in bounded case.</P> <P>In this Part I, divided in two because of its length, after surveying chronologically several algebras related to logic, as residuated lattices, Hilbert algebras, MV algebras, divisible residuated lattices, BCK algebras, Wajsberg algebras, BL algebras, MTL algebras, WNM algebras, IMTL algebras, NM algebras, we propose a methodology in two steps for the simultaneous work with them (the first part of Part I).</P> <P>We then apply the methodology, redefining those algebras as particular cases of reversed left-BCK algebras. We analyse among others the properties Weak Nilpotent Minimum and Double Negation of a bounded BCK(P) lattice, we introduce new corresponding algebras and we establish hierarchies (the subsequent part of Part I).Iorgulescu, Afrodita2009-08-07T09:15:03+02:00BCK algebraBCK(P) latticeBL algebraHertz algebraHeyting algebraHilbert algebraHájek(P) algebraIMTL algebraMTL algebraMV algebraNM algebraR0 algebraWNM algebraWajsberg algebradivisible BCK(P) latticegeneralized-BL algebrageneralized-MV algebrageneralized-Wajsberg algebrapocrimresiduated latticet-normweak-BL algebraOn BCK Algebras - Part I.b: An Attempt to Treat Unitarily the Algebras of Logic. New AlgebrasIorgulescu, AfroditaBCK algebra,BCK(P) lattice,BL algebra,Hertz algebra,Heyting algebra,Hilbert algebra,Hájek(P) algebra,IMTL algebra,MTL algebra,MV algebra,NM algebra,R0 algebra,WNM algebra,Wajsberg algebra,divisible BCK(P) lattice,generalized-BL algebra,generalized-MV algebra,generalized-Wajsberg algebra,pocrim,residuated lattice,t-norm,weak-BL algebraJUCS - Journal of Universal Computer Science Vol. 142008053686-3715Verlag 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, AustriaDisentangling Denotational Semantics Definitions
http://www.jucs.org/jucs_14_21/disentangling_denotational_semantics_definitions
Denotational semantics is a powerful technique to formally define programming languages. However, language constructs are not always orthogonal, so many semantic equations in a definition may have to be aware of unrelated constructs semantics. Current approaches for modularity in this formalism do not address this problem, providing, for this reason, tangled semantic definitions. This paper proposes an incremental approach for denotational semantic specifications, in which each step can either add new features or adapt existing equations, by means of a formal language based on function transformation and aspect weaving.Tirelo, Fabio; Saraiva, Joâo; Bigonha, Roberto S.2009-03-19T14:48:14+01:00aspect-oriented definitionsdenotational semanticsmodularitysemantics of programming languagesDisentangling Denotational Semantics DefinitionsTirelo, FabioSaraiva, JoâoBigonha, Roberto S.aspect-oriented definitions,denotational semantics,modularity,semantics of programming languagesJUCS - Journal of Universal Computer Science Vol. 142008123592-3607Verlag der Technischen Universität GrazUniversiti Malaysia SarawakGraz, AustriaOn the Interaction of Advices and Raw Types in AspectJ
http://www.jucs.org/jucs_14_21/on_the_interaction_of
The latest versions of AspectJ, the most popular aspect-oriented extension for Java, must cope with the complex changes that occurred in the Java type system, specially with those that introduced type parameters for classes and methods. In this work we study the influence of raw types, i.e. parameterless instantiations of class types, over the semantics of an AspectJ-like language. As a result, we define an operational semantics and a type system for a calculus, named Raw Aspect Featherweight Generic Java (Raw-AFGJ), that represents a minimal aspect-oriented extension of Raw Featherweight Generic Java. Through our calculus it is possible to achieve a better understanding of several subtleties of aspect weaving with the restrictions imposed by raw types support in the type system.Nunes, Daltro Jé; Rubbo, Fernando Barden; Ribeiro, Leila; Machado, Rodrigo; Moreira, Álvaro Freitas2009-03-19T14:47:58+01:00aspect-oriented programmingoperational semantics,type systemsOn the Interaction of Advices and Raw Types in AspectJNunes, Daltro JéRubbo, Fernando BardenRibeiro, LeilaMachado, RodrigoMoreira, Álvaro Freitasaspect-oriented programming,operational semantics,,type systemsJUCS - Journal of Universal Computer Science Vol. 142008123534-3555Verlag der Technischen Universität GrazUniversiti Malaysia SarawakGraz, AustriaAn LALR Parser Generator Supporting Conflict Resolution
http://www.jucs.org/jucs_14_21/an_lalr_parser_generator
Despite all the advance brought by LALR parsing method by DeRemer in the late 60's, conflicts continue to be removed in a non-productive way, by means of analysis of a huge amount of textual and low level data dumped by the parser generator tool. For the purpose of changing this scenario, we present a parser generator capable of automatically removing some types of conflicts, along with a supported methodology that guides the process of manual removal. We also discuss the internal algorithms and how the created parsers are compact in terms of memory usage.Passos, Leonardo Teixeira; Bigonha, Mariza A. S.; Bigonha, Roberto S.2009-03-19T14:47:36+01:00automatic conflict removallalr parsingmethodologytable compressionAn LALR Parser Generator Supporting Conflict ResolutionPassos, Leonardo TeixeiraBigonha, Mariza A. S.Bigonha, Roberto S.automatic conflict removal,lalr parsing,methodology,table compressionJUCS - Journal of Universal Computer Science Vol. 142008123447-3464Verlag der Technischen Universität GrazUniversiti Malaysia SarawakGraz, AustriaShortcut Fusion of Monadic Programs
http://www.jucs.org/jucs_14_21/shortcut_fusion_of_monadic
Functional programs often combine separate parts of the program using intermediate data structures for communicating results. Programs so defined are easier to understand and maintain, but suffer from inefficiency problems due to the generation of those data structures. In response to this problematic, some program transformation techniques have been studied with the aim to eliminate the intermediate data structures that arise in function compositions. One of these techniques is known as shortcut fusion. This technique has usually been studied in the context of purely functional programs. In this work we propose an extension of shortcut fusion that is able to eliminate intermediate data structures generated in the presence of monadic effects. The extension to be presented can be uniformly defined for a wide class of data types and monads.Pardo, Alberto; Manzino, Cecilia2009-03-19T14:47:31+01:00computational effectsfunctional programmingmonadsshortcut fusionShortcut Fusion of Monadic ProgramsPardo, AlbertoManzino, Ceciliacomputational effects,functional programming,monads,shortcut fusionJUCS - Journal of Universal Computer Science Vol. 142008123431-3446Verlag der Technischen Universität GrazUniversiti Malaysia SarawakGraz, AustriaA Tool for Reasoning about Qualitative Temporal Information: the Theory of S-languages with a Lisp Implementation
http://www.jucs.org/jucs_14_20/a_tool_for_reasoning
Reasoning about incomplete qualitative temporal information is an essential topic inmany artificial intelligence and natural language processing applications. In the domain of natural language processing for instance, the temporal analysis of a text yields a set of temporal relationsbetween events in a given linguistic theory. The problem is first to express events and any possible temporal relations between them, then to express the qualitative temporal constraints (as subsetsof the set of all possible temporal relations) and compute (or count) all possible temporal relations that can be deduced. For this purpose, we propose to use the formalism of S-languages, based onthe mathematical notion of S-arrangements with repetitions [Schwer, 2002]. In this paper, we present this formalism in detail and our implementation of it. We explain why Lisp is adequateto implement this theory. Next we describe a Common Lisp system SLS (for S-LanguageS)which implements part of this formalism. A graphical interface written using McCLIM, the free implementation of the CLIM specification, frees the potential user of any Lisp knowledge. Fullydeveloped examples illustrate both the theory and the implementation.Durand, Irène A.; Schwer, Sylviane R.2009-08-04T22:52:27+02:00LispS-languagesrelation algebrastemporal reasoningA Tool for Reasoning about Qualitative Temporal Information: the Theory of S-languages with a Lisp ImplementationDurand, Irène A.Schwer, Sylviane R.Lisp,S-languages,relation algebras,temporal reasoningJUCS - Journal of Universal Computer Science Vol. 142008113282-3306Verlag 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, AustriaParallel Strategies for Stochastic Evolution
http://www.jucs.org/jucs_14_15/parallel_strategies_for_stochastic
This paper discusses the parallelization of Stochastic Evolution (StocE) metaheuristic, for a distributed parallel environment. VLSI cell placement is used as an optimization problem. A comprehensive set of parallelization approaches are tested and an effective strategy is identified in terms of two underlying factors: workload division and the effect of parallelization on metaheuristic's search intelligence. The strategies are compared with parallelization of another similar evolutionary metaheuristic called Simulated Evolution (SimE). The role of the two mentioned underlying factors is discussed in parallelization of StocE.Khan, Khawar S.; Ali, Mustafa I.; Sait, Sadiq M.2009-08-04T17:32:39+02:00VLSI cell placementcluster computingcombinatorial optimizationparallel metaheuristicssimulated evolutionstochastic evolutionParallel Strategies for Stochastic EvolutionKhan, Khawar S.Ali, Mustafa I.Sait, Sadiq M.VLSI cell placement,cluster computing,combinatorial optimization,parallel metaheuristics,simulated evolution,stochastic evolutionJUCS - Journal of Universal Computer Science Vol. 142008082471-2490Verlag der Technischen Universität GrazUniversiti Malaysia SarawakGraz, AustriaWhat is Correctness of Security Protocols?
http://www.jucs.org/jucs_14_12/what_is_correctness_of
As soon as major protocol flaws were discovered empirically - a good luck that is not older than the early 1990s -- this title question came up to the world. It was soon realised that some notion of formal correctness was necessary to substantiate the confidence derived from informal analyses. But protocol correctness was born in a decade when security in general was only beginning to ferment. <P> Security protocols aim at a large variety of goals. This is partly due to the increasing domains where the protocols are finding an application, such as secure access to localarea network services, secure e-mail, e-commerce, public-key registration at certification authorities and so on. Also, several interpretations are possible about each goal. <P> Clearly, it is impossible to study protocol correctness profitably without a universal and unambiguous interpretation of its goals. What may be typical of security problems is that it is at least as important to state a detailed and appropriate model of threats that a secure system is meant to withstand. This has been a second and significant source of perhaps useless debates around many protocols. <P> These are certain to be some of the reasons why dozens of papers appeared about one, now popular, protocol attack in just a few years of the second half of the last decade. One of the protocol designers firmly refused those "findings" because his protocol had been conceived within a different threat model -- and perhaps for different goals -- from the one that the publications had been constructed upon. <P> It seems obvious that an ant may survive under a single sheet of paper but certainly will not under a hard-back bulky book. It should be clarified what an ant and a bulky book precisely are. With particular attention to similar issues, this position paper discusses some findings of the author's in the area of protocol formal analysis. Their significance mostly is methodical rather than specific for particular protocols. The paper then outlines the author's favourite tool, the Inductive Method, and concludes with a few open problems.Bella, Giampaolo2009-07-21T12:21:41+02:00inductive methodprotocol goalprotocol verificationthreat modelWhat is Correctness of Security Protocols?Bella, Giampaoloinductive method,protocol goal,protocol verification,threat modelJUCS - Journal of Universal Computer Science Vol. 142008062083-2107Verlag der Technischen Universität GrazUniversiti Malaysia SarawakGraz, Austria