Informacja

Drogi użytkowniku, aplikacja do prawidłowego działania wymaga obsługi JavaScript. Proszę włącz obsługę JavaScript w Twojej przeglądarce.

Wyszukujesz frazę "-completeness" wg kryterium: Temat


Tytuł:
Completeness, Categoricity and Imaginary Numbers: The Debate on Husserl
Autorzy:
Aranda, Víctor
Powiązania:
https://bibliotekanauki.pl/articles/750024.pdf
Data publikacji:
2020
Wydawca:
Uniwersytet Łódzki. Wydawnictwo Uniwersytetu Łódzkiego
Tematy:
Husserl
completeness
categoricity
relative and absolute definiteness
imaginary numbers
Opis:
Husserl's two notions of "definiteness" enabled him to clarify the problem of imaginary numbers. The exact meaning of these notions is a topic of much controversy. A "definite" axiom system has been interpreted as a syntactically complete theory, and also as a categorical one. I discuss whether and how far these readings manage to capture Husserl's goal of elucidating the problem of imaginary numbers, raising objections to both positions. Then, I suggest an interpretation of "absolute definiteness" as semantic completeness and argue that this notion does not suffice to explain Husserl's solution to the problem of imaginary numbers.
Źródło:
Bulletin of the Section of Logic; 2020, 49, 2
0138-0680
2449-836X
Pojawia się w:
Bulletin of the Section of Logic
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Balanced problems on graphs with categorization of edges
Autorzy:
Berežný, Štefan
Lacko, Vladimír
Powiązania:
https://bibliotekanauki.pl/articles/743374.pdf
Data publikacji:
2003
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
algorithms on graphs
categorization of edges
NP-completeness
Opis:
Suppose a graph G = (V,E) with edge weights w(e) and edges partitioned into disjoint categories S₁,...,Sₚ is given. We consider optimization problems on G defined by a family of feasible sets (G) and the following objective function:
$L₅(D) = max_{1≤i≤p} (max_{e ∈ S_i ∩ D} w(e) - min_{e ∈ S_i ∩ D} w(e))$
For an arbitrary number of categories we show that the L₅-perfect matching, L₅-a-b path, L₅-spanning tree problems and L₅-Hamilton cycle (on a Halin graph) problem are NP-complete.
We also summarize polynomiality results concerning above objective functions for arbitrary and for fixed number of categories.
Źródło:
Discussiones Mathematicae Graph Theory; 2003, 23, 1; 5-21
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Użyteczność danych o lasach udostępnianych w serwisie OpenStreetMap
Usability of the OpenStreetMap forest data
Autorzy:
Bielecka, E.
Leszczyńska, M.
Powiązania:
https://bibliotekanauki.pl/articles/986666.pdf
Data publikacji:
2018
Wydawca:
Polskie Towarzystwo Leśne
Tematy:
lesnictwo
lasy
zrodla danych
serwis OpenStreetMap
kompletnosc danych
wiarygodnosc
forest
osm
spatial data quality
completeness
location accuracy
Opis:
OpenStreetMap (OSM) is a collaborative project covering the whole World with topographic data. Data are edited by volunteer users on the basis of satellite images, ortophotomaps and GPS traces, therefore are of diversified quality, especially completeness and positional accuracy. The aim of this study was to evaluate the usability of OSM forest data for Poland. We proved that positional accuracy, expressed by RMSE that equals to 16 m, was comparable with the national topographic data at the scale 1:10 000. However 3.5% of the outliers were noticed, for which the positional accuracy amounted to about 300 m. The completeness of the OSM data in May 2017, computed on the basis of Czekanowski matching feature area−based completeness index, equalled 86% and was still increasing. The lowest value of the completeness was observed for lubuskie voivodeship (76.4%), while the highest (92.5%) for zachodniopomorskie. For ten voivodeships the completeness of forest cover was greater than national average. In general, there were only a few forest polygons with their name or other pertinent characteristics like tree type (coniferous/deciduous) attributed by the editors. Logical consistency was nearly perfect as only 5.8% of the polygons were topologically incorrect. Forest definition as ‘an area dominated by trees’, is very similar in national topographic data and in OSM, both are based on physical characteristics of the surface of the Earth. Contrary to the national spatial data, OSM data are constantly updated, free and available without restrictions. It constitutes valuable alternative data source for all users. However, the heterogeneity of these data should also be kept in mind, while they are used in analysis and decision process support.
Źródło:
Sylwan; 2018, 162, 06; 460-468
0039-7660
Pojawia się w:
Sylwan
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
OpenStreetMap – building data completeness visualization in terms of “Fitness for purpose”
Autorzy:
Borkowska, Sylwia
Bielecka, Elzbieta
Pokonieczny, Krzysztof
Powiązania:
https://bibliotekanauki.pl/articles/43852777.pdf
Data publikacji:
2023
Wydawca:
Polska Akademia Nauk. Czasopisma i Monografie PAN
Tematy:
baza danych
jakość danych
lokalizacja budynku
data completeness
data quality
bivariate choropleth map
OSM
VGI
Opis:
The purpose of this article was to provide the user with information about the number of buildings in the analyzed OpenStreetMap (OSM) dataset in the form of data completeness indicators, namely the standard OSM building areal completeness index (C Index), the numerical completeness index (COUNT Index) and OSM building location accuracy index (TP Index). The official Polish vector database BDOT10k (Database of Topographic Objects) was designated as the reference dataset. Analyses were carried out for Piaseczno County in Poland, differentiated by land cover structure and urbanization level. The results were presented in the form of a bivariate choropleth map with an individually selected class interval suitable for the statistical distribution of the analyzed data. The results confirm that the completeness of OSM buildings close to 100% was obtained mainly in built-up areas. Areas with a commission of OSM buildings were distinguished in terms of area and number of buildings. Lower values of completeness rates were observed in less urbanized areas. The developed methodology for assessing the quality of OSM building data and visualizing the quality results to assist the user in selecting a dataset is universal and can be applied to any OSM polygon features, as well as for peer review of other spatial datasets of comparable thematic scope and detail.
Źródło:
Advances in Geodesy and Geoinformation; 2023, 72, 1; art. no. e35, 2023
2720-7242
Pojawia się w:
Advances in Geodesy and Geoinformation
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
A note on hardness of multiprocessor scheduling with scheduling solution space tree
Autorzy:
Dwibedy, Debasis
Mohanty, Rakesh
Powiązania:
https://bibliotekanauki.pl/articles/27312879.pdf
Data publikacji:
2023
Wydawca:
Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
Tematy:
combinatorial structures
computational complexity
hardness
makespan
multiprocessor scheduling
multiuser
NP-completeness
nondeterministic algorithms
reduction
scheduling solution space tree
Opis:
We study the hardness of the non-preemptive scheduling problem of a list of independent jobs on a set of identical parallel processors with a makespan minimization objective. We make a maiden attempt to explore the combinatorial structure of the problem by introducing a scheduling solution space tree (SSST) as a novel data structure. We formally define and characterize the properties of SSST through our analytical results. We show that the multiprocessor scheduling problem is N P-complete with an alternative technique using SSST and weighted scheduling solution space tree (WSSST) data structures. We propose a non-deterministic polynomial-time algorithm called magic scheduling (MS) based on the reduction framework. We also define a new variant of multiprocessor scheduling by including the user as an additional input parameter, which we called the multiuser multiprocessor scheduling problem (MUMPSP). We also show that MUMPSP is N P-complete. We conclude the article by exploring several non-trivial research challenges for future research investigations.
Źródło:
Computer Science; 2023, 24 (1); 53--74
1508-2806
2300-7036
Pojawia się w:
Computer Science
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Unifiability and Structural Completeness in Relation Algebras and in Products of Modal Logic S5
Autorzy:
Dzik, Wojciech
Wróbel, Beniamin
Powiązania:
https://bibliotekanauki.pl/articles/749956.pdf
Data publikacji:
2015
Wydawca:
Uniwersytet Łódzki. Wydawnictwo Uniwersytetu Łódzkiego
Tematy:
admissible rules
passive rules
unification
projective unification
almost structural completeness
n-modal logic S5n
relation algebras
representable diagonal-free cylindric algebras
Opis:
Unifiability of terms (and formulas) and structural completeness in the variety of relation algebras RA and in the products of modal logic S5 is investigated. Nonunifiable terms (formulas) which are satisfiable in varieties (in logics) are exhibited. Consequently, RA and products of S5 as well as representable diagonal-free n-dimensional cylindric algebras, RDfn, are almost structurally complete but not structurally complete. In case of S5n a basis for admissible rules and the form of all passive rules are provided.
Źródło:
Bulletin of the Section of Logic; 2015, 44, 1-2
0138-0680
2449-836X
Pojawia się w:
Bulletin of the Section of Logic
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Carathéodory completeness on the plane
Autorzy:
Edigarian, Armen
Powiązania:
https://bibliotekanauki.pl/articles/2188102.pdf
Data publikacji:
2019
Wydawca:
Uniwersytet Jagielloński. Wydawnictwo Uniwersytetu Jagiellońskiego
Tematy:
Carathéodory distance
completeness
Melnikov's theorem
peak function
Opis:
M. A. Selby [8-10] and, independently, N. Sibony [11] proved that on the complex plane c-completeness is equivalent to c-finitely compactness. Their proofs are quite similar and are based on [4]. We give more refined equivalent conditions and, along the way, simplify the proofs.
Źródło:
Universitatis Iagellonicae Acta Mathematica; 2019, 56; 15-21
2084-3828
0083-4386
Pojawia się w:
Universitatis Iagellonicae Acta Mathematica
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Equitable Colorings Of Corona Multiproducts Of Graphs
Autorzy:
Furmánczyk, Hanna
Kubale, Marek
Mkrtchyan, Vahan V.
Powiązania:
https://bibliotekanauki.pl/articles/31341573.pdf
Data publikacji:
2017-11-27
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
corona graph
equitable chromatic number
equitable coloring conjecture
equitable graph coloring
multiproduct of graphs
NP-completeness
polynomial algorithm
Opis:
A graph is equitably k-colorable if its vertices can be partitioned into k independent sets in such a way that the numbers of vertices in any two sets differ by at most one. The smallest k for which such a coloring exists is known as the equitable chromatic number of G and denoted by χ=(G). It is known that the problem of computation of χ=(G) is NP-hard in general and remains so for corona graphs. In this paper we consider the same model of coloring in the case of corona multiproducts of graphs. In particular, we obtain some results regarding the equitable chromatic number for the l-corona product G ◦l H, where G is an equitably 3- or 4-colorable graph and H is an r-partite graph, a cycle or a complete graph. Our proofs are mostly constructive in that they lead to polynomial algorithms for equitable coloring of such graph products provided that there is given an equitable coloring of G. Moreover, we confirm the Equitable Coloring Conjecture for corona products of such graphs. This paper extends the results from [H. Furmánczyk, K. Kaliraj, M. Kubale and V.J. Vivin, Equitable coloring of corona products of graphs, Adv. Appl. Discrete Math. 11 (2013) 103–120].
Źródło:
Discussiones Mathematicae Graph Theory; 2017, 37, 4; 1079-1094
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
A Note on Polynomial Algorithm for Cost Coloring of Bipartite Graphs with Δ ≤ 4
Autorzy:
Giaro, Krzysztof
Kubale, Marek
Powiązania:
https://bibliotekanauki.pl/articles/31526308.pdf
Data publikacji:
2020-08-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
bipartite graph
chromatic sum
cost coloring
NP-completeness
polynomial algorithm
Opis:
In the note we consider vertex coloring of a graph in which each color has an associated cost which is incurred each time the color is assigned to a vertex. The cost of coloring is the sum of costs incurred at each vertex. We show that the minimum cost coloring problem for n-vertex bipartite graph of degree Δ ≤ 4 can be solved in O(n2) time. This extends Jansen’s result [K. Jansen, The optimum cost chromatic partition problem, in: Proc. CIAC’97, Lecture Notes in Comput. Sci. 1203 (1997) 25–36] for paths and cycles to subgraphs of biquartic graphs.
Źródło:
Discussiones Mathematicae Graph Theory; 2020, 40, 3; 885-891
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Efficient list cost coloring of vertices and/or edges of bounded cyclicity graphs
Autorzy:
Giaro, Krzysztof
Kubale, Marek
Powiązania:
https://bibliotekanauki.pl/articles/744404.pdf
Data publikacji:
2009
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
cost coloring
dynamic programming
list coloring
NP-completeness
polynomial-time algorithm
Opis:
We consider a list cost coloring of vertices and edges in the model of vertex, edge, total and pseudototal coloring of graphs. We use a dynamic programming approach to derive polynomial-time algorithms for solving the above problems for trees. Then we generalize this approach to arbitrary graphs with bounded cyclomatic numbers and to their multicolorings.
Źródło:
Discussiones Mathematicae Graph Theory; 2009, 29, 2; 361-376
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Tentative division of Latin adverbs of degree
Próba podziału łacińskich przysłówków stopnia
Autorzy:
Górska, Małgorzata
Powiązania:
https://bibliotekanauki.pl/articles/1882754.pdf
Data publikacji:
2015
Wydawca:
Katolicki Uniwersytet Lubelski Jana Pawła II. Towarzystwo Naukowe KUL
Tematy:
stopniowanie
przysłówki stopnia
wykładniki gradacji
intensywność
kompletność
dostateczność i nadmiar
comparison
adverbs of degree
indices of gradation
intensity
completeness
sufficiency and excess
Opis:
Artykuł jest próbą podziału łacińskich leksemów służących do wskazywania bezwzględnego stopnia cechy lub stanu, określanego przez predykaty gradualne, tradycyjnie nazywanych przysłówkami stopnia. Proponuje się rozróżnianie czterech grup wykładników stopnia, charakteryzujących cechę lub stan ze względu na kategorie intensywności, kompletności, dostateczności i nadmiaru: (1) wykładniki intensywności: a. intensyfikatory, wskazujące na wysoki stopień cechu lub stanu (valde, multum, magnopere/magno opere, admodum, bene, male, sane, plane, non mediocriter, abunde, impense, vehementer, graviter, egregie, eximie, mire, mirifice, mirabiliter), b. dezintensyfikatory, wskazujące na niski stopień cechy lub stanu (non valde, non magnopere, non admodum, male, mediocriter); (2) wykładniki kompletności: a. wskazujące na pełny stopień cechy lub stanu (bene, male, plane, admodum, longe, omnino), b. wskazujące na niepełny stopień cechy lub stanu (prope, paene, non plane); (3) wykładniki dostateczności: a. wskazujące na dostateczny stopień cechy lub stanu (satis/sat), b. wskazujące na niedostateczny stopień cechy lub stanu (non satis/sat, parum) i (4) wykładniki nadmiaru: a. wskazujące na nadmiar cechy lub stanu (nimis/nimium, oppido), b. wskazujące na brak nadmiaru cechy lub stanu (non nimis).
The paper is an attempt of dividing Latin lexemes of the nonrelative degree of a property or state, which is expressed by gradable predicates, traditionally called adverbs of degree. The disitnction of four groups of degree indices is proposed, which characterize a property or state according to categories of intensity, completeness, sufficiency and excess, i.e. (1) Indices of intensity: a. intensifiers describing the high degree of a property or state (valde, multum, magnopere/magno opere, admodum, bene, male, sane, plane, non mediocriter, abunde, impense, vehementer, graviter, egregie, eximie, mire, mirifice, mirabiliter), b. disintensifiers describing the low degree of a property or state (non valde, non magnopere, non admodum, male, mediocriter); (2) Indices of completeness: a. describing the complete degree of a property or state (bene, male, plane, admodum, longe, omnino), b. describing the incomplete degree of a property or state (prope, paene, non plane); (3) Indices of sufficiency: a. describing the sufficient degree of a property or state (satis/sat), b. describing the insufficient degree of a property or state (non satis/sat, parum) and (4) Indices of excess: a. describing the excess of a property or state (nimis/nimium, oppido), b. describing the lack of excess of a property or state (non nimis).
Źródło:
Roczniki Humanistyczne; 2015, 63, 3; 177-198
0035-7707
Pojawia się w:
Roczniki Humanistyczne
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
On the completeness of decomposable properties of graphs
Autorzy:
Hałuszczak, Mariusz
Vateha, Pavol
Powiązania:
https://bibliotekanauki.pl/articles/744156.pdf
Data publikacji:
1999
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
decomposition
hereditary property
completeness
Opis:
Let ₁,₂ be additive hereditary properties of graphs. A (₁,₂)-decomposition of a graph G is a partition of E(G) into sets E₁, E₂ such that induced subgraph $G[E_i]$ has the property $_i$, i = 1,2. Let us define a property ₁⊕₂ by {G: G has a (₁,₂)-decomposition}.
A property D is said to be decomposable if there exists nontrivial additive hereditary properties ₁, ₂ such that D = ₁⊕₂. In this paper we determine the completeness of some decomposable properties and we characterize the decomposable properties of completeness 2.
Źródło:
Discussiones Mathematicae Graph Theory; 1999, 19, 2; 229-236
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
An Arithmetically Complete Predicate Modal Logic
Autorzy:
Hao, Yunge
Tourlakis, George
Powiązania:
https://bibliotekanauki.pl/articles/2033850.pdf
Data publikacji:
2021-08-23
Wydawca:
Uniwersytet Łódzki. Wydawnictwo Uniwersytetu Łódzkiego
Tematy:
Predicate modal logic
arithmetic completeness
logic GL
Solovay's theorem
equational proofs
Opis:
This paper investigates a first-order extension of GL called \(\textup{ML}^3\). We outline briefly the history that led to \(\textup{ML}^3\), its key properties and some of its toolbox: the \emph{conservation theorem}, its cut-free Gentzenisation, the ``formulators'' tool. Its semantic completeness (with respect to finite reverse well-founded Kripke models) is fully stated in the current paper and the proof is retold here. Applying the Solovay technique to those models the present paper establishes its main result, namely, that \(\textup{ML}^3\) is arithmetically complete. As expanded below, \(\textup{ML}^3\) is a first-order modal logic that along with its built-in ability to simulate general classical first-order provability―"\(\Box\)" simulating the the informal classical "\(\vdash\)"―is also arithmetically complete in the Solovay sense.
Źródło:
Bulletin of the Section of Logic; 2021, 50, 4; 513-541
0138-0680
2449-836X
Pojawia się w:
Bulletin of the Section of Logic
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
On the Complexity of the 3-Kernel Problem in Some Classes of Digraphs
Autorzy:
Hell, Pavol
Hernández-Cruz, César
Powiązania:
https://bibliotekanauki.pl/articles/30147225.pdf
Data publikacji:
2014-02-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
kernel
3-kernel
NP-completeness
multipartite tournament
cyclically 3-partite digraphs
k-quasi-transitive digraph
Opis:
Let D be a digraph with the vertex set V (D) and the arc set A(D). A subset N of V (D) is k-independent if for every pair of vertices u, v ∈ N, we have d(u, v), d(v, u) ≥ k; it is l-absorbent if for every u ∈ V (D) − N there exists v ∈ N such that d(u, v) ≤ l. A k-kernel of D is a k-independent and (k − 1)-absorbent subset of V (D). A 2-kernel is called a kernel. It is known that the problem of determining whether a digraph has a kernel (“the kernel problem”) is NP-complete, even in quite restricted families of digraphs. In this paper we analyze the computational complexity of the corresponding 3-kernel problem, restricted to three natural families of digraphs. As a consequence of one of our main results we prove that the kernel problem remains NP-complete when restricted to 3-colorable digraphs.
Źródło:
Discussiones Mathematicae Graph Theory; 2014, 34, 1; 167-185
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Algorithms for testing security in graphs
Algorytmy testujące bezpieczeństwo zbioru wierzchołków grafu
Autorzy:
Hiler, Arkadiusz
Lewoń, Robert
Małafiejski, Michał
Powiązania:
https://bibliotekanauki.pl/articles/41205262.pdf
Data publikacji:
2014
Wydawca:
Uniwersytet Kazimierza Wielkiego w Bydgoszczy
Tematy:
property tester
pseudotester
secure set
security
coNP-completeness
testowanie własności
zbiór bezpieczny
bezpieczeństwo
coNP-zupełność
Opis:
In this paper we propose new algorithmic methods giving with a high probability the correct answer to the decision problem of security in graphs. For a given graph G and a subset S of a vertex set of G we have to decide whether S is secure, i.e. every subset X of S fulfils the condition:|N[X] ∩ S| ≥ |N[X] \ S|, where N[X]is a closed neighbourhood of X in graph G. We constructed a polynomial time property pseudotester based on the heuristic using simulated annealing and tested it on graphs with induced small subgraphs G[S] being trees or graphs with a bounded degree (by 3 or 4). Our approach is a generalization of the concept of property testers known from the subject literature, but we applied our concepts to the coNP-complete problem.
W niniejszym artykule przedstawiamy metodę weryfikowania bezpieczeństwa zbioru w grafie, dającą wysokie prawdopodobieństwo poprawnej weryfikacji. Problemem jest określenie, czy dla danego grafu G oraz podzbioru S zbioru wierzchołków tego grafu zbiór S jest bezpieczny, to znaczy każdy jego podzbiór X spełnia warunek: |N[X] ∩ S| ≥ |N[X] \ S|, gdzie N[X] jest domkniętym sąsiedztwem zbioru X w grafie G. Zaprojektowaliśmy pseudotester o wielomianowej złożoności obliczeniowej dla decyzyjnego problemu bezpieczeństwa zbioru w grafie wykorzystując m.in. koncepcję symulowanego wyżarzania. Wykonaliśmy testy dla grafów, w których podgraf indukowany przez zbiór S jest drzewem lub grafem ograniczonego stopnia (przez 3 oraz 4). Z uwagi na coNP-zupełność problemu bezpieczeństwa zaproponowane przez nas podejście jest uogólnieniem koncepcji testowania własności znanej z literatury.
Źródło:
Studia i Materiały Informatyki Stosowanej; 2014, 14; 18-26
1689-6300
Pojawia się w:
Studia i Materiały Informatyki Stosowanej
Dostawca treści:
Biblioteka Nauki
Artykuł

Ta witryna wykorzystuje pliki cookies do przechowywania informacji na Twoim komputerze. Pliki cookies stosujemy w celu świadczenia usług na najwyższym poziomie, w tym w sposób dostosowany do indywidualnych potrzeb. Korzystanie z witryny bez zmiany ustawień dotyczących cookies oznacza, że będą one zamieszczane w Twoim komputerze. W każdym momencie możesz dokonać zmiany ustawień dotyczących cookies