Abstract:
We show that the Parikh image of the language of an NFA with n states over an alphabet of size k can be described as a finite union of linear sets with at most k generators and total size 2^{O(k^2 log n)}, i.e., polynomial for all fixed k >= 1. Previously, it was not known whether the number of generators could be made independent of n, and best upper bounds on the total size were exponential in n. Furthermore, we give an algorithm for performing such a translation in time 2^{O(k^2 log(kn))}. Our proof exploits a previously unknown connection to the theory of convex sets, and establishes a normal form theorem for semilinear sets, which is of independent interests. To complement these results, we show that our upper bounds are tight and that the results cannot be extended to context-free languages. We give four applications: (1) a new polynomial fragment of integer programming, (2) precise complexity of membership for Parikh images of NFAs, (3) an answer to an open question about polynomial PAC-learnability of semilinear sets, and (4) an optimal algorithm for LTL model checking over discrete-timed reversal-bounded counter systems.

Abstract:
We point out a subtle error in the proof of Chrobak's theorem that every unary NFA can be represented as a union of arithmetic progressions that is at most quadratically large. We propose a correction for this and show how Martinez's polynomial time algorithm, which realizes Chrobak's theorem, can be made correct accordingly. We also show that Martinez's algorithm cannot be improved to have logarithmic space, unless L = NL.

Abstract:
By algorithmic metatheorems for a model checking problem P over infinite-state systems we mean generic results that can be used to infer decidability (possibly complexity) of P not only over a specific class of infinite systems, but over a large family of classes of infinite systems. Such results normally start with a powerful formalism of infinite-state systems, over which P is undecidable, and assert decidability when is restricted by means of an extra "semantic condition" C. We prove various algorithmic metatheorems for the problems of model checking LTL and its two common fragments LTL(Fs,Gs) and LTLdet over the expressive class of word/tree automatic transition systems, which are generated by synchronized finite-state transducers operating on finite words and trees. We present numerous applications, where we derive (in a unified manner) many known and previously unknown decidability and complexity results of model checking LTL and its fragments over specific classes of infinite-state systems including pushdown systems; prefix-recognizable systems; reversal-bounded counter systems with discrete clocks and a free counter; concurrent pushdown systems with a bounded number of context-switches; various subclasses of Petri nets; weakly extended PA-processes; and weakly extended ground-tree rewrite systems. In all cases,we are able to derive optimal (or near optimal) complexity. Finally, we pinpoint the exact locations in the arithmetic and analytic hierarchies of the problem of checking a relevant semantic condition and the LTL model checking problems over all word/tree automatic systems.

Abstract:
The orbit problem is at the heart of symmetry reduction methods for model checking concurrent systems. It asks whether two given configurations in a concurrent system (represented as finite strings over some finite alphabet) are in the same orbit with respect to a given finite permutation group (represented by their generators) acting on this set of configurations by permuting indices. It is known that the problem is in general as hard as the graph isomorphism problem, whose precise complexity (whether it is solvable in polynomial-time) is a long-standing open problem. In this paper, we consider the restriction of the orbit problem when the permutation group is cyclic (i.e. generated by a single permutation), an important restriction of the problem. It is known that this subproblem is solvable in polynomial-time. Our main result is a linear-time algorithm for this subproblem.

Abstract:
Graph data models have recently become popular owing to their applications, e.g., in social networks and the semantic web. Typical navigational query languages over graph databases - such as Conjunctive Regular Path Queries (CRPQs) - cannot express relevant properties of the interaction between the underlying data and the topology. Two languages have been recently proposed to overcome this problem: walk logic (WL) and regular expressions with memory (REM). In this paper, we begin by investigating fundamental properties of WL and REM, i.e., complexity of evaluation problems and expressive power. We first show that the data complexity of WL is nonelementary, which rules out its practicality. On the other hand, while REM has low data complexity, we point out that many natural data/topology properties of graphs expressible in WL cannot be expressed in REM. To this end, we propose register logic, an extension of REM, which we show to be able to express many natural graph properties expressible in WL, while at the same time preserving the elementariness of data complexity of REMs. It is also incomparable to WL in terms of expressive power.

