Search

In an era of increasingly interconnected information, graph-structured data has become pervasive across numerous domains, from social media platforms and telecommunication networks to biological systems and knowledge graphs. However, traditional database management systems often struggle when confronted with the unique challenges posed by graph-structured data, in large part due to the explosion of intermediate results, the complexity of join-heavy queries, and the use of regular path queries. This monograph provides a comprehensive overview of modern query processing techniques designed to address these challenges. Four key components that have emerged as pivotal in optimizing queries on graph-structured databases are focused on, namely: (1) Predefined joins, which leverage precomputed data structures to accelerate joins; (2) Worst-case optimal join algorithms, that avoid redundant computations for queries with cycles; (3) Factorized representations, which compress intermediate and final query results; and (4) Advanced techniques for processing recursive queries, essential for traversing graph structures. For each component, theoretical underpinnings are covered and design considerations are explored, and implementation challenges associated with integrating these techniques into existing database management systems are discussed. This monograph aims to serve as a comprehensive resource for both researchers pushing the boundaries of query processing and practitioners seeking to implement state-of-the-art techniques, in addition to offering insights into future research directions in this rapidly evolving field.

The two open access volumes LNCS 14574 and 14575 constitute the proceedings of the 27th International Conference on Foundations of Software Science and Computation Structures, FOSSACS 2024, which took place in Luxembourg in April 2024.The 24 full papers included in this book were carefully reviewed and selected from 79 submissions. They were organized in topical sections as follows: Part I: Infinite games; categorical semantics; automata and synthesis; Part II: Types and programming languages; logic and proofs; infinite-state systems.

Recent years have seen a resurgence of interest in Datalog from both the industry and research community. Datalog is a declarative query language that extends relational algebra with recursion. It is used to express a wide spectrum of modern data management tasks such as data integration, declarative networking, graph analysis, business analytics, and program analysis. The result of this long line of research is a plethora of Datalog engines that support different variants of Datalog, and have different technical specifications and capabilities. In this monograph, the authors provide an overview of the architecture and technical characteristics of the various Datalog engines. They identify common architectural decisions and evaluation methods as well as data structures and layouts used to speed up the query execution. They also discuss the ways in which Datalog engines differ when they specialize to workloads with different characteristics. A particular focus of this monograph is how modern Datalog engines scale to massively parallel environments, which is necessary to support the processing of very large datasets. The authors conclude with opportunities for future research directions and new possible applications for Datalog engines.

Automata theory is a subject of study at the crossroads of mathematics, theoretical computer science, and applications. In its core it deals with abstract models of systems whose behaviour is based on transitions between states, and it develops methods for the description, classification, analysis, and design of such systems. The Handbook of Automata Theory gives a comprehensive overview of current research in automata theory, and is aimed at a broad readership of researchers and graduate students in mathematics and computer science. Volume I is divided into three parts. The first part presents various types of automata: automata on words, on infinite words, on finite and infinite trees, weighted and maxplus automata, transducers, and two-dimensional models. Complexity aspects are discussed in the second part. Algebraic and topological aspects of automata theory are covered in the third part. Volume II consists of two parts. The first part is dedicated to applications of automata in mathematics: group theory, number theory, symbolic dynamics, logic, and real functions. The second part presents a series of further applications of automata theory such as message-passing systems, symbolic methods, synthesis, timed automata, verification of higher-order programs, analysis of probabilistic processes, natural language processing, formal verification of programs and quantum computing. The two volumes comprise a total of thirty-nine chapters, with extensive references and individual tables of contents for each one, as well as a detailed subject index.

This book contains the invited and contributed papers selected for presentation at SOFSEM 2021, the 47th International Conference on Current Trends in Theory and Practice of Computer Science, which was held online during January 25–28, 2021, hosted by the Free University of Bozen-Bolzano, Italy.The 33 full and 7 short papers included in the volume were carefully reviewed and selected from 100 submissions. They were organized in topical sections on: foundations of computer science; foundations of software engineering; foundations of data science and engineering; and foundations of algorithmic computational biology. The book also contains 5 invited papers.

