Wyniki wyszukiwania - BazTech

1

Tight Bounds for Cut-Operations on Deterministic Finite Automata

Drewes F., van der Merwe B., Holzer M., Jakobi S.

Fundamenta Informaticae

|

2017

|

Vol. 155, nr 1/2

89--110

EN

We investigate the state complexity of the cut and iterated cut operation for deterministic finite automata (DFAs), answering an open question stated in [M. BERGLUND, et al.: Cuts in regular expressions. In Proc. DLT, LNCS 7907, 2011]. These operations can be seen as an alternative to ordinary concatenation and Kleene star modelling leftmost maximal string matching. We show that the cut operation has a matching upper and lower bound of n states, if m = 1, and (n-1).m+n states, otherwise, on DFAs accepting the cut of two individual languages that are accepted by n-andm-state DFAs, respectively. In the unary case we obtain max(2n-1;m+n-2) states as a tight bound--notice that for m ≤n the bound for unary DFAs only depends on the former automaton and not on the latter. For accepting the iterated cut of a language accepted by an n-state DFA we find a matching bound of 1+(n+1). F( 1; n+2;-n+2; n+1 j-1 ) states on DFAs, if n ≥ 4 and where F refers to the generalized hypergeometric function. This bound is in the order of magnitude Θ((n - 1)!). Finally, the bound drops to 2n - 1 for unary DFAs accepting the iterated cut of an n-state DFA, if n ≥ 3, and thus is similar to the bound for the cut operation on unary DFAs.

2

On the Computational Complexity of Partial Word Automata Problems

Holzer M., Jakobi S., Wendlandt M.

Fundamenta Informaticae

|

2016

|

Vol. 148, nr 3/4

267--289

EN

We consider the computational complexity of problems related to partial word automata. Roughly speaking, a partial word is a word in which some positions are unspecified and a partial word automaton is a finite automaton that accepts a partial word language-here the unspecified positions in the word are represented by a "hole" symbol ◊ . A partial word language L' can be transformed into an ordinary language L by using a ◊-substitution. In particular, we investigate the complexity of the compression or minimization problem for partial word automata, which is known to be NP-hard. We improve on the previously known complexity on this problem, by showing PSPACE-completeness. In fact, it turns out that almost all problems related to partial word automata, such as, e.g., equivalence and universality, are already PSPACE- complete. Moreover, we also study these problems under the further restriction that the involved automata accept only finite languages. In this case, the complexities of the studied problems drop from PSPACE-completeness down to coNP-hardness and containment in ∑P2 depending on the problem investigated.

3

Minimization and Characterizations for Biautomata

Holzer M., Jakobi S.

Fundamenta Informaticae

|

2015

|

Vol. 136, nr 1/2

113--137

EN

We show how to minimize biautomata with adaptations of classical minimization algorithms for ordinary deterministic finite automata and moreover by a Brzozowski-like minimization algorithm by applying reversal and power-set construction twice to the biautomaton under consideration. Biautomata were recently introduced in [O. KL´I MA, L. POL´A K: On biautomata. RAIRO— Theor. Inf. Appl., 46(4), 2012] as a generalization of ordinary finite automata, reading the input from both sides. The correctness of the Brzozowski-like minimization algorithm needs a little bit more argumentation than for ordinary finite automata since for a biautomaton its dual or reverse automaton, built by reversing all transitions, does not necessarily accept the reversal of the original language. To this end we first use the recently introduced notion of nondeterminism for biautomata [M. HOLZER, S. JAKOBI: Nondeterministic Biautomata and Their Descriptional Complexity. In: 15th DCFS, Number 8031 of LNCS, 2013] and take structural properties of the forward- and backward-transitions of the automaton into account. This results in a variety of biautomata models, the accepting power of which is characterized. As a byproduct we give a simple structural characterization of cyclic regular and commutative regular languages in terms of deterministic biautomata.

4

Computational Complexity of NURIKABE

Holzer M., Klein A., Kutrib M., Ruepp O.

Fundamenta Informaticae

|

2011

|

Vol. 110, nr 1-4

159-174

EN

We show that the popular pencil puzzle NURIKABE is intractable from the computational complexity point of view, that is, it is NP-complete, even when the involved numbers are 1 and 2 only. To this end, we show how to simulate Boolean gates by the puzzle under consideration. Moreover, we also study some NURIKABE variants, which remain NP-complete, too.

5

More on the Size of Higman-Haines Sets: Effective Constructions

Gruber H., Holzer M., Kutrib M.

Fundamenta Informaticae

|

2009

|

Vol. 91, nr 1

105-121

EN

A not so well-known result in formal language theory is that the Higman-Haines sets for any language are regular [11, Theorem 4.4]. It is easily seen that these sets cannot be effectively computed in general. The Higman-Haines sets are the languages of all scattered subwords of a given language as well as the sets of all words that contain some word of a given language as a scattered subword. Recently, the exact level of unsolvability of Higman-Haines sets was studied in [8]. Here we focus on language families whose Higman-Haines sets are effectively constructible. In particular, we study the size of descriptions of Higman-Haines sets for the lower classes of the Chomsky hierarchy, namely for the family of regular, linear context-free, and context-free languages. We prove upper and lower bounds on the size of descriptions of these sets for general and unary languages.

