Relevant bibliographies by topics / Bounded-degree logics

Contents

  1. Journal articles
  2. Dissertations / Theses
  3. Book chapters
  4. Conference papers

Academic literature on the topic 'Bounded-degree logics'

Author: Grafiati
Published: 4 June 2021
Last updated: 1 February 2022

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Consult the lists of relevant articles, books, theses, conference reports, and other scholarly sources on the topic 'Bounded-degree logics.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Journal articles on the topic "Bounded-degree logics"

1

Juba, Brendan. "Polynomial-Time Probabilistic Reasoning with Partial Observations via Implicit Learning in Probability Logics." Proceedings of the AAAI Conference on Artificial Intelligence 33 (July 17, 2019): 7866–75. http://dx.doi.org/10.1609/aaai.v33i01.33017866.

Full text
Abstract:
Standard approaches to probabilistic reasoning require that one possesses an explicit model of the distribution in question. But, the empirical learning of models of probability distributions from partial observations is a problem for which efficient algorithms are generally not known. In this work we consider the use of bounded-degree fragments of the “sum-of-squares” logic as a probability logic. Prior work has shown that we can decide refutability for such fragments in polynomial-time. We propose to use such fragments to decide queries about whether a given probability distribution satisfie
APA, Harvard, Vancouver, ISO, and other styles
2

Slaman, Theodore A., and Michael~E Mytilinaios. "Differences between Resource Bounded Degree Structures." Notre Dame Journal of Formal Logic 44, no. 1 (2003): 1–12. http://dx.doi.org/10.1305/ndjfl/1082637612.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Stephan, Frank. "On the structures inside truth-table degrees." Journal of Symbolic Logic 66, no. 2 (2001): 731–70. http://dx.doi.org/10.2307/2695042.

Full text
Abstract:
AbstractThe following theorems on the structure inside nonrecursive truth-table degrees are established: Dëgtev's result that the number of bounded truth-table degrees inside a truth-table degree is at least two is improved by showing that this number is infinite. There are even infinite chains and antichains of bounded truth-table degrees inside every truth-table degree. The latter implies an affirmative answer to the following question of Jockusch: does every truth-table degree contain an infinite antichain of many-one degrees? Some but not all truth-table degrees have a least bounded truth-
APA, Harvard, Vancouver, ISO, and other styles
4

Kuske, Dietrich, та Markus Lohrey. "First-order and counting theories of ω-automatic structures". Journal of Symbolic Logic 73, № 1 (2008): 129–50. http://dx.doi.org/10.2178/jsl/1208358745.

Full text
Abstract:
AbstractThe logic extends first-order logic by a generalized form of counting quantifiers (“the number of elements satisfying … belongs to the set C”). This logic is investigated for structures with an injectively ω-automatic presentation. If first-order logic is extended by an infinity-quantifier, the resulting theory of any such structure is known to be decidable [6]. It is shown that, as in the case of automatic structures [21], also modulo-counting quantifiers as well as infinite cardinality quantifiers (“there are many elements satisfying …”) lead to decidable theories. For a structure of
APA, Harvard, Vancouver, ISO, and other styles
5

Seese, Detlef. "Linear time computable problems and first-order descriptions." Mathematical Structures in Computer Science 6, no. 6 (1996): 505–26. http://dx.doi.org/10.1017/s0960129500070079.

Full text
Abstract:
It is well known that every algorithmic problem definable by a formula of first-order logic can be solved in polynomial time, since all these problems are inL(see Aho and Ullman (1979) and Immerman (1987)). Using an old technique of Hanf (Hanf 1965) and other techniques developed to prove the decidability of formal theories in mathematical logic, it is shown that an arbitraryFO-problem over relational structures of bounded degree can be solved in linear time.
APA, Harvard, Vancouver, ISO, and other styles
6

Meinel, Christoph. "Logic vs. complexity theoretic properties of the graph accessibility problem for directed graphs of bounded degree." Information Processing Letters 34, no. 3 (1990): 143–46. http://dx.doi.org/10.1016/0020-0190(90)90093-d.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Hella, Lauri, Leonid Libkin, and Juha Nurmonen. "Notions of locality and their logical characterizations over finite models." Journal of Symbolic Logic 64, no. 4 (1999): 1751–73. http://dx.doi.org/10.2307/2586810.

Full text
Abstract:
AbstractMany known tools for proving expressibility bounds for first-ordér logic are based on one of several locality properties. In this paper we characterize the relationship between those notions of locality. We note that Gaifman's locality theorem gives rise to two notions: one deals with sentences and one with open formulae. We prove that the former implies Hanf's notion of locality, which in turn implies Gaifman's locality for open formulae. Each of these implies the bounded degree property, which is one of the easiest tools for proving expressibility bounds. These results apply beyond t
APA, Harvard, Vancouver, ISO, and other styles
8

