doc. RNDr. Daniel Průša, Ph.D.

In 1978 Sakoda and Sipser raised the question of the cost, in terms of size of representations, of the transformation of two-way and one-way nondeterministic automata into equivalent two-way deterministic automata. Despite all the attempts, the question has been answered only for particular cases, while it remains open in general, the best upper bound currently known being exponential. We present a new approach in which unrestricted nondeterministic automata are simulated by deterministic models extending two-way deterministic automata, paying only a polynomial increase of size. Indeed, we study the costs of the conversions of nondeterministic automata into some variants of one-tape deterministic Turing machines working in linear time; namely Hennie machines, weight-reducing Turing machines, and weight-reducing Hennie machines. All these variants are known to share the same computational power: they characterize the class of regular languages.

We introduce complete LR(0)-grammars with sentinels (called complete LR(¢,$)-grammars) to prepare tools for the study of pumping restarting automata controlled by this type of grammars. A complete LR(¢,$)-grammar generates both a language and the complement of the language with sentinels. Based on a complete LR(¢,$)- grammar, we can construct a deterministic pumping restarting automaton performing pumping analysis by reduction on each word over its input alphabet. A pumping reduction analysis is a method where an input word is stepwise simplified by removing at most two continuous parts of the current word in a way that preserves (in)correctness of the word. Each such simplification corresponds to removing parts of the current word that could be “pumped” in the sense of a pumping lemma for context-free languages. The computation of a pumping restarting automaton ends when the original word is shortened under a given length, and then it is decided about the correctness or incorrectness of the original input word. This means that pumping restarting automata can analyze both correct and incorrect inputs with respect to a deterministic context-free language (DCFL). That gives an excellent formal basis for the error localization and the error recovery of DCFL.

We present two types of pumping patterns that allow a total separation inside the class of LR(0)-grammars. Using the same type of pumping patterns, we obtain a total separation inside of linear LR(0)-grammars. This type of study has a long-term motivation from computational linguistics and the area of syntactic error localization. A recent motivation also comes from the field of formal models of neural networks.

Given a two-dimensional array of symbols and a picture language over a finite alphabet, we investigate how to find rectangular subarrays that belong to the picture language. Two-dimensional pattern matching problems can be formulated by interpreting subarrays as matches and picture languages as patterns. We formulate four particular problems – finding maximum, minimum, any or all match(es) – and describe algorithms solving the problems for basic classes of picture languages, which include local picture languages and picture languages accepted by various types of deterministic two-dimensional finite automata such as four-way, three-way and two-way automata, on-line tessellation automata, and returning finite automata. We also prove that the pattern matching problems cannot be solved for the class of local picture languages in time linear in the input area unless the well known problem of triangle finding in a graph is solvable in quadratic time. This shows a fundamental difference between the complexity of one-dimensional and two-dimensional pattern matching.

We study the problem of finding a given 2x2 matrix as a submatrix of a given Boolean matrix. Three variants are considered: search for a matching submatrix of any area, of minimum area, or of maximum area. The problem relates to 2D pattern matching, and to fields such as data mining, where the search for submatrices plays an important role. Besides these connections, the problem itself is very natural and its investigation helps to demonstrate differences between search tasks in one-dimensional and multidimensional topologies.

We study properties of a two-dimensional grammar introduced recently for use in document analysis and recognition. The grammar is obtained from the two-dimensional context-free grammar by restricting the form of productions. Variants (ranks) of the grammar with regard to productions complexity are defined. It is suggested that the lowest-rank variant can be considered as a natural generalization of the regular matrix grammar, which in addition has good properties with respect to the membership and emptiness problems. However, it is also showed that the higher-rank variants do not loosen complexity of the context-free grammar too much. There is a conditional lower bound preventing to propose a linear-time parsing algorithm. Moreover, the grammar is able to simulate the 2-counter Minsky machine, which results in non-recursive trade-offs and undecidability of the emptiness problem.

