Wyniki wyszukiwania - BazTech

1

The Inverse of Ackermann Function is Computable in Linear Time

Sureson Claude

Fundamenta Informaticae

|

2021

|

Vol. 182, nr 4

345--361

EN

We propose a detailed proof of the fact that the inverse of Ackermann function is computable in linear time.

2

Self-Verifying Pushdown and Queue Automata

Fernau Henning, Kutrib Martin, Wendlandt Matthias

Fundamenta Informaticae

|

2021

|

Vol. 180, nr 1-2

1--28

EN

We study the computational and descriptional complexity of self-verifying pushdown automata (SVPDA) and self-verifying realtime queue automata (SVRQA). A self-verifying automaton is a nondeterministic device whose nondeterminism is symmetric in the following sense. Each computation path can give one of the answers yes, no, or do not know. For every input word, at least one computation path must give either the answer yes or no, and the answers given must not be contradictory. We show that SVPDA and SVRQA are automata characterizations of so-called complementation kernels, that is, context-free or realtime nondeterministic queue automaton languages whose complement is also context free or accepted by a realtime nondeterministic queue automaton. So, the families of languages accepted by SVPDA and SVRQA are strictly between the families of deterministic and nondeterministic languages. Closure properties and various decidability problems are considered. For example, it is shown that it is not semidecidable whether a given SVPDA or SVRQA can be made self-verifying. Moreover, we study descriptional complexity aspects of these machines. It turns out that the size trade-offs between nondeterministic and self-verifying as well as between self-verifying and deterministic automata are non-recursive. That is, one can choose an arbitrarily large recursive function f, but the gain in economy of description eventually exceeds f when changing from the former system to the latter.

3

Cut Points in PEG

Redziejowski R. R.

Fundamenta Informaticae

|

2016

|

Vol. 143, nr 1/2

141--149

EN

Parsing Expression Grammar (PEG) encodes a recursive-descent parser with limited backtracking. It has been recently noticed that in the situation when the parser is to explore several alternatives one after another, no further alternatives need to be explored after the parser reached certain ”cut point”. This fact can be used to save both processing time and storage. The subject of the paper is identification of cut points, which can also help in producing better diagnostics.

4

The Supports of Weighted Unranked Tree Automata

Droste M., Heusel D.

Fundamenta Informaticae

|

2015

|

Vol. 136, nr 1/2

37--58

EN

We investigate the supports of weighted unranked tree automata. Our main result states that the support of a weighted unranked tree automaton over a zero-sum free, commutative strong bimonoid is recognizable. For this, we use methods of Kirsten (DLT 2009), in particular, his construction of finite automata recognizing the supports of weighted automata on strings over zero-sum free, commutative semirings. We also get an effective construction of a finite tree automaton recognizing the support of a given weighted unranked tree automaton for zero-sum free, commutative strong bimonoids where Kirsten’s zero generation problem is decidable. In addition, we give a translation of nested weighted automata into weighted unranked tree automata for arbitrary commutative strong bimonoids. As a consequence,we derive analogous results for the supports of nested weighted automata. Finally, we give similar results for the supports of weighted pushdown automata.

5

Recursive Query Processing in SBQL

Pieciukiewicz T., Subieta K.

Prace Instytutu Podstaw Informatyki Polskiej Akademii Nauk

|

2004

|

Nr 979

1-56

EN

Recursive queries arę reąuired for many tasks of database applications. Among them we can mention Bill-Of-Material (BOM), various kinds of networks (transportation, telecommunication, etc.), processing semi-structured data (XML, RDF), and so on. The support for recursive queries in current query languages is limited and lacks of theoretical foundations. In particular, this concerns corresponding extensions of SQL in Oracle and DB2 systems. In this report we present recursive query processing capabilities for the object-oriented Stack-Based Query Language (SBQL) and compare them with similar capabilities in yariants of SQL. SBQL offers very powerful and flexible recursive querying capabilities due to the fact that recursive processing operators arę fully orthogonal to other features of this language. This report specifies corresponding SBQL constructs, such as transitive closures and fixed point equations. We compare them to other query languages, in particular to Datalog. We also present briefly optimization possibilities for recursive queries.

PL

Rekurencyjne zapytania są wymagane dla wielu zadań występujących w rzeczywistych aplikacjach baz danych. Wśród nich możemy wymienić rachunek materiałów (BOM), różne typy sieci (transportowa, telekomunikacyjna, itp.), przetwarzanie danych półstrukturalnych (XML, RDF) itd. Wspomaganie dla rekurencyjnych zapytań w obecnych językach zapytań jest ograniczone i pozbawione podstaw teoretycznych. W szczególności, dotyczy to odpowiednich rozszerzeń SQL w systemach Oracle i DB2. W raporcie przedstawiamy możliwości w zakresie rekurencyjnych zapytań w języku zorientowanym obiektowo Stack-Based Query Language (SBQL) i porównujemy je do podobnych możliwości w wariantach SQL. SBQL oferuje bardzo mocne i elastyczne możliwości w zakresie rekurencyjnych zapytań dzięki temu, że operatory służące do przetwarzania rekurencyjnego są całkowicie ortogonalne w stosunku do innych cech języka. Raport specyfikuje odpowiednie konstrukcje SBQL, takie jak tranzytywne domknięcia oraz równania stałopunktowe. Porównujemy je do innych języków zapytań, w szczególności do Datalogu. Na zakończenie prezentujemy krótko możliwości optymalizacji zapytań rekurencyjnych.

6

Funkcje normalne jako nowy model definiowania funkcji obliczalnych

Dubiel L.

Computer Science

|

2004

|

Vol. 6

7-28

PL

Artykuł prezentuje nową metodę definiowania funkcji obliczalnych. Metoda jest formalizacją tradycyjnego zapisu funkcji i pozwala na określanie funkcji w sposób intuicyjny. W systemie funkcji rekursywnych Hilberta nie wszystkie odwzorowania, które mają łatwe algorytmy obliczania, mogą być równie łatwo zdefiniowane formalnie, czego przykładem jest funkcja Ackermanna. Funkcje normalne są pozbawione tej wady.

EN

Report sets new method of defining computable functions. This is formalization of traditional function descriptions, so it allows to define functions in very intuitive way. Discovery of Ackermann function proved that not all functions that can be easily computed can be so easily described with Hilbert's system of recursive functions. Normal functions lack this disadvantage.