This book constitutes the proceedings of the 8th and 9th International Provenance and Annotation Workshop, IPAW 2020 and IPAW 2021 which were held as part of ProvenanceWeek in 2020 and 2021. Due to the COVID-19 pandemic, PropvenanceWeek 2020 was held as a 1-day virtual event with brief teaser talks on June 22, 2020. In 2021, the conference was held virtually during July 19-22, 2021. The 11 full papers and 12 posters and system demonstrations included in these proceedings were carefully reviewed and selected from a total of 31 submissions. They were organized in the following topical sections: provenance capture and representation; security; provenance types, inference, queries and summarization; reliability and trustworthiness; joint IPAW/TaPP poster and demonstration session.

This book is a tribute to Professor Ewa Orłowska, a Polish logician who was celebrating the 60th year of her scientific career in 2017. It offers a collection of contributed papers by different authors and covers the most important areas of her research. Prof. Orłowska made significant contributions to many fields of logic, such as proof theory, algebraic methods in logic and knowledge representation, and her work has been published in 3 monographs and over 100 articles in internationally acclaimed journals and conference proceedings. The book also includes Prof. Orłowska's autobiography, bibliography and a trialogue between her and the editors of the volume, as well as contributors'biographical notes, and is suitable for scholars and students of logic who are interested in understanding more about Prof. Orłowska's work.

The idea of this book grew out of a symposium that was held at Stony Brook in September 2012 in celebration of David S.Warren's fundamental contributions to Computer Science and the area of Logic Programming in particular. Logic Programming (LP) is at the nexus of Knowledge Representation, Artificial Intelligence, Mathematical Logic, Databases, and Programming Languages. It is fascinating and intellectually stimulating due to the fundamental interplay among theory, systems, and applications brought about by logic. Logic programs are more declarative in the sense that they strive to be logical specifications of'what'to do rather than'how'to do it, and thus they are high-level and easier to understand and maintain. Yet, without being given an actual algorithm, LP systems implement the logical specifications automatically. Several books cover the basics of LP but focus mostly on the Prolog language with its incomplete control strategy and non-logical features. At the same time, there is generally a lack of accessible yet comprehensive collections of articles covering the key aspects in declarative LP. These aspects include, among others, well-founded vs. stable model semantics for negation, constraints, object-oriented LP, updates, probabilistic LP, and evaluation methods, including top-down vs. bottom-up, and tabling. For systems, the situation is even less satisfactory, lacking accessible literature that can help train the new crop of developers, practitioners, and researchers. There are a few guides onWarren's Abstract Machine (WAM), which underlies most implementations of Prolog, but very little exists on what is needed for constructing a state-of-the-art declarative LP inference engine. Contrast this with the literature on, say, Compilers, where one can first study a book on the general principles and algorithms and then dive in the particulars of a specific compiler. Such resources greatly facilitate the ability to start making meaningful contributions quickly. There is also a dearth of articles about systems that support truly declarative languages, especially those that tie into first-order logic, mathematical programming, and constraint solving. LP helps solve challenging problems in a wide range of application areas, but in-depth analysis of their connection with LP language abstractions and LP implementation methods is lacking. Also, rare are surveys of challenging application areas of LP, such as Bioinformatics, Natural Language Processing, Verification, and Planning. The goal of this book is to help fill in the previously mentioned void in the LP literature. It offers a number of overviews on key aspects of LP that are suitable for researchers and practitioners as well as graduate students. The following chapters in theory, systems, and applications of LP are included.

This book includes revised selected papers from five International Workshops on Artificial Intelligence Approaches to the Complexity of Legal Systems, AICOL VI to AICOL X, held during 2015-2017: AICOL VI in Braga, Portugal, in December 2015 as part of JURIX 2015; AICOL VII at EKAW 2016 in Bologna, Italy, in November 2016; AICOL VIII in Sophia Antipolis, France, in December 2016; AICOL IX at ICAIL 2017 in London, UK, in June 2017; and AICOL X as part of JURIX 2017 in Luxembourg, in December 2017.The 37 revised full papers included in this volume were carefully reviewed and selected form 69 submissions. They represent a comprehensive picture of the state of the art in legal informatics. The papers are organized in six main sections: legal philosophy, conceptual analysis, and epistemic approaches; rules and norms analysis and representation;legal vocabularies and natural language processing; legal ontologies and semantic annotation; legal argumentation; and courts, adjudication and dispute resolution.