It is well-known that for general convex optimization problems, block-coordinate descent can get stuck in poor local optima. Despite that, versions of this method known as convergent message passing are very successful to approximately solve the dual LP relaxation of the MAP inference problem in graphical models. In attempt to identify the reason why these methods often achieve good local minima, we argue that if in block-coordinate descent the set of minimizers over a variable block has multiple elements, one should choose an element from the relative interior of this set. We show that this rule is not worse than any other rule for choosing block-minimizers. Based on this observation, we develop a theoretical framework for block-coordinate descent applied to general convex problems. We illustrate this theory on convergent message-passing methods.

We study the task of an automatic evaluation of mathematical word problems, which belongs to the category of natural language processing and has become popular in recent years. Since all the so far published methods were developed for inputs in English, our goal is to review them and propose solutions able to cope with inputs in the Czech language. We face the question whether we can achieve a competitive accuracy for a natural language with flexible word order, and with the assumption that only a relatively small dataset of training and testing data is available. We propose and evaluate two methods. One relies on a rule-based processing of dependency trees computed by UDPipe. The other method builds on machine learning. It transforms word problems into numeric vectors and trains SVM to classify them. We also show that it improves in a combination with a search for predefined sequences of words and word classes, achieving 75% accuracy on our dataset of 500 Czech word problems.

This paper introduces spanning tree automata (ST automata) usable for defining sets of labeled, connected graphs. The automata are simply obtained by extending ordinary top-down finite tree automata for labeled, ordered trees. It is shown that ST automata can define any finite set of labeled, connected graphs, and also some subclasses of infinite sets of graphs that can represent the structure of chemical molecules. Although the membership problem for ST automata is NP-complete, an efficient software was developed which supports a practical use of ST automata in chemoinformatics as well as in other fields.

In classification with a reject option, the classifier is allowed in uncertain cases to abstain from prediction. The classical cost based model of an optimal classifier with a reject option requires the cost of rejection to be defined explicitly. An alternative bounded-improvement model, avoiding the notion of the reject cost, seeks for a classifier with a guaranteed selective risk and maximal cover. We prove that both models share the same class of optimal strategies, and we provide an explicit relation between the reject cost and the target risk being the parameters of the two models. An optimal rejection strategy for both models is based on thresholding the conditional risk defined by posterior probabilities which are usually unavailable. We propose a discriminative algorithm learning an uncertainty function which preserves ordering of the input space induced by the conditional risk, and hence can be used to construct optimal rejection strategies.

We show that the general linear programming (LP) problem reduces in nearly linear time to the LP relaxations of many classical NP-hard combinatorial problems, assuming sparse encoding of instances. We distinguish two types of such reductions. In the first type (shown for set cover/packing, facility location, maximum satisfiability, maximum independent set, and multiway cut), the input linear program is feasible and bounded iff the optimum value of the LP relaxation attains a threshold, and then optimal solutions to the input linear program correspond to optimal solutions to the LP relaxation. In the second type (shown for exact set cover, three-dimensional matching, and constraint satisfaction), feasible solutions to the input linear program correspond to feasible solutions to the LP relaxations. Thus, the reduction preserves objective values of all (not only optimal) solutions. In polyhedral terms, every polytope in standard form is a scaled coordinate projection of the optimal or feasible set of the LP relaxation. Besides nearly linear-time reductions, we show that the considered LP relaxations are P-complete under log-space reductions, and therefore also hard to parallelize. These results pose a limitation on designing algorithms to compute exact or even approximate solutions to the LP relaxations, as any lower bound on the complexity of solving the general LP problem is inherited by the LP relaxations.

Given a two-dimensional array of symbols and a picture language over a finite alphabet, we study the problem of finding rectangular subarrays of the array that belong to the picture language. We formulate four particular problems – finding maximum, minimum, any or all match(es) – and describe algorithms solving them for basic classes of picture languages, including local picture languages and picture languages accepted by deterministic on-line tessellation automata or deterministic four-way finite automata. We also prove that the matching problems cannot be solved for the class of local picture languages in linear time unless the problem of triangle finding is solvable in quadratic time. This shows there is a fundamental difference in the pattern matching complexity regarding the one-dimensional and two-dimensional setting.

