{"results":[{"id":"doaj_10.46298/dmtcs.7288","title":"Induced betweenness in order-theoretic trees","authors":[{"name":"Bruno Courcelle"}],"abstract":"The ternary relation B(x,y,z) of betweenness states that an element y is between the elements x and z, in some sense depending on the considered structure. In a partially ordered set (N,≤), B(x,y,z):⇔x\u003cy\u003cz∨z\u003cy\u003cx, and the corresponding betweenness structure is (N,B). The class of betweenness structures of linear orders is first-order definable. That of partial orders is monadic second-order definable. An order-theoretic tree is a partial order such that the set of elements larger that any element is linearly ordered and any two elements have an upper-bound. Finite or infinite rooted trees ordered by the ancestor relation are order-theoretic trees. In an order-theoretic tree, B(x,y,z) means that x\u003cy\u003cz or z\u003cy\u003cx or x\u003cy≤x⊔z or z\u003cy≤x⊔z, where x⊔z is the least upper-bound of incomparable elements x and z. In a previous article, we established that the corresponding class of betweenness structures is monadic second-order definable.We prove here that the induced substructures of the betweenness structures of the countable order-theoretic trees form a monadic second-order definable class, denoted by IBO. The proof uses a variant of cographs, the partitioned probe cographs, and their known six finite minimal excluded induced subgraphs called the bounds of the class. This proof links two apparently unrelated topics: cographs and order-theoretic trees.However, the class IBO has finitely many bounds, i.e., minimal excluded finite induced substructures. Hence it is first-order definable. The proof of finiteness uses well-quasi-orders and does not provide the finite list of bounds. Hence, the associated first-order defining sentence is not known.","source":"DOAJ","year":2022,"language":"","subjects":["Mathematics"],"doi":"10.46298/dmtcs.7288","url":"https://dmtcs.episciences.org/7288/pdf","pdf_url":"https://dmtcs.episciences.org/7288/pdf","is_open_access":true,"published_at":"","score":66},{"id":"crossref_10.6017/cs.v3i1.15935","title":"“ME DI CUENTA EL OTRO DÍA QUE ERA CHINA Y NO LO SABÍA”: UNA CONVERSACIÓN SOBRE LA HIBRIDACIÓN CULTURAL CON QUAN ZHOU WU","authors":[{"name":"Raquel Vega-Durán"}],"abstract":"ENTREVISTA CON QUAN ZHOU WU","source":"CrossRef","year":2022,"language":"en","subjects":null,"doi":"10.6017/cs.v3i1.15935","url":"https://doi.org/10.6017/cs.v3i1.15935","pdf_url":"https://ejournals.bc.edu/index.php/consecuencias/article/download/15935/11607","is_open_access":true,"published_at":"","score":66},{"id":"doaj_10.23638/DMTCS-22-4-2","title":"A Type System Describing Unboundedness","authors":[{"name":"Paweł Parys"}],"abstract":"We consider nondeterministic higher-order recursion schemes as recognizers of languages of finite words or finite trees. We propose a type system that allows to solve the simultaneous-unboundedness problem (SUP) for schemes, which asks, given a set of letters A and a scheme G, whether it is the case that for every number n the scheme accepts a word (a tree) in which every letter from A appears at least n times. Using this type system we prove that SUP is (m-1)-EXPTIME-complete for word-recognizing schemes of order m, and m-EXPTIME-complete for tree-recognizing schemes of order m. Moreover, we establish the reflection property for SUP: out of an input scheme G one can create its enhanced version that recognizes the same language but is aware of the answer to SUP.","source":"DOAJ","year":2020,"language":"","subjects":["Mathematics"],"doi":"10.23638/DMTCS-22-4-2","url":"https://dmtcs.episciences.org/4748/pdf","pdf_url":"https://dmtcs.episciences.org/4748/pdf","is_open_access":true,"published_at":"","score":64},{"id":"crossref_10.12809/hkjr1916917","title":"Factors Affecting Inferior Vena Cava Filter Retrieval Success Rate","authors":[{"name":"HC Lee"},{"name":"WY Wong"},{"name":"FH Ng"},{"name":"CS Chan"},{"name":"KL Lo"}],"abstract":"","source":"CrossRef","year":2019,"language":"en","subjects":null,"doi":"10.12809/hkjr1916917","url":"https://doi.org/10.12809/hkjr1916917","is_open_access":true,"published_at":"","score":63},{"id":"doaj_10.23638/DMTCS-20-2-11","title":"IMP with exceptions over decorated logic","authors":[{"name":"Burak Ekici"}],"abstract":"In this paper, we facilitate the reasoning about impure programming languages, by annotating terms with “decorations”that describe what computational (side) effect evaluation of a term may involve. In a point-free categorical language,called the “decorated logic”, we formalize the mutable state and the exception effects first separately, exploiting anice duality between them, and then combined. The combined decorated logic is used as the target language forthe denotational semantics of the IMP+Exc imperative programming language, and allows us to prove equivalencesbetween programs written in IMP+Exc. The combined logic is encoded in Coq, and this encoding is used to certifysome program equivalence proofs.","source":"DOAJ","year":2018,"language":"","subjects":["Mathematics"],"doi":"10.23638/DMTCS-20-2-11","url":"https://dmtcs.episciences.org/3272/pdf","pdf_url":"https://dmtcs.episciences.org/3272/pdf","is_open_access":true,"published_at":"","score":62},{"id":"crossref_10.18046/recs.i21.2423","title":"Los distintos modos de lo urbano","authors":[{"name":"Enrique Rodríguez Caporalli"}],"abstract":"","source":"CrossRef","year":2017,"language":"en","subjects":null,"doi":"10.18046/recs.i21.2423","url":"https://doi.org/10.18046/recs.i21.2423","pdf_url":"https://200.3.192.46/revistas/index.php/revista_cs/article/download/2423/3082","is_open_access":true,"published_at":"","score":61},{"id":"crossref_10.1145/2839509.2844658","title":"igniteCS","authors":[{"name":"Erin Mindell Cannon"},{"name":"Priya Chawla"},{"name":"Katherine Lo"},{"name":"Haley Adams"}],"abstract":"","source":"CrossRef","year":2016,"language":"en","subjects":null,"doi":"10.1145/2839509.2844658","url":"https://doi.org/10.1145/2839509.2844658","is_open_access":true,"published_at":"","score":60},{"id":"crossref_10.18046/recs.i16.2044","title":"Intervención social y el debate sobre lo público","authors":[{"name":"Maria del Pilar Acosta"}],"abstract":"Reseña del libro:Grupo de Intervención y Responsabilidad Social (2014). Intervención social y el debate sobre lo público: reflexiones conceptuales y casos locales. Colección \"El Sur es Cielo Roto\", No. 9. Cali, Colombia: Universidad Icesi, Facultad de Derecho y Ciencias Sociales. 258 pp.","source":"CrossRef","year":2015,"language":"en","subjects":null,"doi":"10.18046/recs.i16.2044","url":"https://doi.org/10.18046/recs.i16.2044","pdf_url":"https://200.3.192.46/revistas/index.php/revista_cs/article/download/2044/2639","is_open_access":true,"citations":2,"published_at":"","score":59.06},{"id":"doaj_10.2168/LMCS-8(3:7)2012","title":"Bounded Arithmetic in Free Logic","authors":[{"name":"Yoriyuki Yamagata"}],"abstract":"One of the central open questions in bounded arithmetic is whether Buss'\nhierarchy of theories of bounded arithmetic collapses or not. In this paper, we\nreformulate Buss' theories using free logic and conjecture that such theories\nare easier to handle. To show this, we first prove that Buss' theories prove\nconsistencies of induction-free fragments of our theories whose formulae have\nbounded complexity. Next, we prove that although our theories are based on an\napparently weaker logic, we can interpret theories in Buss' hierarchy by our\ntheories using a simple translation. Finally, we investigate finitistic G\\\"odel\nsentences in our systems in the hope of proving that a theory in a lower level\nof Buss' hierarchy cannot prove consistency of induction-free fragments of our\ntheories whose formulae have higher complexity.","source":"DOAJ","year":2012,"language":"","subjects":["Logic","Electronic computers. Computer science"],"doi":"10.2168/LMCS-8(3:7)2012","url":"https://lmcs.episciences.org/863/pdf","pdf_url":"https://lmcs.episciences.org/863/pdf","is_open_access":true,"published_at":"","score":56},{"id":"doaj_10.2168/LMCS-8(1:21)2012","title":"Modeling Adversaries in a Logic for Security Protocol Analysis","authors":[{"name":"Joseph Y. Halpern"},{"name":"Riccardo Pucella"}],"abstract":"Logics for security protocol analysis require the formalization of an\nadversary model that specifies the capabilities of adversaries. A common model\nis the Dolev-Yao model, which considers only adversaries that can compose and\nreplay messages, and decipher them with known keys. The Dolev-Yao model is a\nuseful abstraction, but it suffers from some drawbacks: it cannot handle the\nadversary knowing protocol-specific information, and it cannot handle\nprobabilistic notions, such as the adversary attempting to guess the keys. We\nshow how we can analyze security protocols under different adversary models by\nusing a logic with a notion of algorithmic knowledge. Roughly speaking,\nadversaries are assumed to use algorithms to compute their knowledge; adversary\ncapabilities are captured by suitable restrictions on the algorithms used. We\nshow how we can model the standard Dolev-Yao adversary in this setting, and how\nwe can capture more general capabilities including protocol-specific knowledge\nand guesses.","source":"DOAJ","year":2012,"language":"","subjects":["Logic","Electronic computers. Computer science"],"doi":"10.2168/LMCS-8(1:21)2012","url":"https://lmcs.episciences.org/688/pdf","pdf_url":"https://lmcs.episciences.org/688/pdf","is_open_access":true,"published_at":"","score":56},{"id":"doaj_10.2168/LMCS-7(3:9)2011","title":"Answering Non-Monotonic Queries in Relational Data Exchange","authors":[{"name":"Andre Hernich"}],"abstract":"Relational data exchange is the problem of translating relational data from a\nsource schema into a target schema, according to a specification of the\nrelationship between the source data and the target data. One of the basic\nissues is how to answer queries that are posed against target data. While\nconsensus has been reached on the definitive semantics for monotonic queries,\nthis issue turned out to be considerably more difficult for non-monotonic\nqueries. Several semantics for non-monotonic queries have been proposed in the\npast few years. This article proposes a new semantics for non-monotonic\nqueries, called the GCWA*-semantics. It is inspired by semantics from the area\nof deductive databases. We show that the GCWA*-semantics coincides with the\nstandard open world semantics on monotonic queries, and we further explore the\n(data) complexity of evaluating non-monotonic queries under the\nGCWA*-semantics. In particular, we introduce a class of schema mappings for\nwhich universal queries can be evaluated under the GCWA*-semantics in\npolynomial time (data complexity) on the core of the universal solutions.","source":"DOAJ","year":2011,"language":"","subjects":["Logic","Electronic computers. Computer science"],"doi":"10.2168/LMCS-7(3:9)2011","url":"https://lmcs.episciences.org/904/pdf","pdf_url":"https://lmcs.episciences.org/904/pdf","is_open_access":true,"published_at":"","score":55},{"id":"doaj_10.2168/LMCS-7(2:10)2011","title":"Towards a Proof Theory of G\\\"odel Modal Logics","authors":[{"name":"George Metcalfe"},{"name":"Nicola Olivetti"}],"abstract":"Analytic proof calculi are introduced for box and diamond fragments of basic\nmodal fuzzy logics that combine the Kripke semantics of modal logic K with the\nmany-valued semantics of G\\\"odel logic. The calculi are used to establish\ncompleteness and complexity results for these fragments.","source":"DOAJ","year":2011,"language":"","subjects":["Logic","Electronic computers. Computer science"],"doi":"10.2168/LMCS-7(2:10)2011","url":"https://lmcs.episciences.org/972/pdf","pdf_url":"https://lmcs.episciences.org/972/pdf","is_open_access":true,"published_at":"","score":55},{"id":"doaj_10.2168/LMCS-6(3:17)2010","title":"Unification in the Description Logic EL","authors":[{"name":"Franz Baader"},{"name":"Barbara Morawska"}],"abstract":"The Description Logic EL has recently drawn considerable attention since, on\nthe one hand, important inference problems such as the subsumption problem are\npolynomial. On the other hand, EL is used to define large biomedical\nontologies. Unification in Description Logics has been proposed as a novel\ninference service that can, for example, be used to detect redundancies in\nontologies. The main result of this paper is that unification in EL is\ndecidable. More precisely, EL-unification is NP-complete, and thus has the same\ncomplexity as EL-matching. We also show that, w.r.t. the unification type, EL\nis less well-behaved: it is of type zero, which in particular implies that\nthere are unification problems that have no finite complete set of unifiers.","source":"DOAJ","year":2010,"language":"","subjects":["Logic","Electronic computers. Computer science"],"doi":"10.2168/LMCS-6(3:17)2010","url":"https://lmcs.episciences.org/1106/pdf","pdf_url":"https://lmcs.episciences.org/1106/pdf","is_open_access":true,"published_at":"","score":54},{"id":"doaj_10.2168/LMCS-6(4:1)2010","title":"Tree Languages Defined in First-Order Logic with One Quantifier Alternation","authors":[{"name":"Mikolaj Bojanczyk"},{"name":"Luc Segoufin"}],"abstract":"We study tree languages that can be defined in \\Delta_2 . These are tree\nlanguages definable by a first-order formula whose quantifier prefix is forall\nexists, and simultaneously by a first-order formula whose quantifier prefix is\n. For the quantifier free part we consider two signatures, either the\ndescendant relation alone or together with the lexicographical order relation\non nodes. We provide an effective characterization of tree and forest languages\ndefinable in \\Delta_2 . This characterization is in terms of algebraic\nequations. Over words, the class of word languages definable in \\Delta_2 forms\na robust class, which was given an effective algebraic characterization by Pin\nand Weil.","source":"DOAJ","year":2010,"language":"","subjects":["Logic","Electronic computers. Computer science"],"doi":"10.2168/LMCS-6(4:1)2010","url":"https://lmcs.episciences.org/699/pdf","pdf_url":"https://lmcs.episciences.org/699/pdf","is_open_access":true,"published_at":"","score":54},{"id":"doaj_10.2168/LMCS-6(4:5)2010","title":"Refinement Types for Logical Frameworks and Their Interpretation as Proof Irrelevance","authors":[{"name":"William Lovas"},{"name":"Frank Pfenning"}],"abstract":"Refinement types sharpen systems of simple and dependent types by offering\nexpressive means to more precisely classify well-typed terms. We present a\nsystem of refinement types for LF in the style of recent formulations where\nonly canonical forms are well-typed. Both the usual LF rules and the rules for\ntype refinements are bidirectional, leading to a straightforward proof of\ndecidability of typechecking even in the presence of intersection types.\nBecause we insist on canonical forms, structural rules for subtyping can now be\nderived rather than being assumed as primitive. We illustrate the expressive\npower of our system with examples and validate its design by demonstrating a\nprecise correspondence with traditional presentations of subtyping. Proof\nirrelevance provides a mechanism for selectively hiding the identities of terms\nin type theories. We show that LF refinement types can be interpreted as\npredicates using proof irrelevance, establishing a uniform relationship between\ntwo previously studied concepts in type theory. The interpretation and its\ncorrectness proof are surprisingly complex, lending support to the claim that\nrefinement types are a fundamental construct rather than just a convenient\nsurface syntax for certain uses of proof irrelevance.","source":"DOAJ","year":2010,"language":"","subjects":["Logic","Electronic computers. Computer science"],"doi":"10.2168/LMCS-6(4:5)2010","url":"https://lmcs.episciences.org/1063/pdf","pdf_url":"https://lmcs.episciences.org/1063/pdf","is_open_access":true,"published_at":"","score":54},{"id":"crossref_10.1109/tns.1972.4326702","title":"Performance Studies of Photomutipliers Having Dynodes with GaP(Cs) Secondary Emitting Surface","authors":[{"name":"B. Leskovar"},{"name":"C. C. Lo"}],"abstract":"","source":"CrossRef","year":1972,"language":"en","subjects":null,"doi":"10.1109/tns.1972.4326702","url":"https://doi.org/10.1109/tns.1972.4326702","is_open_access":true,"citations":24,"published_at":"","score":50.72},{"id":"doaj_10.46298/dmtcs.3471","title":"Undecidable problems concerning densities of languages","authors":[{"name":"Jakub Kozik"}],"abstract":"In this paper we prove that the question whether a language presented by a context free grammar has density, is undecidable. Moreover we show that there is no algorithm which, given two unambiguous context free grammars on input, decides whether the language defined by the first grammar has a relative density in the language defined by the second one. Our techniques can be extended to show that this problem is undecidable even for languages given by grammars from $LL(k)$ (for sufficiently large fixed $k ∈ \\mathbb{N} )$.","source":"DOAJ","year":2005,"language":"","subjects":["Mathematics"],"doi":"10.46298/dmtcs.3471","url":"https://dmtcs.episciences.org/3471/pdf","pdf_url":"https://dmtcs.episciences.org/3471/pdf","is_open_access":true,"published_at":"","score":50},{"id":"doaj_10.46298/dmtcs.3473","title":"On-line Adaptive Chain Covering of Upgrowing Posets","authors":[{"name":"Bartłomiej Bosek"},{"name":"Piotr Micek"}],"abstract":"We analyze on-line chain partitioning problem and its variants as a two-person game. One person (Spoiler) builds an on-line poset presenting one point at time. The other one (Algorithm) assigns new point to a chain. Kierstead gave a strategy for Algorithm showing that width w posets can be on-line chain partitioned into $\\frac{{5}^{w-1}}{4}$ chains. Felsner proved that if Spoiler presents an upgrowing poset, i.e., each new point is maximal at the moment of its arrival then there is a strategy for Algorithm using at most $\\binom{w+1}{2}$ chains and it is best possible. An adaptive variant of this problem allows Algorithm to assign to the new point a set of chains and than to remove some of them (but not all) while covering next points. Felsner stated a hypothesis that in on-line adaptive chain covering of upgrowing posets Algorithm may use smaller number of chains than in non-adaptive version. In this paper we provide an argument suggesting that it is true. We present a class of upgrowing posets in which Spoiler has a strategy forcing Algorithm to use at least $\\binom{w+1}{2}$ chains (in non-adaptive version) and Algorithm has a strategy using at most $O(w\\sqrt{w})$ chains in adaptive version.","source":"DOAJ","year":2005,"language":"","subjects":["Mathematics"],"doi":"10.46298/dmtcs.3473","url":"https://dmtcs.episciences.org/3473/pdf","pdf_url":"https://dmtcs.episciences.org/3473/pdf","is_open_access":true,"published_at":"","score":50},{"id":"doaj_10.46298/dmtcs.3468","title":"Non-Determinism and Nash Equilibria for Sequential Game over Partial Order","authors":[{"name":"Stéphane Le Roux"}],"abstract":"In sequential games of traditional game theory, backward induction guarantees existence of Nash equilibrium by yielding a sub-game perfect equilibrium. But if payoffs range over a partially ordered set instead of the reals, then the backward induction predicate does no longer imply the Nash equilibrium predicate. Non-determinism is a solution: a suitable non-deterministic backward induction function returns a non-deterministic strategy profile which is a non-deterministic Nash equilibrium. The main notions and results in this article are constructive, conceptually simple and formalised in the proof assistant Coq.","source":"DOAJ","year":2005,"language":"","subjects":["Mathematics"],"doi":"10.46298/dmtcs.3468","url":"https://dmtcs.episciences.org/3468/pdf","pdf_url":"https://dmtcs.episciences.org/3468/pdf","is_open_access":true,"published_at":"","score":50},{"id":"doaj_10.46298/dmtcs.267","title":"The First-Order Theory of Ordering Constraints over Feature Trees","authors":[{"name":"Martin Müller"},{"name":"Joachim Niehren"},{"name":"Ralf Treinen"}],"abstract":"The system FT\u003c of ordering constraints over feature trees has been introduced as an extension of the system FT of equality constraints over feature trees. We investigate the first-order theory of FT\u003c and its fragments in detail, both over finite trees and over possibly infinite trees. We prove that the first-order theory of FT\u003c is undecidable, in contrast to the first-order theory of FT which is well-known to be decidable. We show that the entailment problem of FT\u003c with existential quantification is PSPACE-complete. So far, this problem has been shown decidable, coNP-hard in case of finite trees, PSPACE-hard in case of arbitrary trees, and cubic time when restricted to quantifier-free entailment judgments. To show PSPACE-completeness, we show that the entailment problem of FT\u003c with existential quantification is equivalent to the inclusion problem of non-deterministic finite automata. Available at http://www.ps.uni-saarland.de/Publications/documents/FTSubTheory_98.pdf","source":"DOAJ","year":2001,"language":"","subjects":["Mathematics"],"doi":"10.46298/dmtcs.267","url":"https://dmtcs.episciences.org/267/pdf","pdf_url":"https://dmtcs.episciences.org/267/pdf","is_open_access":true,"published_at":"","score":50}],"total":242419,"page":1,"page_size":20,"sources":["DOAJ","CrossRef"],"query":"cs.LO"}