30472 research outputs found
Sort by
Subsequence covers of words
Get PDFWe introduce subsequence covers (s-covers, in short), a new type of covers of a word. A word C is an s-cover of a word S if the occurrences of C in S as subsequences cover all the positions in S.
The s-covers seem to be computationally much harder than standard covers of words (cf. Apostolico et al., Inf. Process. Lett. 1991), but, on the other hand, much easier than the related shuffle powers (Warmuth and Haussler, J. Comput. Syst. Sci. 1984).
We give a linear-time algorithm for testing if a candidate word C is an s-cover of a word S over a polynomially-bounded integer alphabet. We also give an algorithm for finding a shortest s-cover of a word S, which in the case of a constant-sized alphabet, also runs in linear time. Furthermore, we complement our algorithmic results with a lower and an upper bound on the length of a longest word without non-trivial s-covers, which are both exponential in the size of the alphabet
Current insights and future challenges
Get PDFBook synopsis: This publication provides an overview of current knowledge and the latest developments in the field of drug use and prison in Europe. The report explores in depth the epidemiology of drug use and drug-related problems among the prison population, the available social and health service responses to drug-related problems in prison, including the most recent evidence of effectiveness, and the drug supply and markets inside prison. It also discusses recent and future challenges in this area. The report will be of interest to policymakers and their advisors, specialists and practitioners, researchers and scientists and all those concerned with the issue of prison and drugs
Glover, Phil, Protecting National Security: A history of British Communications Investigation Regulation, Abingdon, Routledge, 2021
No full text
The site of the archive: responsibility and rhetoric in archival archaeology of the Middle East
No full textBook synopsis: Archives held in institutions around the world hold a wealth of material but traditionally, the fields of Classical and ancient Near Eastern archaeology have been slow to make use of such legacy data in their investigations. In recent years, however, this trend has begun to change, and scholars increasingly recognize the importance of archival material to their research. Drawing directly on these trends, this volume offers the first in-depth analysis of what it means to engage in archive archaeology and how it can influence understandings of both the ancient world and the recent past. Excavation historiographies and the formation of archaeological archives in the twentieth century are investigated in locations from across the Eastern Mediterranean and the Middle East, with current understanding of sites such as Dura Europos or Palmyra being fundamentally reassessed in the light of the archival material. Crucially, the volume contributions gathered here look to the future as well as to the past: archives are acknowledged as essential to cultural heritage preservation and restitution initiatives, and chapters explore best practices, as well as presenting some of the manifold potentials of archive and legacy data to future research
Modulation of EEG theta by naturalistic social content is not altered in infants with family history of autism
Get PDFTheta oscillations (spectral power and connectivity) are sensitive to the social content of an experience in typically developing infants, providing a possible marker of early social brain development. Autism is a neurodevelopmental condition affecting early social behaviour, but links to underlying social brain function remain unclear. We explored whether modulations of theta spectral power and connectivity by naturalistic social content in infancy are related to family history for autism. Fourteen-month-old infants with (family history; FH; N=75) and without (no family history; NFH; N=26) a first-degree relative with autism watched social and non-social videos during EEG recording. We calculated theta (4-5 Hz) spectral power and connectivity modulations (social – non-social) and associated them with outcomes at 36 months. We replicated previous findings of increased theta power and connectivity during social compared to non-social videos. Theta modulations with social content were similar between groups, for both power and connectivity. Together, these findings suggest that neural responses to naturalistic social stimuli may not be strongly altered in 14-month-old infants with family history of autism
Long reads: Esther Leslie on Walter Benjamin's messianic Marxism
No full textEsther Leslie joins Long Reads for a discussion about Walter Benjamin, one of the most influential cultural theorists of the last century. His unorthodox Marxism and ideas about culture and history have inspired several generations of critical thought about the world made by capitalism. Esther is a leading authority on Benjamin’s life and work who teaches at Birkbeck University in London.
Long Reads is a Jacobin podcast looking in-depth at political topics and thinkers, both contemporary and historical, with the magazine’s longform writers. Hosted by Features Editor Daniel Finn. Produced by Conor Gillies, music by Knxwledge
First-Order Rewritability and complexity of Two-Dimensional Temporal Ontology-Mediated Queries
Get PDFAiming at ontology-based data access to temporal data, we design two-dimensional temporal ontology and query languages by combining logics from the (extended) DL-Lite family with linear temporal logic LTL over discrete time (Z, 1, and FO(RPR) that admits relational primitive recursion. In terms of circuit complexity, FOE- and FO(RPR)-rewritability guarantee answering OMQs in uniform AC0 and NC1, respectively.
We proceed in three steps. First, we define a hierarchy of 2D DL-Lite/LTL ontology languages and investigate the FO-rewritability of OMQs with atomic queries by constructing projections onto 1D LTL OMQs and employing recent results on the FO-rewritability of propositional LTL OMQs. As the projections involve deciding consistency of ontologies and data, we also consider the consistency problem for our languages. While the undecidability of consistency for 2D ontology languages with expressive Boolean role inclusions might be expected, we also show that, rather surprisingly, the restriction to Krom and Horn role inclusions leads to decidability (and ExpSpace-completeness), even if one admits full Booleans on concepts. As a final step, we lift some of the rewritability results for atomic OMQs to OMQs with expressive positive temporal instance queries. The lifting results are based on an in-depth study of the canonical models and only concern Horn ontologies
Data sources:
Access Repository Dashboard
Do you manage Birkbeck Institutional Research Online? Access insider analytics, issue reports and manage access to outputs from your repository in the CORE Repository Dashboard!