2,873 research outputs found
Relational Width of First-Order Expansions of Homogeneous Graphs with Bounded Strict Width
No full textSolving the algebraic dichotomy conjecture for constraint satisfaction problems over structures first-order definable in countably infinite finitely bounded homogeneous structures requires understanding the applicability of local-consistency methods in this setting. We study the amount of consistency (measured by relational width) needed to solve CSP(?) for first-order expansions ? of countably infinite homogeneous graphs ℋ := (A; E), which happen all to be finitely bounded. We study our problem for structures ? that additionally have bounded strict width, i.e., for which establishing local consistency of an instance of CSP(?) not only decides if there is a solution but also ensures that every solution may be obtained from a locally consistent instance by greedily assigning values to variables, without backtracking.
Our main result is that the structures ? under consideration have relational width exactly (2, ?_ℋ) where ?_ℋ is the maximal size of a forbidden subgraph of ℋ, but not smaller than 3. It beats the upper bound: (2 m, 3 m) where m = max(arity(?)+1, ?, 3) and arity(?) is the largest arity of a relation in ?, which follows from a sufficient condition implying bounded relational width given in [Manuel Bodirsky and Antoine Mottet, 2018]. Since ?_ℋ may be arbitrarily large, our result contrasts the collapse of the relational bounded width hierarchy for finite structures ?, whose relational width, if finite, is always at most (2,3)
The Complexity of Abduction for Equality Constraint Languages
No full textAbduction is a form of nonmonotonic reasoning that looks for an explanation for an observed manifestation according to some knowledge base. One form of the abduction problem studied in the literature is the propositional abduction problem parameterized by a structure \Gamma over the two-element domain. In that case, the knowledge base is a set of constraints over \Gamma, the manifestation and explanation are propositional formulas.
In this paper, we follow a similar route. Yet, we consider abduction over infinite domain. We study the equality abduction problem parameterized by a relational first-order structure \Gamma over the natural numbers such that every relation in \Gamma is definable by a Boolean combination of equalities, a manifestation is a literal of the form (x = y) or (x != y), and an explanation is a set of such literals. Our main contribution is a complete complexity characterization of the equality abduction problem. We prove that depending on \Gamma, it is \Sigma^P_2-complete, or NP-complete, or in P
Identifying Tractable Quantified Temporal Constraints Within Ord-Horn
No full textThe constraint satisfaction problem, parameterized by a relational structure, provides a general framework for expressing computational decision problems. Already the restriction to the class of all finite structures forms an interesting microcosm on its own, but to express decision problems in temporal reasoning one has to take a step beyond the finite-domain realm. An important class of templates used in this context are temporal structures, i.e., structures over ℚ whose relations are first-order definable using the usual countable dense linear order without endpoints.
In the standard setting, which allows only existential quantification over input variables, the complexity of finite and temporal constraints has been fully classified. In the quantified setting, i.e., when one also allows universal quantifiers, there is only a handful of partial classification results and many concrete cases of unknown complexity. This paper presents a significant progress towards understanding the complexity of the quantified constraint satisfaction problem for temporal structures. We provide a complexity dichotomy for quantified constraints over the Ord-Horn fragment, which played an important role in understanding the complexity of constraints both over temporal structures and in Allen’s interval algebra. We show that all problems under consideration are in P or coNP-hard. In particular, we determine the complexity of the quantified constraint satisfaction problem for (ℚ;x = y⇒ x ≥ z), hereby settling a question open for more than ten years
Equivalence Constraint Satisfaction Problems
No full textThe following result for finite structures Gamma has been conjectured to hold for all countably infinite omega-categorical structures Gamma: either the model-complete core Delta of Gamma has an expansion by finitely many constants such that the pseudovariety generated by its polymorphism algebra contains a two-element algebra all of whose operations are projections, or there is a homomorphism f from Delta^k to Delta, for some finite k, and an automorphism alpha of Delta satisfying f(x1,...,xk) = alpha(f(x2,...,xk,x1)). This conjecture has been confirmed for all infinite structures Gamma that have a first-order definition over (Q;<), and for all structures that are definable over the random graph. In this paper, we verify the conjecture for all structures that are definable over an equivalence relation with a countably infinite number of countably infinite classes.
Our result implies a complexity dichotomy (into NP-complete and P) for a family of constraint satisfaction problems (CSPs) which we call equivalence constraint satisfaction problems. The classification for equivalence CSPs can also be seen as a first step towards a classification of the CSPs for all relational structures that are first-order definable over Allen's interval algebra, a well-known constraint calculus in temporal reasoning
Smooth Approximations and Relational Width Collapses
No full textWe prove that relational structures admitting specific polymorphisms (namely, canonical pseudo-WNU operations of all arities n ≥ 3) have low relational width. This implies a collapse of the bounded width hierarchy for numerous classes of infinite-domain CSPs studied in the literature. Moreover, we obtain a characterization of bounded width for first-order reducts of unary structures and a characterization of MMSNP sentences that are equivalent to a Datalog program, answering a question posed by Bienvenu et al.. In particular, the bounded width hierarchy collapses in those cases as well
Lesion and stimulation of the ventral tegmental area increases cholinergic activity in the rat brain
No full textOur previous study indicated that unilateral lesion of the ventral tegmental area (VTA) facilitates contralateral VTA stimulation-induced feeding or exploration. The present study was aimed to determine the possible role of the central cholinergic systems in this effect. Immunohistochemistry for choline acetyltransferase (ChAT) was used to measure the number of active cholinergic neurons in their major groups (Ch1-Ch6) and in striatal regions in rats subjected to unilateral electrocoagulation and contralateral VTA electrical stimulation (L/S group) in comparison to the unilaterally stimulated (S), unilaterally lesioned (L) and sham (Sh) groups. The study showed that unilateral VTA lesion increased (as compared to Sh group) the number of ChAT+ neurons in the Ch1-Ch3 and unilateral VTA stimulation increased the number in the Ch1 and the ventral pallidum only. The most sensitive to these changes in the mesolimbic system were cholinergic structures providing hippocampal afferentation. Surprisingly, there was no significant increase in the number of ChAT+ neurons in the L/S group. The obtained results did not confirm any evident influence of the cholinergic systems on the VTA lesion-induced facilitation of the behavioral response evoked by contralateral VTA stimulation
Determining the personality of Internet users by analyzing their digital footprints in the light of selected research by Michał Kosiński
No full textAccording to data from Internet Live Stats, in April 2021, about 92,000 queries were made, every second, in the Google search engine. Each activity performed by users of digital devices is indexed as so-called digital footprints [also called digital traces], thanks to which it is possible, using appropriate technologies and methods, to precisely define personality traits, political views and sexual orientations of these users.The article was inspired by the works of PhD Michał Kosiński and describes the issues related to analyzing digital traces of Internet users (mainly social media).The main aim of the article is to present the research by PhD Michał Kosiński and to draw the attention of the IT community to the issues related to analyzing the digital traces of Internet users. This work is of a popularizing nature and does not constitute a comprehensive description of the achievements of the indicated scientist. The article does not present new information or own research – however, it is intended to encourage recipients to analyze the literature on the subject of analyzing digital traces and privacy in the digital age.The work uses the method of database content analysis – to collect and analyze the literature on the subject. The focus was on the resources made available by PhD Kosinski through his private website – https://www.michalkosinski.com Additionally, datamining techniques were used to summarize the archival content published on the Cambridge Analytica website.The chronological range of the searched writing materials was narrowed from 2011 to the first quarter of 2021, focusing mainly on the years 2013–2021, i.e. from the year of publishing the article Private traits and attributes are predictable from digital records of human behavior until the year of publication of the text Facial recognition technology can expose political orientation from naturalistic facial images.The article presents selected works by PhD Michał Kosiński, which constitute "milestones" in research on determining the personality of Internet users within the publication of the indicated author. Consequently, the article does not present the works that described part of the research or contributed to taking larger, further measurements.Według danych Internet Live Stats w kwietniu 2021 roku w czasie każdej sekundy zadawano około 92 tysięcy zapytań w wyszukiwarce Google. Każda czynność dokonywana przez użytkowników urządzeń cyfrowych jest indeksowana jako tak zwane cyfrowe ślady, dzięki którym możliwe jest, przy zastosowaniu odpowiednich technologii oraz metod, precyzyjne określanie cech osobowości, poglądów politycznych oraz orientacji seksualnych tychże użytkowników.Artykuł został zainspirowany pracami dr. Michała Kosińskiego i stanowi opis problematyki związanej z analizowaniem cyfrowych śladów użytkowników Internetu (głównie mediów społecznościowych).Nadrzędnym celem artykułu jest przedstawienie badań Michała Kosińskiego i zwrócenie uwagi środowiska informatologicznego na kwestie związane z analizowaniem cyfrowych śladów użytkowników Internetu. Praca ta ma charakter popularyzatorski, nie stanowi całościowego opisu dokonań wskazanego naukowca. Artykuł nie przedstawia nowych informacji ani badań własnych – ma jednak zachęcić odbiorców do przeanalizowania literatury przedmiotu dotyczącej analizowania cyfrowych śladów oraz prywatności w dobie cyfrowej.W pracy wykorzystano metodę analizy zawartości baz danych – do zebrania i przeanalizowania literatury przedmiotu. Skupiono się na zasobach udostępnianych przez dr. Kosińskiego poprzez prywatną stronę internetową – https://www.michalkosinski.com Dodatkowo wykorzystano techniki związane z data miningiem, aby w podsumowaniu móc przedstawić archiwalne treści publikowane na stronie internetowej firmy Cambridge Analytica.Zasięg chronologiczny odszukiwanych materiałów piśmienniczych zawężono do okresu od 2011 r. do pierwszego kwartału 2021 r., skupiając się głównie na latach 2013–2021, czyli od roku opublikowania artykułu Private traits and attributes are predictable from digital records of human behavior do roku publikacji tekstu Facial recognition technology can expose political orientation from naturalistic facial images. W artykule przedstawiono wybrane prace dr. Michała Kosińskiego, które stanowią „kamienie milowe” w badaniach nad określaniem osobowości użytkowników Internetu w obrębie publikacji wskazanego autora. Co za tym idzie, w artykule nie przedstawiono tych prac, które były opisem części badań lub były przyczynkiem do podjęcia większych, dalszych pomiarów
Michał Twarowski (Mykolas Tvarauskas) i jego "Słownik"
No full textMykolas Tvarauskas (1844-1912) – spausdinimo lietuvių kalba Jungtinėse Amerikos Valstijose pradininkas. 1874-1875 m. M. Tvarauskas įsteigė pirmąją lietuvišką spaustuvę Šamokine (Pensilvanija, JAV). Jis buvo pirmosios lietuviškos knygos Amerikoje – dvikalbio anglų-lietuvių ir lietuvių-anglų kalbų žodyno „Tlumaczius arba Slownikas Angielckaj-Lietuwyszkas ir Lietuwiszkaj-Angielckas“ – autorius, redaktorius ir leidėjas. Iki šiol išliko tik vienas šios knygos egzempliorius ir reklaminis bukletas lietuviams „Mieli broliai“. 1997 m. „Minties“ leidykla išleido abiejų leidinių faksimiles. Tai labai vertingas šaltinis istorikams ir kalbininkams. Šiuose leidiniuose naudojama kitokia rašyba nei dabartiniu metu. M. Tvarauskas vartojo savo gimtojo krašto, Kybartų, tarmę, t. y. vakarų aukštaičių pietvakarinės dalies tarmę. Naujame leidime pateikiami Lietuvos mokslininkų straipsniai, skirti M. Tvarausko gyvenimui, veiklai ir „Žodynui“. Reikšminiai žodžiai: JAV; JAV lietuvių knyga; Jonas Šliūpas; Knygos lietuvių kalba; Leidiniai; Lietuvių emigracija; Mykolas Tvarauskas (Michal Twarowski); Mykolas Tvarauskas (Michal Twarowski); Periodika; Spauda; Spaustuvės; Tekstologinė analizė; Žodynai; „Tlumoczius arba Slownikas Angielckaj-Lietuwyszkas ir Lietuwyszkaj-Angielckas“; Amerikos lietuvių knyga; Dictionaries; Jonas Šliūpas; Lietuvių emigracija; Lithuanian book in the USA; Lithuanian books; Michal Twarowski; Mykolas Tvarauskas (Michal Twarowski); Periodicals; Printing houses; Publications; Publishing; Textual analysis; USA; „Tlumoczius arba Slownikas Angielckaj-Lietuwyszkas ir Lietuwyszkaj-Angielckas“Michał Twarowski (1844-1912) was a pioneer of printing in Lithuanian in the U.S. Between 1874 and 1875 Twarowski founded the first Lithuanian printing house in the U.S. located in Shamokin (Pennsylvania). He was the author as well as an editor and printer of the first Lithuanian book in the U.S. - a bilingual English-Lithuanian and Lithuanian-English Dictionary (Tlumaczius arba Slownikas Angielckaj-Lietuwyszkas ir Lietuwiszkaj-Angielcaks, Shamokin 1875). Only one original copy of the book and an advertising brochure, addressed to Lithuanians (called „Dear Brothers"), has survived. In 1997 "Mintys" Publishing House reprinted both literary monuments. They are very valuable as the sources for historical and linguistic research. The spelling orthography used in these publications are different than today. Their language is based on the West South form of the West High Lithuanian dialect used in the Kibartai area where Twarowski was born. This edition is accompanied with articles written by Lithuanian scholars and devoted to Twarowski's life, his activities and the "Dictionary"
Michał Bałucki’s Literary Disputes
No full textArtykuł charakteryzuje wypowiedzi krytyczne Michała Bałuckiego, autora rozprawy O różnych modach w literaturze powieściowej (1894), dotyczące modernizmu oraz wypowiedzi przedstawicieli krytyki młodopolskiej formułowane w stosunku do twórczości Bałuckiego. Spór literacki przybiera najbardziej tragiczne zakończenie z możliwych. Kontekstem rozważań czyni autorka kategorię agonu literackiego, która okazuje się interesująca przy próbie opisu dokonań artystycznych ostatniej dekady życia i twórczości krakowskiego komediopisarza.The aim of this article is to summarise critical responses of Michał Bałucki, the author of the essay O różnych modach w literaturze powieściowej (1894), concerning modernism and the criticism expressed about his own works by the critics of the Young Poland movement. The literary feud takes on the most tragic end possible. As a context for her reflections, the author of this article utilises the category of literary agon, which turns out to be a very illuminating idea when applied to describing the artistic achievements of the last decade of the playwright’s life
- …