We study the lengths of synchronizing words produced by the classical greedy compression algorithm. We associate a sequence of graphs with every synchronizing automaton and rely on evolution of the independence number to bound the lengths of produced words. By leveraging graph theoretical results we show that in many cases automata with good extension properties have good compression properties as well. More precisely, we show that the compression algorithm will produce a synchronizing word of length O(n^2log(n)) on cyclic, regular and strongly-transitive automata with n states, which is not far from the best possible bound of (n−1)^2. Furthermore, we provide a relatively simple proof that every n-state automaton has a synchronizing word of length at most (1/4)n^3+O(n^2) .

We study the task of document layout analysis based on two-dimensional context-free grammars. We first identify a subclass of the grammars sufficient for a document structure description where productions follow a mechanism inducing regular languages in the case of one-dimensional productions. We then show that properties of such grammars can be conveniently utilized to implement a very fast top-down parser. Experimental results are reported for PDF documents, which are chosen as a test domain since we are motivated by a development of digital document access methods for people with disabilities in which a retrieval of structural information plays an important role.

It is well-known that one-tape Turing machines working in linear time are no more powerful than finite automata, namely they recognize exactly the class of regular languages. We study the costs, in terms of description sizes, of the conversion of nondeterministic finite automata into equivalent linear-time one-tape deterministic machines. We prove a polynomial blowup from two-way nondeterministic finite automata into equivalent weight-reducing one-tape deterministic machines that work in linear time. The blowup remains polynomial if the tape in the resulting machines is restricted to the portion which initially contains the input. However, in this case the machines resulting from our construction are not weight reducing, unless the input alphabet is unary.

We study the two-dimensional pattern matching implemented using the deterministic two-dimensional on-line tessellation automaton. This restricted two-dimensional cellular automaton is able to simulate the Baker-Bird algorithm, which was proposed as the first algorithm for the two-dimensional pattern matching. We explore capabilities of this automaton to carry out the matching task against an arbitrary set of equal-sized patterns. To measure amount of resources needed to accomplish it, we introduce the pattern complexity of a picture language. We show that this complexity ranges from a constant to exponential one. All of these are illustrated by giving examples of two-dimensional on-line tessellation automata matching sets of patterns, describing general techniques of how to construct them and proving lower bounds on the pattern complexity of some picture languages as well as operations over them.

In our recent work, we showed that solving the LP relaxation of the pairwise min-sum labeling problem (also known as MAP inference in graphical models or discrete energy minimization) is not much easier than solving any linear program. Precisely, the general linear program reduces in linear time (assuming the Turing model of computation) to the LP relaxation of the min-sum labeling problem. The reduction is possible, though in quadratic time, even to the min-sum labeling problem with planar structure. Here we prove similar results for the pairwise min-sum labeling problem with attractive Potts interactions (also known as the uniform metric labeling problem).

We show that solving linear programming (LP) relaxations of many classical NP-hard combinatorial optimization problems is as hard as solving the general LP problem. Precisely, the general LP can be reduced in linear time to the LP relaxation of each of these problems. This result poses a fundamental limitation for designing efficient algorithms to solve the LP relaxations, because finding such an algorithm might improve the complexity of best known algorithms for the general LP. Besides linear-time reductions, we show that the LP relaxations of the considered problems are P-complete under log-space reduction, therefore also hard to parallelize.

We experiment with off-line recognition of handwritten flowcharts based on strokes reconstruction and our state-of-the-art on-line diagram recognizer. A simple baseline algorithm for strokes reconstruction is presented and necessary modifications of the original recognizer are identified. We achieve very promising results on a flowcharts database created as an extension of our previously published on-line database.

