1,721,015 research outputs found
Making home at the borders of citizenship: Migrants, home, and (il)legality
No full textA growing literature at the intersection of citizenship and border studies have theorized borders as filters drawing distinctions through socio-cultural, legal and administrative constructs of deservingness extending from the territorial “entry gates” into the “soft inside” of citizenship (Bonizzoni 2016, 2020; Chauvin and Garcés-Mascareñas 2012, 2014; Gargiulo 2017, 2021; Horton and Heyman 2020; Yuval-Davis, Wemyss and Cassidy 2019). These socio-legal constructs produce a wide array of categories – EU-citizen/TCN, legal/illegal; refugee/economic/family migrants – stratifying migrants’ access to citizenship rights, including the right to housing (Andersen, Turner and Søholt 2013; Jacobsen 2006; Morris 2002). As migrants’ access to (private and public) housing is heavily mediated by the possess (or the lack) of a certain status, the latter can heavily constraint migrants’ housing choices regarding where to live, for how long and with whom. This includes both vulnerable and especially protected groups hosted in reception centres (e.g. unaccompanied minors, asylum seekers and refugees, trafficked women...) as well as undocumented migrants pushed to live in camps, squats or in the informal housing market (Agier 2011; Campesi 2018).
At the same time, the possess (or the lack) of “adequate” and “proper” housing represents a key element informing policies and bureaucrats’ decisions that can bear relevant consequences for migrant’s (il)legality and citizenship rights, more broadly. In other terms, homelessness, precarious and informal housing can turn into a key trait of the “deserving” (un)citizen, jeopardizing a wide array of status-related assessments and procedures, including naturalization, family reunification and legalization opportunities.
As argued by Walters (2004) under domopolitics, migrants are “guests”, who must be monitored and disciplined to ensure “good” behaviour. This chapter, drawing on an extended and cross-national review of studies on immigration, home and (il)legality, aims to show how this efforts extend into the private space of home to produce inclusionary/exclusionary public outcomes in terms of bordered (un)citizenship
A characterization of (regular) circular languages generated by monotone complete splicing systems
No full textCircular splicing systems are a formal model of a generative mechanism of circular words, inspired by a recombinant behaviour of circular DNA. Some unanswered questions are
related to the computational power of such systems, and finding a characterization of the class of circular languages generated by circular splicing systems is still an open problem. In this paper we solve this problem for monotone complete systems, which are finite circular splicing systems with rules of a simpler form.We show that a circular language L is generated by a monotone complete system if and only if the set Lin(L) of all words corresponding to L is a pure unitary language generated by a set closed under the conjugacy relation. The class of pure unitary languages was introduced by A. Ehrenfeucht, D. Haussler, G. Rozenberg in 1983, as a subclass of the class of context-free languages, together with a characterization of regular pure unitary languages by means of a decidable property. As a direct consequence, we characterize (regular) circular languages generated by monotone complete systems.We can also decide whether the language generated by a monotone complete system is regular.
Finally, we point out that monotone complete systems have the same computational power
as finite simple systems, an easy type of circular splicing system defined in the literature
from the very beginning, when only one rule of a specific type is allowed. From our results
on monotone complete systems, it follows that finite simple systems generate a class of
languages containing non-regular languages, showing the incorrectness of a longstanding
result on simple systems
The structure of reflexive regular splicing languages via Schutzenberger constants
No full textThe splicing operation was introduced in 1987 by Head as a mathematical model of the recombination of DNA molecules under the influence of restriction and ligases enzymes. This operation allows us to define a computing (language generating) device, called a splicing system. Other variants of this original definition were also proposed by Paun and Pixton respectively. The computational power of splicing systems has been thoroughly investigated. Nevertheless, an interesting problem is
still open, namely the characterization of the class of regular languages generated by finite splicing systems. In this paper, we will solve the problem for a special class of finite splicing systems, termed reflexive splicing systems, according to each of the definitions of splicing given by Paun and Pixton. This special class of systems contains, in perticular, finite Head splicing systems. The notion of a constant, given by Schützenberger, once again intervenes
Circular splicing and regularity
No full textCircular splicing has been very recently introduced to model a specific recombinant behaviour of circular DNA, continuing the
investigation initiated with linear splicing. In this paper we restrict our study to the relationship between regular circular languages and languages generated by finite circular splicing systems and provide some results towards a characterization of the intersection between these two classes. We consider the class of languages X*, called here star languages, which are closed under conjugacy relation and with X being a regular language. Using automata theory and combinatorial techniques
on words, we show that for a subclass of star languages the corresponding circular languages are (Paun) circular splicing languages. For example, star languages belong to this subclass when X* is a free monoid or X is a finite set. We also prove that each (Paun) circular splicing language L over a one-letter alphabet has the form L = X^+ ∪ Y , with X, Y finite sets satisfying particular hypotheses. Cyclic and weak cyclic
languages, which will be introduced in this paper, show that this result does not hold when we increase the size of alphabets, even if we restrict ourselves to regular languages
Linear splicing and syntactic monoid
No full textSplicing systems were introduced by Head in 1987 as a formal counterpart of a biological mechanism of DNA recombination under the action of restriction and ligase enzymes. Despite the intensive studies on linear splicing systems, some elementary questions about their computational power are still open. In particular, in this paper we face the problem of characterizing the proper subclass of regular languages which are generated by finite (Paun) linear splicing systems.We introduce here the class of marker languages L, i.e., regular languages with the form L=L_1[x]_1L_2, where L_1,L_2 are regular languages, [x] is a syntactic congruence class satisfying special conditions and [x]_1 is either equal to [x] or equal to [x] ∪ {1}, 1 being the empty word. Using classical properties of formal language theory, we give an algorithm which allows us to decide whether a regular language is a marker language. Furthermore, for each marker language L we exhibit a finite Paun linear splicing system and we prove that this system generates L
A rearrangement distance for fully-labelled trees
Full text linkThe problem of comparing trees representing the evolutionary histories of cancerous tumors has turned out to be crucial, since there is a variety of different methods which typically infer multiple possible trees. A departure from the widely studied setting of classical phylogenetics, where trees are leaf-labelled, tumoral trees are fully labelled, i.e., every vertex has a label. In this paper we provide a rearrangement distance measure between two fully-labelled trees. This notion originates from two operations: one which modifies the topology of the tree, the other which permutes the labels of the vertices, hence leaving the topology unaffected. While we show that the distance between two trees in terms of each such operation alone can be decided in polynomial time, the more general notion of distance when both operations are allowed is NP-hard to decide. Despite this result, we show that it is fixed-parameter tractable, and we give a 4-approximation algorithm when one of the trees is binary
- …