NIES, ANDRÉ. "PARAMETER DEFINABILITY IN THE RECURSIVELY ENUMERABLE DEGREES." Journal of Mathematical Logic 03, no. 01 (2003): 37–65. http://dx.doi.org/10.1142/s0219061303000236.

Full text
Abstract:
The biinterpretability conjecture for the r.e. degrees asks whether, for each sufficiently large k, the [Formula: see text] relations on the r.e. degrees are uniformly definable from parameters. We solve a weaker version: for each k ≥ 7, the [Formula: see text] relations bounded from below by a nonzero degree are uniformly definable. As applications, we show that Low 1 is parameter definable, and we provide methods that lead to a new example of a ∅-definable ideal. Moreover, we prove that automorphisms restricted to intervals [d, 1], d ≠ 0, are [Formula: see text]. We also show that, for each
APA, Harvard, Vancouver, ISO, and other styles
9

Calvert, Wesley. "The isomorphism problem for computable Abelian p-groups of bounded length." Journal of Symbolic Logic 70, no. 1 (2005): 331–45. http://dx.doi.org/10.2178/jsl/1107298523.

Full text
Abstract:
AbstractTheories of classification distinguish classes with some good structure theorem from those for which none is possible. Some classes (dense linear orders, for instance) are non-classifiable in general, but are classifiable when we consider only countable members. This paper explores such a notion for classes of computable structures by working out a sequence of examples.We follow recent work by Goncharov and Knight in using the degree of the isomorphism problem for a class to distinguish classifiable classes from non-classifiable. In this paper, we calculate the degree of the isomorphis
APA, Harvard, Vancouver, ISO, and other styles
10

HENRY, SIMON. "AN ABSTRACT ELEMENTARY CLASS NONAXIOMATIZABLE IN." Journal of Symbolic Logic 84, no. 3 (2019): 1240–51. http://dx.doi.org/10.1017/jsl.2019.25.

Full text
Abstract:
AbstractWe show that for any uncountable cardinal λ, the category of sets of cardinality at least λ and monomorphisms between them cannot appear as the category of points of a topos, in particular is not the category of models of a ${L_{\infty ,\omega }}$-theory. More generally we show that for any regular cardinal $\kappa < \lambda$ it is neither the category of κ-points of a κ-topos, in particular, nor the category of models of a ${L_{\infty ,\kappa }}$-theory.The proof relies on the construction of a categorified version of the Scott topology, which constitute a left adjoint to the funct
APA, Harvard, Vancouver, ISO, and other styles
More sources

Dissertations / Theses on the topic "Bounded-degree logics"

1

Ferreira, Francicleber Martins. "Expressividade e Complexidade em LÃgicas Preferenciais, HÃbridas e de Grau Limitado." Universidade Federal do CearÃ, 2012. http://www.teses.ufc.br/tde_busca/arquivo.php?codArquivo=9071.

Full text
Abstract:
CoordenaÃÃo de AperfeiÃoamento de Pessoal de NÃvel Superior<br>NÃs investigamos a teoria dos modelos de LÃgicas Preferenciais, LÃgica HÃbrida e fragmentos da LÃgica de Segunda-Ordem com relaÃÃo a modelos finitos. A semÃnticas dessas lÃgicas diferem da abordagem clÃssica pelo uso de relaÃÃes entre modelos ou por restringir a cardinalidade dos modelos a cardinais finitos. Este trabalho tem trÃs partes. Na primeira parte deste trabalho nÃs estudamos a teoria dos modelos de lÃgicas preferenciais. LÃgicas preferenciais surgem no contexto do raciocÃnio nÃo-monotÃnico em InteligÃncia Artificial. A pr
APA, Harvard, Vancouver, ISO, and other styles
2

Ferreira, Francicleber Martins. "Expressividade e complexidade em lógicas preferenciais, híbridas e de grau limitado." reponame:Repositório Institucional da UFC, 2012. http://www.repositorio.ufc.br/handle/riufc/18677.

Full text
Abstract:
FERREIRA, Francicleber Martins. Expressividade e complexidade em lógicas preferenciais, híbridas e de grau limitado. 2012. 130 f. Tese (Doutorado em ciência da computação)- Universidade Federal do Ceará, Fortaleza-CE, 2012.<br>Submitted by Elineudson Ribeiro (elineudsonr@gmail.com) on 2016-07-20T11:58:10Z No. of bitstreams: 1 2012_tese_fmferreira.pdf: 772301 bytes, checksum: b1e1a404221e38ffb8e0712513749a4c (MD5)<br>Approved for entry into archive by Rocilda Sales (rocilda@ufc.br) on 2016-07-25T11:47:07Z (GMT) No. of bitstreams: 1 2012_tese_fmferreira.pdf: 772301 bytes, checksum: b1e1a404221e3
APA, Harvard, Vancouver, ISO, and other styles
3