Abstract:
We study the problem of deciding satisfiability of first order logic queries over views, our aim being to delimit the boundary between the decidable and the undecidable fragments of this language. Views currently occupy a central place in database research, due to their role in applications such as information integration and data warehousing. Our main result is the identification of a decidable class of first order queries over unary conjunctive views that generalises the decidability of the classical class of first order sentences over unary relations, known as the Lowenheim class. We then demonstrate how various extensions of this class lead to undecidability and also provide some expressivity results. Besides its theoretical interest, our new decidable class is potentially interesting for use in applications such as deciding implication of complex dependencies, analysis of a restricted class of active database rules, and ontology reasoning.

Abstract:
HTML5 applications normally have a large set of CSS (Cascading Style Sheets) rules for data display. Each CSS rule consists of a node selector (given in an XPath-like query language) and a declaration block (assigning values to selected nodes' display attributes). As web applications evolve, maintaining CSS files can easily become problematic. Some CSS rules will be replaced by new ones, but these obsolete (hence redundant) CSS rules often remain in the applications. Not only does this "bloat" the applications, but it also significantly increases web browsers' processing time. Most works on detecting redundant CSS rules in HTML5 applications do not consider the dynamic behaviors of HTML5 (specified in JavaScript); in fact, the only proposed method that takes these into account is dynamic analysis (a.k.a. testing), which cannot soundly prove redundancy of CSS rules. In this paper, we introduce an abstraction of HTML5 applications based on monotonic tree-rewriting and study its "redundancy problem". We establish the precise complexity of the problem and various subproblems of practical importance (ranging from P to EXP). In particular, our algorithm relies on an efficient reduction to an analysis of symbolic pushdown systems (for which highly optimised solvers are available), which yields a fast method for checking redundancy in practice. We implemented our algorithm and demonstrated its efficacy in detecting redundant CSS rules in HTML5 applications.

Abstract:
Recently, several strains of microalgae have been studied as they contain high lipid content capable to be converted to biodiesel. Fresh water microalgae Chlorella vulgaris studied in this research was one of the proof as it contained high triacyl glyceride which made it a potential candidate for biodiesel production. Factors responsible for good growing of microalgae such as CO2 and nitrogen concentration were investigated. It was found that total lipid content was increased after exposing to media with not enough nitrogen concentration. However, under this nitrogen depletion media, the growth rate was very slow leading to lower lipid productivity. The productivity could be increased by increasing CO2 concentration. The lipid content was found to be affected by drying temperature during lipid extraction of algal biomass. Drying at very low temperature under vacuum gave the best result but drying at 60oC slightly decreased the total lipid content.

Abstract:
Bamboo is one of the economic plant which grow widely in the villages and have been used by the local people in the villages. Indonesia has about 10% of the world bamboo, 50% among them was endemic to Indonesia. According Widjaja (2001) Lesser Sunda Island which consists of Lombok, Sumbawa, Flores, Timor, Sumba and other small island eastern of Flores has 14 bamboo species, however, the information from the Sumba Island was lacking because of lacking data from this area except one species which was proposed by S. Soenarko in 1977 where the type specimens was collected by Iboet 443 in 1925. To fullfill data from the Sumba Island, an exploration to this area has been conducted on July 2003. The observation was done in West Sumba and East Sumba District, especially in two natioal parks at both districts. According to this inventory study in the Sumba Island, there were 10 bamboo species in Sumba Island, 1 species among them (Dinochloa sp.) was a new species which has not been collected before, whereas the other species (Dinochloa kostermansiana) has a new addition record from this area. The bamboo species in Sumba Island were Bambusa blumeana, Bambusa vulgaris, Dendocalamus asper, Dinochloa kostermansiana, Dinochloa sp., Gigantochloa atter, Nastus reholtumianus, Phyllostachys aurea, Schisotachyum brachycladum and Schizostachyum lima. From 10 recorded species, the genera Dinochloa and Nastus grow wild in the forest, whereas another species grow widly or cultivated in the garden. Furthermore, the genus Dinochloa was the only genus grow climbing. The endemic species found in Sumba Island was Nastus reholttumianus, whereas Dinochloa kostermansiana was also found in Flores Island.

Abstract:
This research conducted a study on non-financial performance relationship with a financial performance. The framework used is the Balanced Scorecard. Non-financial performance is represented by faculty satisfaction, service quality and student satisfaction, while financial performance is represented by the financial sustainability. In this research, the data collection is done by distributing questionnaires to the faculty and students. The Partial Least Square for Multivariate Analysis is employed for processing the data. The result of this research is useful to be able to explore more deeply the relationship between each of the indicator whether non-financial and the financial sustainability.