We propose a framework for pattern matching in twodimensional arrays of symbols where the patterns are described by an extended version of the regular matrix grammar and the size of desired matches is prescribed. We then demonstrate how to reformulate the 2D pattern matching as the one-dimensional pattern matching (string pattern matching), and study the efficiency of the string pattern matching algorithm based on pattern complexity with respect to two finite automaton models: (1) the classical finite automaton and (2) the finite automaton equipped with two scanning heads placed in a fixed distance. We also identify several subclasses of the considered templates for which the framework yields a more efficient matching than the naive algorithm.

A two-dimensional Kolam grammar as defined by Siromoney et al. in 1972 and independently by Matz in 1997 and Schlesinger in 1989 allows context-free productions of the form A→a, A→BC, A→B/C, and S→λ which concatenate sub-pictures produced by B and C horizontally respectively vertically if their height respectively width fits. We demonstrate that this grammar is quite powerful by proving undecidability of the emptiness problem. We further analyze consequences of this finding and give additional characteristics related to size of generated pictures.

We study the two-dimensional pattern matching implemented using the two-dimensional on-line tessellation automaton, which is a restricted type of the cellular automaton able to simulate the Baker-Bird algorithm, proposed as the first algorithm for the two-dimensional pattern matching. We further explore capabilities of this automaton to carry out the matching task against an arbitrary set of equally sized patterns. To measure amount of resources needed to accomplish it, we introduce the pattern complexity of a picture language. We show that this complexity spreads in a wide range. It is demonstrated by giving examples, deriving general techniques and proving some lower bounds.

We study succinctness of descriptional systems for picture languages. Basic models of two-dimensional finite automata and generalizations of context-free grammars are considered. They include the four-way automaton of Blum and Hewitt, the two-dimensional online tessellation automaton of Inoue and Nakamura and the context-free Kolam grammar of Siromoney et al. We show that non-recursive trade-offs between the systems are very common. Basically, each separation result proving that one system describes a picture language which cannot be described by another system can usually be turned into a non-recursive trade-off result between the systems. These findings are strongly based on the ability of the systems to simulate Turing machines.

We introduce a new, online, stroke-based recognition system for hand-drawn diagrams which belong to a group of documents with an explicit structure obvious to humans but only loosely defined from the machine point of view. We propose a model for recognition by selection of symbol candidates, based on evaluation of relations between candidates using a set of predicates. It is suitable for simpler structures where the relations are explicitly given by symbols, arrows in the case of diagrams. Knowledge of a specific diagram domain is used—the two domains are flowcharts and finite automata. Although the individual pipeline steps are tailored for these, the system can readily be adapted for other domains. Our entire diagram recognition pipeline is outlined. Its core parts are text/non-text separation, symbol segmentation, their classification and structural analysis. Individual parts have been published by the authors previously and so are described briefly and referenced. Thorough evaluation on benchmark databases shows the accuracy of the system reaches the state of the art and is ready for practical use. The paper brings several contributions: (a) the entire system and its state-of-the-art performance; (b) the methodology exploring document structure when it is loosely defined; (c) the thorough experimental evaluation; (d) the new annotated database for online sketched flowcharts and finite automata diagrams.

With the aid of homogeneous morphisms, we turn the deterministic two-dimensional twoway ordered restarting automaton and its extended variant into devices that compute transductions of pictures, and we study the resulting classes of transductions in detail.

We study how dimensionality and form of context-free productions affect the power of multi-dimensional context-free grammars over unary alphabets. Attention is paid to the emptiness decision problem. It is an open question whether or not it is decidable for two-dimensional Kolam type context-free grammars of Siromoney. We show that the undecidability can be proved in the three-dimensional setting. For the two-dimensional variant, we present several results revealing that the process of generating is still much more complex than that one of the classical one-dimensional context-free grammar.