This book offers a state-of-the-art introduction to the basic techniques and results of neighborhood semantics for modal logic. In addition to presenting the relevant technical background, it highlights both the pitfalls and potential uses of neighborhood models – an interesting class of mathematical structures that were originally introduced to provide a semantics for weak systems of modal logic (the so-called non-normal modal logics). In addition, the book discusses a broad range of topics, including standard modal logic results (i.e., completeness, decidability and definability); bisimulations for neighborhood models and other model-theoretic constructions; comparisons with other semantics for modal logic (e.g., relational models, topological models, plausibility models); neighborhood semantics for first-order modal logic, applications in game theory (coalitional logic and game logic); applications in epistemic logic (logics of evidence and belief); and non-normal modal logics with dynamic modalities.The book can be used as the primary text for seminars on philosophical logic focused on non-normal modal logics; as a supplemental text for courses on modal logic, logic in AI, or philosophical logic (either at the undergraduate or graduate level); or as the primary source for researchers interested in learning about the uses of neighborhood semantics in philosophical logic and game theory.

This double volumes LNCS 10573-10574 constitutes the refereed proceedings of the Confederated International Conferences: Cooperative Information Systems, CoopIS 2017, Ontologies, Databases, and Applications of Semantics, ODBASE 2017, and Cloud and Trusted Computing, C&TC, held as part of OTM 2017 in October 2017 in Rhodes, Greece.The 61 full papers presented together with 19 short papers were carefully reviewed and selected from 180 submissions. The OTM program every year covers data and Web semantics, distributed objects, Web services, databases, information systems, enterprise workflow and collaboration, ubiquity, interoperability, mobility, grid and high-performance computing.

This book constitutes the refereed proceedings of the 9th International Conference on Web Reasoning and Rule Systems, RR 2015, held in Berlin, Germany, in August 2015. The 5 full papers, 4 technical communications presented together with 4 invited talks were carefully reviewed and selected from 16 submissions. The scale and the heterogenous nature of web data poses many challenges, and turns basic tasks such as query answering and data transformations into complex reasoning problems. Rule-based systems have found many applications in this area. The RR conference welcomes original research from all areas of Web Reasoning and Rule Systems. Topics of particular interest are: answer set programming, complex events, datalog, description logics, event-condition-action rules, information extraction, and logic programming.

This text offers an extension to the traditional Kripke semantics for non-classical logics by adding the notion of reactivity. Reactive Kripke models change their accessibility relation as we progress in the evaluation process of formulas in the model. This feature makes the reactive Kripke semantics strictly stronger and more applicable than the traditional one. Here we investigate the properties and axiomatisations of this new and most effective semantics, and we offer a wide landscape of applications of the idea of reactivity. Applied topics include reactive automata, reactive grammars, reactive products, reactive deontic logic and reactive preferential structures.Reactive Kripke semantics is the next step in the evolution of possible world semantics for non-classical logics, and this book, written by one of the leading authorities in the field, is essential reading for graduate students and researchers in applied logic, and it offers many research opportunities forPhD students.

This book constitutes the thoroughly refereed conference proceedings of the 38th International Symposium on Mathematical Foundations of Computer Science, MFCS 2013, held in Klosterneuburg, Austria, in August 2013. The 67 revised full papers presented together with six invited talks were carefully selected from 191 submissions. Topics covered include algorithmic game theory, algorithmic learning theory, algorithms and data structures, automata, formal languages, bioinformatics, complexity, computational geometry, computer-assisted reasoning, concurrency theory, databases and knowledge-based systems, foundations of computing, logic in computer science, models of computation, semantics and verification of programs, and theoretical issues in artificial intelligence.

This Festschrift volume, published in honour of Peter Buneman, contains contributions written by some of his colleagues, former students, and friends. In celebration of his distinguished career a colloquium was held in Edinburgh, Scotland, 27-29 October, 2013. The articles presented herein belong to some of the many areas of Peter's research interests.

This is the first book-length treatment of hybrid logic and its proof-theory. Hybrid logic is an extension of ordinary modal logic which allows explicit reference to individual points in a model (where the points represent times, possible worlds, states in a computer, or something else). This is useful for many applications, for example when reasoning about time one often wants to formulate a series of statements about what happens at specific times. There is little consensus about proof-theory for ordinary modal logic. Many modal-logical proof systems lack important properties and the relationships between proof systems for different modal logics are often unclear. In the present book we demonstrate that hybrid-logical proof-theory remedies these deficiencies by giving a spectrum of well-behaved proof systems (natural deduction, Gentzen, tableau, and axiom systems) for a spectrum of different hybrid logics (propositional, first-order, intensional first-order, and intuitionistic).