Heimberg, Lucas. "Complexity of Normal Forms on Structures of Bounded Degree." Doctoral thesis, Humboldt-Universität zu Berlin, 2018. http://dx.doi.org/10.18452/19205.

Full text
Abstract:
Normalformen drücken semantische Eigenschaften einer Logik durch syntaktische Restriktionen aus. Sie ermöglichen es Algorithmen, Grenzen der Ausdrucksstärke einer Logik auszunutzen. Ein Beispiel ist die Lokalität der Logik erster Stufe (FO), die impliziert, dass Graph-Eigenschaften wie Erreichbarkeit oder Zusammenhang nicht FO-definierbar sind. Gaifman-Normalformen drücken die Bedeutung einer FO-Formel als Boolesche Kombination lokaler Eigenschaften aus. Sie haben eine wichtige Rolle in Model-Checking Algorithmen für Klassen dünn besetzter Graphen, deren Laufzeit durch die Größe der auszuwert
APA, Harvard, Vancouver, ISO, and other styles
4

Akishev, Galym. "Monadic bounded algebras : a thesis submitted to the Victoria University of Wellington in fulfilment of the requirements for the degree of Doctor of Philosophy in Mathematics /." ResearchArchive@Victoria e-Thesis, 2009. http://hdl.handle.net/10063/915.

Full text
APA, Harvard, Vancouver, ISO, and other styles

Book chapters on the topic "Bounded-degree logics"

1

Kuske, Dietrich, and Markus Lohrey. "Automatic Structures of Bounded Degree Revisited." In Computer Science Logic. Springer Berlin Heidelberg, 2009. http://dx.doi.org/10.1007/978-3-642-04027-6_27.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Lohrey, Markus. "Automatic Structures of Bounded Degree." In Logic for Programming, Artificial Intelligence, and Reasoning. Springer Berlin Heidelberg, 2003. http://dx.doi.org/10.1007/978-3-540-39813-4_25.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Shoudai, Takayoshi, Satoshi Matsumoto, and Yusuke Suzuki. "Distributional Learning of Regular Formal Graph System of Bounded Degree." In Inductive Logic Programming. Springer International Publishing, 2017. http://dx.doi.org/10.1007/978-3-319-63342-8_6.

Full text
APA, Harvard, Vancouver, ISO, and other styles

Conference papers on the topic "Bounded-degree logics"

1

Grange, Julien. "Successor-Invariant First-Order Logic on Classes of Bounded Degree (Extended Abstract)." In Thirtieth International Joint Conference on Artificial Intelligence {IJCAI-21}. International Joint Conferences on Artificial Intelligence Organization, 2021. http://dx.doi.org/10.24963/ijcai.2021/649.

Full text
Abstract:
We study the expressive power of successor-invariant first-order logic, which is an extension of first-order logic where the usage of a successor relation on the vertices of the graph is allowed, as long as the validity of formulas is independent on the choice of a particular successor. We show that when the degree is bounded, successor-invariant first-order logic is no more expressive than first-order logic.
APA, Harvard, Vancouver, ISO, and other styles
2

Harwath, Frederik, Lucas Heimberg, and Nicole Schweikardt. "Preservation and decomposition theorems for bounded degree structures." In CSL-LICS '14: JOINT MEETING OF the Twenty-Third EACSL Annual Conference on COMPUTER SCIENCE LOGIC. ACM, 2014. http://dx.doi.org/10.1145/2603088.2603130.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Grange, Julien. "Successor-Invariant First-Order Logic on Classes of Bounded Degree." In LICS '20: 35th Annual ACM/IEEE Symposium on Logic in Computer Science. ACM, 2020. http://dx.doi.org/10.1145/3373718.3394767.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Heimberg, Lucas, Dietrich Kuske, and Nicole Schweikardt. "An Optimal Gaifman Normal Form Construction for Structures of Bounded Degree." In 2013 Twenty-Eighth Annual IEEE/ACM Symposium on Logic in Computer Science (LICS 2013). IEEE, 2013. http://dx.doi.org/10.1109/lics.2013.11.

Full text
APA, Harvard, Vancouver, ISO, and other styles
You might also be interested in the extended bibliographies on the topic 'Bounded-degree logics' for particular source types:
Journal articles
We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!

To the bibliography