This paper deals with recognition of arrows in online sketched diagrams. Arrows have varying appearance and thus it is a difficult task to recognize them directly. It is beneficial to detect arrows after other symbols (easier to detect) are already found. We proposed [4] an arrow detector which searches for arrows as arbitrarily shaped connectors between already found symbols. The detection is done two steps: a) a search for a shaft of the arrow, b) a search for its head. The first step is relatively easy. However, it might be quite difficult to find the head reliably. This paper brings two contributions. The first contribution is a design of an arrow recognizer where the head is detected using relative strokes positioning. We embedded this recognizer into the diagram recognition pipeline proposed earlier [4] and increased the overall accuracy. The second contribution is an introduction of a new approach to evaluate the relative position of two given strokes with neural networks (LSTM). This approach is an alternative to the fuzzy relative positioning proposed by Bouteruche et al. [2]. We made a comparison between the two methods through experiments performed on two datasets for two different tasks. First, we used a benchmark database of hand-drawn finite automata to evaluate detection of arrows. Second, we used a database presented in the paper by Bouteruche et al. containing pairs of reference and argument strokes, where argument strokes are classified into 18 classes. Our method gave significantly better results for the first task and comparable results for the second task.

We show how the simplex algorithm can be tailored to the linear programming relaxation of pairwise energy minimization with binary variables. A special structure formed by basic and nonbasic variables in each stage of the algorithm is identified and utilized to perform the whole iterative process combinatorially over the input energy minimization graph rather than algebraically over the simplex tableau. This leads to a new efficient solver. We demonstrate that for some computer vision instances it performs even better than methods reducing binary energy minimization to finding maximum flow in a network.

An important subclass of the min-sum labeling problem (also known as discrete energy minimization or valued constraint satisfaction) is the pairwise min-sum problem with arbitrary unary costs and attractive Potts pairwise costs (also known as the uniform metric labeling problem). In analogy with our recent result, we show that solving the LP relaxation of the Potts min-sum problem is not significantly easier than that of the general min-sum problem and thus, in turn, the general linear program. This suggests that trying to find an efficient algorithm to solve the LP relaxation of the Potts min-sum problem has a fundamental limitation. Our constructions apply also to integral solutions, yielding novel reductions of the (non-relaxed) general min-sum problem to the Potts min-sum problem.

With the aid of homogeneous morphisms,we extend the deterministic two-dimensional two-way ordered restarting automaton into a device that computes transductions of pictures, and we study the resulting class of transductions in detail.

We show that solving the LP relaxation of the min-sum labeling problem (also known as MAP inference problem in graphical models, discrete energy minimization, or valued constraint satisfaction) is not easier than solving any linear program. Precisely, every polytope is linear-time representable by a local marginal polytope and every LP can be reduced in linear time to a linear optimization (allowing infinite costs) over a local marginal polytope. The reduction can be done (though with a higher time complexity) even if the local marginal polytope is restricted to have a planar structure.

Symbol segmentation is a critical part of handwriting recognition. Any mistake done in this step is propagating further through the recognition pipeline. It forces researchers to consider methods generating multiple hypotheses for symbol segmentation-over-segmentation. Simple approaches which takes all reasonable combinations of strokes are applied very often, because they allow to achieve high recall rates very easily. However, they generate too much hypotheses. It makes a recognizer considerably slow. This paper presents our experimentation with an alternative method based on a single linkage agglomerative clustering of strokes with trainable distance metric. We embed the method into the state-of-the-art recognizer for on-line sketched diagrams. We show that it results in a decrease in the number of generated hypotheses while still reaching high recall rates. A problem emerges, since the number of bad hypotheses is still significantly higher than the number of symbols and it leads to unbalanced training datasets. To deal with it, we propose to train symbol classifiers with synthesized artificial samples. We show that the combination of these two improvements make the recognizer significantly faster and very precise.

This paper introduces a novel method for on-line recognition of handwritten mathematical formulas. The method is based on the combination of a structural analy sis with a statistical model specifying relations of individual symbols. A description o f all recognition phases is given, focusing mostly on the structural analysis stage. The recognition process following a bottom-up manner is driven by a spatial grammar, which expresses mathematical formulas unambiguously. As the grammar describes the relative pos itions only roughly, a statistical model learned from a database of annotated formulas i s employed to refine the description. Several experimental results are also reported.