This volume constitutes the refereed proceedings of the 36th International Symposium on Mathematical Foundations of Computer Science, MFCS 2011, held in Warsaw, Poland, in August 2011. The 48 revised full papers presented together with 6 invited talks were carefully reviewed and selected from 129 submissions. Topics covered include algorithmic game theory, algorithmic learning theory, algorithms and data structures, automata, grammars and formal languages, bioinformatics, complexity, computational geometry, computer-assisted reasoning, concurrency theory, cryptography and security, databases and knowledge-based systems, formal specifications and program development, foundations of computing, logic in computer science, mobile computing, models of computation, networks, parallel and distributed computing, quantum computing, semantics and verification of programs, and theoretical issues in artificial intelligence.

A good title should be informative enough to illuminate a potential reader on the content of a book. We hope that the present title gives at least some hints of what this book is about. The notion of natural deduction or modal logic are rather well known, but the notion of “hybrid system” certainly needs some explanation. In short, this study may be seen as a kind of search for good deductive systems. We think of systems good in practice which may be applied with easenotonlybywelltrainedlogiciansbutalso, forexample, byphilosophers who need handy deductive tools accompanying their analyses. In parti- lar, we are interested in providing systems that may be widely applied in teaching logic. Nowadays one may observe that several courses in “critical thinking” tend to eliminate courses in practical logic. On the other hand, logic is often taught as a strictly mathematical discipline in very dema- ing courses. It is important to?ll the gap between these extrema, and the crucial ingredient of any course which is supposed to teach how to use logic, is certainly a suitable deductive system. Since we address this work to a wide audience interested in applications of logic, we were trying to make it self-contained and accessible to a reader with no hard training in logic. The assumed reader should have some ba- ground in logic (an elementary course covering classical propositional and?rst-order logic with basics of set theory is enough) but not necessarily in modal logic.

The 16th annual International Conference on the Principles and Practice of Constraint Programming (CP 2010) was held in St. Andrews, Scotland, during September 6–10, 2010. We would like to thank our sponsors for their generous support of this event. This conference is concerned with all aspects of computing with constraints, including:theory,algorithms,applications,environments,languages,modelsand systems. We received a wide variety of submissions, each of which was reviewed by at least three referees. Referees were chosen for each submission by an initial bidding process where Program Committee members chose papers from their area of interest. The range of expertise represented by the large Program C- mittee meant that almost all submissions were reviewed by subject experts on the Program Committee, or by colleagues chosen by members of the Program Committee for their particular expertise. Papers weresolicitedeither as long (15 page), or short (8 page) submissions. Short-paper submissions were refereed to exactly the same high standards as long-paper submissions but naturally were expected to contain a smaller quantity of new material. Thus there is no disti- tion in these proceedings between short and long papers. I used the excellent EasyChair conference management system to support this process of reviewing, and for the collation and organization of these proceedings. Submissions were made either to the applications track or to the research track. Therewere101(23short)researchtracksubmissionsofwhich36(8short) wereaccepted,whichisa36%(35%ofshort)acceptancerate. Applicationstrack submissions received special consideration and the acceptance rate was sign- cantly higher than for the research track.

This book constitutes the refereed proceedings of the International Symposium on Logical Foundations of Computer Science, LFCS 2009, held in Deerfield Beach, Florida, USA in January 2008. The volume presents 31 revised refereed papers carefully selected by the program committee. All current aspects of logic in computer science are addressed, including constructive mathematics and type theory, logical foundations of programming, logical aspects of computational complexity, logic programming and constraints, automated deduction and interactive theorem proving, logical methods in protocol and program verification and in program specification and extraction, domain theory logics, logical foundations of database theory, equational logic and term rewriting, lambda and combinatory calculi, categorical logic and topological semantics, linear logic, epistemic and temporal logics, intelligent and multiple agent system logics, logics of proof and justification, nonmonotonic reasoning, logic in game theory and social software, logic of hybrid systems, distributed system logics, system design logics, as well as other logics in computer science.