6

Cooperating Distributed Grammar Systems as Models of Distributed Problem Solving, Revisited

Bordihn H., Holzer M.

Fundamenta Informaticae

|

2007

|

Vol. 76, nr 3

255-270

EN

Based on a derivation mode f for cooperating distributed (CD) grammar systems, we introduce a new form of cooperation protocol, the so called "cut-f-mode" of derivation. Intuitively, in the cut-f-mode of derivation the sentential form is partitioned (cut) into several subwords, where some of these subwords are distributed to the components, which derive them according to the underlying f-mode of derivation, and finally the new sentential form is obtained by concatenating all the subwords-derived or not-in their original order. According to the original motivation from distributed artificial intelligence, the new functioning mode appears to be more realistic than the original model. We investigate the cut-mode versions of the basic derivation modes and some of their combined versions. It turns out that in most cases, the cut-f-mode is at most as powerful as the corresponding non-cut-mode, that is, the f-mode itself. In some cases the power is even reduced to that of context-free grammars.

7

Variable Complexity of Simple Programs

Holzer M., Kutrib M.

Fundamenta Informaticae

|

2006

|

Vol. 74, nr 4

511-528

EN

The number of registers or variables of a LOOP-, WHILE-, or GOTO-program, needed to compute a certain (partial) function from non-negative integers into non-negative integers, is a natural measure of complexity. We show that the hierarchy of LOOP-computable (WHILE-, and GOTO-computable, respectively) functions f:\mathbbNŽ \mathbbN (partial functions f:\mathbbN\hookrightarrow \mathbbN, respectively) which is induced by the number of registers collapses to level four (three, respectively). So, there exist universal WHILE- and GOTO-programs with a constant number of registers. In all three cases we give a characterization of the functions that can be computed by one register only. These characterizations are used to show that the first levels of the register hierarchies are strict, and to compare these levels. Surprisingly, for total functions it turns out that the bottom level of the LOOP-hierarchy is incomparable (with respect to set inclusion) to the bottom levels of the WHILE- and GOTO-hierarchies. Finally we briefly discuss the impact of the register operations on the presented results.

8

Representations of Recursively Enumerable Array Languages by Contextual Array Grammars

Fernau H., Freund R., Holzer M.

Fundamenta Informaticae

|

2005

|

Vol. 64, nr 1-4

159-170

EN

The main result proved in this paper shows that the natural embedding of any recursively enumerable one-dimensional array language in the two-dimensional space can be characterized by the projection of a two-dimensional array language generated by a contextual array grammar working in the t-mode and with norm one. Moreover, we show that any recursively enumerable one-dimensional array language can even be characterized by the projection of a two-dimensional array language generated by a contextual array grammar working in the t-mode where in the selectors of the contextual array productions only the ability to distinguish between blank and non-blank positions is necessary; in that case, the norm of the two-dimensional contextual array grammar working in the t-mode cannot be bounded.

9

Knowledge Acquisition under Incomplete Knowledge using Methods from Formal Concept Analysis: Part I

Holzer M.

Fundamenta Informaticae

|

2004

|

Vol. 63, nr 1

1--39

EN

Formal contexts with unknown entries can be represented by three-valued contexts K = (G,M, {x,o,?},I), where a question mark indicates that it is not known whether the object g ∈G has the attribute m ∈M. To describe logical formulas between columns of such incomplete contexts the Kripke-semantics are used for propositional formulas over the set M of attributes. Attribute implications are considered as special propositional formulas. If a context is too large to be fully represented, an interactive computer algorithm may help the user to get maximal information (with respect to his knowledge) about the valid attribute implications of the unknown context. This computer algorithm is called "attribute exploration''.

10

Knowledge Acquisition under Incomplete Knowledge using Methods from Formal Concept Analysis: Part II

Holzer M.

Fundamenta Informaticae

|

2004

|

Vol. 63, nr 1

41--63

EN

Attribute exploration is an interactive computer algorithm which helps the expert to get informations about the attribute implications of a formal context. In the part I of this paper (see [H04]) an algorithm for attribute exploration with incomplete knowledge was presented. In this part we prove the main results of the algorithm: At the end of the attribute exploration the expert gets maximal information with respect to his knowledge about the unknown universe: He gets a list of implications which are certainly valid, a list of implications which are possibly valid, a list of counterexamples against the implications which are certainly not valid and a list of fictitious counterexamples against the implications which he answered by `"unknown''. He only has to check the implications which he answered by `"unknown'' and if he can decide for each of these implications whether it is valid or not, he gets complete knowledge about the implications of the context.

11

On accepting pure Lindenmayer systems

Bordihn H., Fernau H., Holzer M.

Fundamenta Informaticae

|

1999

|

Vol. 38, Nr 4

365-375

EN

We consider pure Lindenmayer systems, more precisely, 0L and T0L systems as language accepting devices and compare them to their generating counterparts. Accepting Lindenmayer systems can be seen as systems of inverse finite substitutions which are iteratively applied over a free monoid. Hereby, we investigate the deterministic case in detail, comparing several different concepts of determinism in such systems. Whereas in the usual generating case these concepts trivially are equally powerful, the structure of families of accepted languages is much richer. In passing, the case of unary Lindenmayer systems is investigated.