The work addresses the problem of clothing perception and manipulation by a two armed industrial robot aiming at a real-time automated folding of a piece of garment spread out on a flat surface. A complete solution combining vision sensing, garment segmentation and understanding, planning of the manipulation and its real execution on a robot is proposed. A new polygonal model of a garment is introduced. Fitting the model into a segmented garment contour is used to detect garment landmark points. It is shown how folded variants of the unfolded model can be derived automatically. Universality and usefulness of the model is demonstrated by its favorable performance within the whole folding procedure which is applicable to a variety of garments categories (towel, pants, shirt, etc.) and evaluated experimentally using the two armed robot. The principal novelty with respect to the state of the art is in the new garment polygonal model and its manipulation planning algorithm which leads to the speed up by two orders of magnitude.

We study succinctness of descriptional systems for picture languages. Basic models of two-dimensional finite automata and generalizations of context-free grammars are considered. It is shown t hat non-recursive trade-offs between the systems are very common. The results are based on the ability of th e systems to simulate Turing machines.

We address the problem of recognizing a configuration of a piece of garment fairly spread out on a flat surface. We suppose that the background surface is invariant and that its color is sufficiently dissimilar from the color of a piece of garment. This assumption enables quite reliable segmentation followed by extraction of the garment contour. The contour is approximated by a polygon which is then fitted to a polygonal garment model. The model is specific for each category of garment (e.g. towel, pants, shirt) and its parameters are learned from training data. The fitting procedure is based on minimization of the energy function expressing dissimilarities between observed and expected data. The fitted model provides reliable estimation of garment landmark points which can be utilized for an automated folding using a pair of robotic arms. The proposed method was experimentally verified on a dataset of images. It was also deployed to a robot and tested in a real-time automated folding.

We present our recent model of a diagram recognition engine. It extends our previous work which approaches the structural recognition as an optimization problem of choosing the best subset of symbol candidates. The main improvement is the integration of our own text separator into the pipeline to deal with text blocks occurring in diagrams. Second improvement is splitting the symbol candidates detection into two stages: uniform symbols detection and arrows detection. Text recognition is left for postprocessing when the diagram structure is already known. Training and testing of the engine was done on a freely available benchmark database of flowcharts. We correctly segmented and recognized 93.0% of the symbols having 55.1% of the diagrams recognized without any error. Considering correct stroke labeling, we achieved the precision of 95.7%. This result is superior to the state-of-the-art method with the precision of 92.4 %. Additionally, we demonstrate the generality of the proposed method by adapting the system to finite automata domain and evaluating it on own database of such diagrams.

Minimization of a partially separable function of many discrete variables is ubiquitous in machine learning and computer vision, in tasks like maximum a posteriori (MAP) inference in graphical models, or structured prediction. Among successful approaches to this problem is linear programming (LP) relaxation. We discuss this LP relaxation from two aspects. First, we review recent results which characterize languages (classes of functions permitted to form the objective function) for which the problem is solved by the relaxation exactly. Second, we show that solving the LP relaxation is not easier than solving any linear program, which makes a discovery of an efficient algorithm for the LP relaxation unlikely.

We present a new model of a two-dimensional computing device called Sgraffito automaton. In general, the model is quite simple, which allows a clear design of computations. When restricted to one-dimensional inputs, that is, strings, the Sgraffito automaton does not exceed the power of finite-state automata. On the other hand, for two-dimensional inputs, it yields a family of picture languages with good closure properties that strictly includes the class REC of recognizable picture languages. The deterministic Sgraffito automata define a class of picture languages that includes the class of deterministic recognizable picture languages DREC, the class of picture languages that are accepted by four-way alternating automata, those that are accepted by deterministic one-marker automata, and the sudoku-deterministically recognizable picture languages, but the membership problem for the accepted languages is still decidable in polynomial time. In addition, the deterministic Sgraffito automata accept some unary picture languages that are outside of the class REC.

We present a constructive variant of the Hennie machine. It is demonstrated how it can facilitate the design of finite-state machines. We focus on the d eterministic version of the model and study its descriptional complexity. The model's suc cinctness is compared with common devices that include the nondeterministic finite automa ton, two-way finite automaton and pebble automaton.

