Wyniki wyszukiwania - BazTech

1

Complexity of cover - preserving embeddings of bipartite orders into boolean lattices

Herman G.

Reports on Mathematical Logic

|

2014

|

Vol. 49

99--117

EN

We study the problem of deciding, whether a given partial order is embeddable into two consecutive layers of a Boolean lattice. Employing an equivalent condition for such em- beddability similar to the one given by J. Mittas and K. Reuter [5], we prove that the decision problem is NP-complete by showing a polynomial-time reduction from the not-all-equal variant of the Satisfiability problem.

2

Unambiguous Functions in Logarithmic Space

Herman G., Soltys M.

Fundamenta Informaticae

|

2012

|

Vol. 114, nr 2

129-147

EN

We investigate different variants of unambiguity in the context of computingmulti-valued functions. We propose a modification to the standard computation models of Turing machines and configuration graphs, which allows for unambiguity-preserving composition. We define a notion of reductions (based on function composition), which allows nondeterminism but controls its level of ambiguity. In light of this framework we establish reductions between different variants of path counting problems. We obtain improvements of results related to inductive counting.

3

A Propositional Proof System with Quantification Over Permutations

Herman G., Paterson T., Soltys M.

Fundamenta Informaticae

|

2007

|

Vol. 79, nr 1-2

71-83

EN

We introduce a new propositional proof system, which we call H, that allows quantification over permutations. In H we may write ($ab)a and ("ab)a, which is semantically equivalent to a(a,b)Úa(b,a) and a(a,b)U`a(b,a), respectively. We show that H with cuts restricted to S1 formulas (we denote this system H1) simulates efficiently the Hajós calculus (HC) for constructing graphs which are non-3-colorable. This shows that short proofs over formulas that assert the existence of permutations can capture polynomial time reasoning (as by [9], HC is equivalent in strength to EF, which in turn captures polytime reasoning). We also show that EF simulates efficiently H1*, which is H1 with proofs restricted to being tree-like. In short, we show that [formula]

4

Wody mineralne w rejonie Buska-Zdroju i Solca-Zdroju

Herman G., Gągol J.

Przegląd Geologiczny

|

2000

|

Vol. 48, nr 7

616-618

PL

W rejonie Buska Zdroju i Solca Zdroju występują wody mineralne (o mineralizacji powyżej lg/dm3). Niektóre z nich (wody typu Cl-Na+HiS, Cl-Na+J+Br, Cl-SO4-Na+H2S, Cl-Na+J+Br+HiS) zostały uznane za lecznicze. Uproszczoną charakterystykę hydrochemiczną omawianych wód mineralnych przedstawiono na szkicu. W badanym rejonie można wyróżnić 4 grupy wód mineralnych: wody pólslodkie (1-3 g/dm ) typu SO4-Ca+H2S, które występują w skałach trzeciorzędowych i lokalnie kredowych, wody słonawe (3-10 g/dm3) i słone (10-35 g/dm3) typu Cl-Na+J+Br+H2S lub Cl-SO4-Na+J+Br+H2S w skalach kredowych i stropowej części utworów jurajskich, solanki typu Cl-Na+J+Br w skałach jurajskich. Wyniki badań izotopowych wykonane w ostatnich latach wskazują, że płytko występujące wody mineralne są wodami paleoinfiltracyjny'mi (plejstocen). Wody z głębszych poziomów mogą być również wodami paleoinfiltracyjnymi (prawdopodobnie z końca trzeciorzędu).

EN

Mineral waters (mineralization exceeds lg/dm3) are occurring in the Busko-Zdrój and Solec-Zdrój region. Some of them (Cl-Na+H2S, Cl-Na+J+Br, Cl-SOr-Na+H2S, Cl-Na+J+Br+H2S) have been recognized as medicinal waters. The simplified hydrochemical characteristics of mineral waters (from springs, boreholes, shafts) has been presented on the sketch. In the area of interest jour groupes of mineral waters have been recognized: (semi-fresh waters (1-3 g/dm3) primarily type SOj-Ca+HjS. These waters are featured by a shallow circulation within Tertiary rocks (subgypsum horizon) and locally Cretaceous deposits; (brackish (3-10 g/dm3) and saline (10-35 g/dm3) waters type Cl-Na+J+Br+H2S or Cl~SO4-Na+J+Br+H2S. These waters occur in Cretaceous rocks and a top Jurassic series; (brine type Cl-Na+J+Br. They are seized from Jurassic rocks. The origin of mineral waters in the Busko and Solec region have been investigated by many researchers. The latest results of isotopic determinations and hydrochemical analyses indicated that shallow mineral waters are paleoinfiltration waters (Pleistocene). Deeper waters in the Busko and Solec area may also be infiltration water (probably from the late Tertiary).