The proceedings contain 78 papers. The topics discussed include: graphs from search engine queries;model-checking large finite-state systems and beyond;interaction and realizability;weighted nearest neighbor algorithm...
详细信息
ISBN:
(纸本)9783540695066
The proceedings contain 78 papers. The topics discussed include: graphs from search engine queries;model-checking large finite-state systems and beyond;interaction and realizability;weighted nearest neighbor algorithms for the graph exploration problems on cycles;straightening drawings of clustered hierarchical graphs;about the termination detection in the asynchronous message passing model;fast approximate point set matching for information retrieval;maximum rigid components as means for direction-based localization in sensor networks;generating high dimensional data and query sets;indexing factors with gaps;performance analysis of a multiagent architecture for passenger transportation;on efficient resource allocation in communication networks;multi-document summarization based on cluster using non-negative matrix factorization;and towards a versatile contract model to organize behavioral specifications.
The proceedings contain 40 papers. The special focus in this conference is on Foundations in computerscience, Semantics, Specification, Compositionality, theory of Mobile, Distributed Systems, Automated System Analys...
ISBN:
(纸本)9783319519623
The proceedings contain 40 papers. The special focus in this conference is on Foundations in computerscience, Semantics, Specification, Compositionality, theory of Mobile, Distributed Systems, Automated System Analysis, Scheduling Algorithms, Algorithms for Strings and Software Engineering. The topics include: Dependable and optimal cyber-physical systems;verifying parametric thread creation;a model for programmable matter;logical characterisations and compositionality of input-output conformance simulation;symbolic semantics for multiparty interactions in the link-calculus;deciding structural Liveness of Petri nets;distributed network generation based on preferential attachment in ABS;completeness of Hoare logic relative to the standard model;hardness of deriving invertible sequences from finite state machines;a graph-theoretical characterisation of state separation;selfish transportation games;decomposable relaxation for concurrent data structures;sufficient conditions for a connected graph to have a Hamiltonian path;enumerating minimal tropical connected sets;adjacent vertices can be hard to find by quantum walks;how to draw a planarization;parameterized and exact algorithms for class domination coloring;edit-distance between visibly pushdown languages;webpage menu detection based on DOM;eco-data warehouse design through logical variability;domain-specific languages;characterising malicious software with high-level behavioural patterns and using n-grams for the automated clustering of structural models.
Category theory unifies mathematical concepts, aiding comparisons across structures by incorporating not just objects, but also morphisms capturing interactions between objects. Of particular importance in some applic...
详细信息
Server logs of search engines store traces of queries submitted by users, which include queries themselves along with Web pages selected in their answers. Here we describe several graph-based relations among queries a...
详细信息
ISBN:
(纸本)9783540695066
Server logs of search engines store traces of queries submitted by users, which include queries themselves along with Web pages selected in their answers. Here we describe several graph-based relations among queries and many applications where these graphs could be used.
Restarting automata were introduced to model the linguistic concept of analysis by reduction. In recent years there was a growing effort to study classes of formal languages that are generated by different variants of...
详细信息
ISBN:
(纸本)9783540695066
Restarting automata were introduced to model the linguistic concept of analysis by reduction. In recent years there was a growing effort to study classes of formal languages that are generated by different variants of these automata. We follow this line of research and generalize the model to a more complex data structure: free term algebras (or trees). Many of the known results about restarting automata on strings carry over to the new model. We study the expressive power of restarting tree automata and prove some closure properties.
Interaction systems are a formal model for component-based systems. Combining components via connectors to form more complex systems may give rise to deadlock situations. Deciding the existence of deadlocks is NP-hard...
详细信息
ISBN:
(纸本)9783540695066
Interaction systems are a formal model for component-based systems. Combining components via connectors to form more complex systems may give rise to deadlock situations. Deciding the existence of deadlocks is NP-hard as it involves global state analysis. We present here a parametrized polynomial-time algorithm that is able to confirm deadlock-freedom for a certain class of interaction systems. The discussion includes characteristic examples and displays the role of the parameter of the algorithm.
This paper investigates the operational semantics of framed temporal logic programs. To this end, a framed temporal logic programming language called Framed Tempura is employed. The evaluation rules for both the arith...
详细信息
ISBN:
(纸本)9783540695066
This paper investigates the operational semantics of framed temporal logic programs. To this end, a framed temporal logic programming language called Framed Tempura is employed. The evaluation rules for both the arithmetic and boolean expressions are defined. The semantic equivalence rules for the reduction of a program within a state is formalized. Furthermore, the congruence and transition rules between configurations for the reduction of programs are also specified. Thus, the executable behavior of framed programs can be captured in an operational way. In addition, the consistency of the operational semantics and the minimal model semantics based on model theory is proved.
The dependency pair method is a powerful method for automatically proving termination of rewrite systems. When used with traditional simplification orders like LPO and KBO, argument filterings play a key role. In this...
详细信息
ISBN:
(纸本)9783540695066
The dependency pair method is a powerful method for automatically proving termination of rewrite systems. When used with traditional simplification orders like LPO and KBO, argument filterings play a key role. In this paper we propose an encoding of argument filterings in propositional logic. By incorporating propositional encodings of simplification orders, the search for suitable argument filterings is turned into a satisfiability problem. Preliminary experimental results show that our logic-based approach is significantly faster than existing implementations.
Computational social choice is an interdisciplinary field of study at the interface of social choice theory and computerscience, promoting an exchange of ideas in both directions. On the one hand, it is concerned wit...
详细信息
ISBN:
(纸本)9783540695066
Computational social choice is an interdisciplinary field of study at the interface of social choice theory and computerscience, promoting an exchange of ideas in both directions. On the one hand, it is concerned with the application of techniques developed in computerscience, such as complexity analysis or algorithm design, to the study of social choice mechanisms, such as voting procedures or fair division algorithms. On the other hand, computational social choice is concerned with importing concepts from social choice theory into computing. For instance, the study of preference aggregation mechanisms is also very relevant to multiagent systems. In this short paper we give a general introduction to computational social choice, by proposing a taxonomy of the issues addressed by this discipline, together with some illustrative examples and kin (incomplete) bibliography.
暂无评论