We compare two types of automata for accepting picture languages to each other: the two-dimensional one-marker automaton and the sgraffito automaton. On the one hand, it is shown that deterministic sgraffito automata are strictly more powerful than deterministic two-dimensional one-marker automata. On the other hand, nondeterministic two-dimensional one-marker automata accept some picture languages that cannot be accepted by sgraffito automata. However, if nondeterministic two-dimensional one-marker automata were to accept all picture languages that are accepted by (deterministic) sgraffito automata, then the complexity classes NL (nondeterministic logarithmic space) and P (deterministic polynomial time) would coincide. Accordingly, it is likely that the classes of picture languages accepted by these two types of nondeterministic automata are incomparable under inclusion.

This work deals with the on-line recognition of hand-drawn graphical sketches with structure. We present a novel approach, in which the search for a suitable interpretation of the input is formulated as a combinatorial optimization task -- the max-sum problem. The recognition pipeline consists of two main stages. First, groups of strokes possibly representing symbols of a sketch (symbol candidates) are segmented and relations between them are detected. Second, a combination of symbol candidates best fitting the input is chosen by solving the optimization problem. We focused on flowchart recognition. Training and testing of our method was done on a freely available benchmark database. We correctly segmented and recognized 82.7 prec. of the symbols having 31.5 prec. of the diagrams recognized without any error. It indicates that our approach has promising potential and can compete with the state-of-the-art methods.

The deterministic sgraffito automaton is a two-dimensional computing device that allows a clear and simple design of important computations. The family of picture languages it accepts has many nice closure properties, but when restricted to one-row inputs (that is, strings), this family collapses to the class of regular languages. Here we compare the deterministic sgraffito automaton to some other two-dimensional models: the two-dimensional deterministic forgetting automaton, the four-way alternating automaton and the sudoku-deterministically recognizable picture languages. In addition, we prove that deterministic sgraffito automata accept some unary picture languages that are outside the class REC of recognizable picture languages.

We present a new model of a two-dimensional computing device called restarting tiling automaton. The automaton defines a set of tile-rewriting, weight-reducing rules and a scanning strategy by which a tile to rewrite is being searched. We investigate properties of the induced families of picture languages. Special attention is paid to picture languages that can be accepted independently of the scanning strategy. We show that this family strictly includes REC and exhibits similar closure properties. Moreover, we prove that its intersection with the set of one-row languages coincides with the regular languages.

This work deals with recognition of hand-drawn graphical symbols in diagrams. We present two contributions. First, we designed a new composite descriptor expressing overall appearance of symbols. We achieved rather favorable accuracy in classification of segmented symbols on benchmark databases, which is 98.93 prec. for a database of flow charts, 98.33 prec. for a database of crisis management icons, and 92.94 perc. for a database of digits. Second, we used the descriptor in the task of simultaneous segmentation and recognition of graphical symbols. Our method creates symbol candidates by grouping spatially close strokes. Symbol candidates are classified by a multiclass SVM classifier learned on a dataset with negative examples. Thus, some portion of the candidates is filtered out. The joint segmentation and classification was tested on diagrams from the flowchart database. We were able to find 91.85 prec. of symbols while generating 8.8 times more symbol candidates than is the number of true symbols per diagram in average.

We show that solving the LP relaxation of the MAP inference problem in graphical models (also known as the min-sum problem, energy minimization, or weighted constraint satisfaction) is not easier than solving any LP. More precisely, any polytope is linear-time representable by a local marginal polytope and any LP can be reduced in linear time to a linear optimization (allowing infinite weights) over a local marginal polytope.

This paper announces a ground truthed database of on-line handwritten mathematical formulae. It have recently been collected in our group in connection with the research on methods for structural pattern recognition. Unlike the availability of handwritten characters or texts, collections of structural objects are rather scarce, thus we would like to provide them to the community. We also present the methodology and tools used for data acquisition. Finally, we report on our experiment with the automatic generation of additional samples. The process utilizes the dataset to extract statistical descriptions of symbols alignments and relative sizes.