The annual conference of the European Association for Computer Science Logic (EACSL), CSL 2009, was held in Coimbra (Portugal), September 7–11, 2009. The conference series started as a programme of International Workshops on Computer Science Logic, and then at its sixth meeting became the Annual C- ference of the EACSL. This conference was the 23rd meeting and 18th EACSL conference; it was organized at the Department of Mathematics, Faculty of S- ence and Technology, University of Coimbra. In response to the call for papers, a total of 122 abstracts were submitted to CSL 2009of which 89 werefollowedby a full paper. The ProgrammeCommittee selected 34 papers for presentation at the conference and publication in these proceedings. The Ackermann Award is the EACSL Outstanding Dissertation Award for Logic in Computer Science. The awardrecipient for 2009 was Jakob Nordstr¨ om. Citation of the award, abstract of the thesis, and a biographical sketch of the recipient may be found at the end of the proceedings. The award was sponsored for the years 2007–2009 by Logitech S.A.

This book constitutes the refereed proceedings of the 24th Annual Symposium on Theoretical Aspects of Computer Science, STACS 2007, held in Aachen, Germany in February 2007. The 56 revised full papers presented together with 3 invited papers address the whole range of theoretical computer science as well as current challenges like biological computing, quantum computing, and mobile and net computing.

This book constitutes the refereed proceedings of the 10th International Conference on Foundations of Software Science and Computation Structures, FOSSACS 2007, held in Braga, Portugal in March/April 2007. The 25 revised full papers presented together with the abstract of one invited talk cover a broad spectrum on theories and methods to support analysis, synthesis, transformation and verification of programs and software systems.

This book constitutes the refereed proceedings of the International Symposium on Logical Foundations of Computer Science, LFCS 2007, held in New York, NY, USA in June 2007. The volume presents 36 revised refereed papers that address all current aspects of logic in computer science.

This book constitutes the refereed proceedings of the 11th International Conference on Database Theory, ICDT 2007, held in Spain in January 2007. The papers are organized in topical sections on information integration and peer to peer, axiomatizations for XML, expressive power of query languages, incompleteness, inconsistency, and uncertainty, XML schemas and typechecking, stream processing and sequential query processing, ranking, XML update and query, as well as query containment.

Mathematical Problems from Applied Logic I presents chapters from selected, world renowned, logicians. Important topics of logic are discussed from the point of view of their further development in light of requirements arising from their successful application in areas such as Computer Science and AI language. An overview of the current state as well as open problems and perspectives are clarified in such fields as non-standard inferences in description logics, logic of provability, logical dynamics, and computability theory. The book contains interesting contributions concerning the role of logic today, including some unexpected aspects of contemporary logic and the application of logic.

Membrane computing is a branch of natural computing which investigates computing models abstracted from the structure and functioning of living cells and from their interactions in tissues or higher-order biological structures. The models considered, called membrane systems (P systems), are parallel, distributed computing models, processing multisets of symbols in cell-like compartmental architectures. In many applications membrane systems have considerable advantages – among these are their inherently discrete nature, parallelism, transparency, scalability and nondeterminism. In dedicated chapters, leading experts explain most of the applications of membrane computing reported so far, in biology, computer science, computer graphics and linguistics. The book also contains detailed reviews of the software tools used to simulate P systems.

The8thWorkshopontheFoundationsofGeneticAlgorithms,FOGA-8,washeld at the University of Aizu in Aizu-Wakamatsu City, Japan, January 5–9, 2005. This series of workshops was initiated in 1990 to encourage further research on the theoretical aspects of genetic algorithms, and the workshops have been held biennially ever since. The papers presented at these workshops are revised, edited and published as volumes during the year following each workshop. This series of (now eight) volumes provides an outstanding source of reference for the theoretical work in this?eld. At the same time this series of volumes provides a clear picture of how the theoretical research has grown and matured along with the?eld to encompass many evolutionary computation paradigms including evolution strategies (ES), evolutionary programming (EP), and genetic programming (GP), as well as the continuing growthininteractionswith other?elds suchas mathematics,physics, and biology. Atraditionoftheseworkshopsisorganizetheminsuchawayastoencourage lots of interaction and discussion by restricting the number of papers presented and the number of attendees, and by holding the workshop in a relaxed and informal setting. This year's workshop was no exception. Thirty-two researchers met for 3 days to present and discuss 16 papers. The local organizer was Lothar Schmitt who, together with help and support from his university, provided the workshop facilities. Aftertheworkshopwasover,theauthorsweregiventheopportunitytorevise their papers based on the feedback they received from the other participants.