We introduce a localization and mapping approach suitable for a humanoid robot Nao. The proposed method is using data acquired from a single VGA camera, mounted on the head of the robot. It combines two different approaches together to create a detailed map and accurately locate the robot. Firstly, we present a Simultaneous Localization and Mapping technique (SLAM) based on a sparse 3D point cloud reconstruction. Secondly, we investigate the possibilities of enriching the created map by the detection of special markers. Moreover, we describe the options of using the special markers to directly navigate the robot. The main benefit of our method is in the fact we are using only basic equipment of the robot Nao (no extra devices are needed e.g. external cameras) and we do not need high number of special markers in the scene. We use them to specify the created map. Thus, the method will not fail when no marker is detected. The accuracy of our method is tested using a robotic simulation environment Webots and the robustness is verified on a real robot Nao. The results show that our approach makes it possible to safely navigate the robot Nao.

We present a new model of a two-dimensional computing device called restarting tiling automaton. The automaton defines a set of tile-rewriting, weight-reducing rules and a scanning strategy by which a tile to rewrite is being searched. We investigate properties of the induced families of picture languages. Special attention is paid to picture languages that can be accepted independently of the scanning strategy. We show that this family strictly includes REC and exhibits similar closure properties. Moreover, we prove that its intersection with the set of one-row languages coincides with the regular languages.',NULL); keyword('two-dimensional languages

We present a new model of a two-dimensional computing device called sgraffito automaton and demonstrate its significance. In general, the model is simple, allows a clear design of important computations and defines families exhibiting good properties. It does not exceed the power of finite-state automata when working over one-dimensional inputs. On the other hand, it induces a family of picture languages that strictly includes REC and the deterministic variant recognizes languages in DREC as well as those accepted by four-way automata.

We study hand-drawn objects with structure as a way of human-machine communication. The objects include various schemas like building plans, electronic circuits, filled forms or notations like mathematical or chemical formulae. They usually carry a quite complex information in a form which is intelligible to the addressed side, thus we consider them as important means of information representation and transmission. We identify the main principles relating to the structure recognition as it is performed by humans and we outline how the principles can be simulated by machines.

We present a system for on-line mathematical formulas recognition. The main principles of the method we applied for recognition are explained. It is based on the structural construction paradigm and utilizes a sort of two-dimensional grammars called coordinate grammars. Grammar productions are used to model spatial relationships among mathematical symbols. The system itself has been developed as a web application in HTML5. We give details on its client-server architecture and user interface. We also discuss advantages of the chosen approach.

We present a summary of our work in progress related to mathematical formulae recognition. Our approach is based on the structural construction paradigm and two-dimensional grammars. It is a general framework and can be successfully used in the analysis of images containing objects exhibiting rich structural relations. In contrast to most of all other known approaches, the method does not treat symbols segmentation and structural analysis as two separate processes. This allows the system to solve arising ambiguities more reliably. We have already implemented pilot studies for the off-line as well as on-line mathematical formulae recognition showing that the proposed method can be effectively implemented and practically used.

We present a method for on-line mathematical formulae recognition based on the structural construction paradigm and two-dimensional grammars. In general, this approach can be successfully used in the analysis of images containing objects that exhibit rich structural relations. An important benefit of the structural construction is in not treating symbols segmentation and structural analysis as two separate processes which allows the system to perform segmentation in the context of the whole formula structure - this can help to solve arising ambiguities more reliably. We show that the proposed method can be effectively implemented and practically used.

This contribution advocates that two-dimensional context-free grammars can be successfully used in the analysis of images containing objects that exhibit structural relations. The idea of structural construction is further developed. The approach can be made computationally efficient, practical and be able to cope with noise. We have developed and tested the method on a pilot study aiming at recognition of off-line mathematical formulae. The other novelty is not treating symbol segmentation in the image and structural analysis as two separate processes. This allows the system to recover from errors made in initial symbol segmentation.