| Authors |
Title |
|
M. Bresler, D. Průša, V. Hlaváč |
Online recognition of sketched arrow-connected diagrams |
|
International Journal on Document Analysis and Recognition, Vol. 19 (3), 2016, pp. 253-267. |
|
Abstract: 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. |
|
Links: BibTeX, DOI |
|
M. Bresler, D. Průša, V. Hlaváč |
Recognizing Off-line Flowcharts by Reconstructing Strokes and Using On-line Recognition Techniques |
|
In: Proceedings of the International Conference on Frontiers in Handwriting Recognition (ICFHR 2016), Shentzen, China, October 23-26, 2016, pp. 48-53. |
|
Abstract: 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. |
|
Links: BibTeX, DOI |
|
L. Krtek, F. Mráz |
Two-Dimensional Limited Context Restarting Automata |
|
In: Fundamenta Informaticae, Vol. 148 (3-4), 2016, pp. 309-340. |
|
Abstract: Motivated by possible machine learning of picture languages, we introduce a new two-dimensional automaton called two-dimensional limited context restarting automaton.
Our model is a simplification of the two-dimensional restarting tiling automaton, from which it differs in that
it does not require to scan input pictures in a fixed order. We show that the two-dimensional limited
context restarting automaton is equally powerful as the two-dimensional sgraffito automaton.
Moreover, the correctness preserving version of the new model, while still being nondeterministic,
is equivalent to the deterministic sgraffito automaton. However, the property of being correctness
preserving is not even semi-decidable for two-dimensional limited context restarting automata. |
|
Links: BibTeX, DOI |
|
F. Mráz, F. Otto, D. Průša |
Two-Dimensional Limited Context Restarting Automata |
|
RAIRO - Theoretical Informatics and Applications, 2016, Cambridge University Press, publication ahead of print, preprint published online on December 7, 2016 |
|
Abstract: With the aid of homogeneous morphisms, we turn the deterministic two-dimensional two-way
ordered restarting automaton and its extended variant into devices that compute transductions of pictures, and we study the resulting classes of transductions in detail. |
|
Links: BibTeX, DOI |
|
I. Mrázová, P. Zvirinský |
Extraction and Interpretation of Textual Data from Czech Insolvency Proceedings (Technical Report) |
|
TR No. 2016/1/KTIML, December 2016, 11 p. |
|
Abstract: Recently, the Czech Insolvency Register covers about 200 000 insolvency proceedings commenced since 2008. In order to better
assess the real impact of indebtedness across the Czech society, the data
about the creditors or the reasons for the debt might be of great value.
Unfortunately, the vast majority of such information is contained only
in scanned document copies attached to the insolvency proceedings. Our
goal is thus to extract textual data from the scanned pdf-files and to find
the wanted information in the obtained texts. |
|
Links: Address requests for download to: I. Mrázová |
|
F. Otto, F. Mráz |
Cyclically extended variants of Sgraffito and restarting automata for picture languages |
|
In: H. Bordihn, R. Freund, B. Nagy, G. Vaszil (Eds.): Proceedings of the Eighth Workshop on Non-Classical Models of Automata and Applications (NCMA 2016), šsterreichische Computer Gesellschaft, vol. 321 of books@ocg.at, 2016, pp. 259-273. |
|
Abstract: Here we introduce and study cyclic extensions of deterministic Sgraffito automata and of deterministic
two-dimensional two-way ordered restarting automata for picture languages. Such
a cyclically extended automaton can move in a single step from the last column (or row) of
a picture to the first column (or row). For deterministic Sgraffito automata, we show that
this cyclic extension does not increase the expressive power of the model, while for deterministic
two-dimensional two-way restarting automata, the expressive power is strictly increased by
allowing cyclic moves. In fact, for the latter automata, we take the number of allowed cyclic
moves in any column or row as a parameter, and we show that already with a single cyclic move
per column (or row) the deterministic two-dimensional extended two-way restarting automaton
can be simulated. On the other hand, we show that two cyclic moves per column or row already
give the same expressive power as any finite number of cyclic moves. Finally, we show that for one-row pictures (that is, strings), already one cyclic move suffices. |
|
Links: BibTeX |
|
F. Otto, F. Mráz |
Regulated variants of limited context restarting automata |
|
Theoretical Compute Science, vol. 682, pp. 190-207, 2016. |
|
Abstract: In the literature various types of restarting automata have been studied that are based on contextual rewriting. A word w is accepted by such an automaton if, starting from the initial configuration that corresponds to input w, the tape contents is reduced to a particular word within a finite number of applications of these contextual rewritings. Here we extend the limited context restarting automata by using additional global means to structure the reductions they execute. In fact, we study regulated lc-R-automata, for which a regular control language is used to restrict the set of admissible reduction sequences, and we propose random context conditions to restrict the place at which a transition of an lc-R-automaton can be applied. |
|
Links: BibTeX, DOI |
|
M. Plátek, K. Oliva |
Redukční analýza A-stromů s minimalistickými omezeními |
|
In: Proceedings of the 16th ITAT Conference on Information Technologies - Applications and Theory, Tatranské Matliare, Slovakia, September 15-19, 2016, pp. 26-33. |
|
Abstract: Tento příspěvek navazuje na náš lonský příspěvek na ITATu. Zpracovává novým způsobem redukční
analýzu na A-stromech, které jsou formalizací stromů,
zpracovaných metodikou pro analytickou rovinu Pražského
závislostního korpusu (PDT). Redukční analýza A-stromů sestává z minimálních korektních redukcí, které
používají pouze elementární operace delete a shift.
Hlavním cílem je vyvinout formální prostředky, které
by exaktně zachycovaly lingvisticky pozorované minimalistické
vlastnosti jednotlivých parametrů stromové redukční analýzy stromů ve formátu PDT a dovolily následně realizovat podobná pozorování na různých přirozených,
či umělých jazycích.
Pomocí pozorování lingvistického typu upřesnujeme
strukturálně-složitostní vlastnosti A-stromů se závislostmi
a koordinacemi. Zvýraznujeme vlastnosti, kterými se závislosti
a koordinace liší. |
|
Links: BibTeX, Publication |
|
D. Průša |
Complexity of Sets of Two-Dimensional Patterns |
|
In: Y.-S. Han, K. Salomaa (Eds.): Proceedings of the 21st International Conference on Implementation and Application of Automata (CIAA 2016), LNCS, Vol. 9705, 2016, pp. 236-247. |
|
Abstract: 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. |
|
Links: BibTeX, DOI |
|
D. Průša, K. Reinhardt |
Undecidability of the emptiness problem for context-free picture languages |
|
Theoretical Computer Science, 2016, in print. |
Abstract:  |
|
Links: BibTeX, DOI |
|
J. van Leeuwen, J. Wiedermann |
Knowledge, Representation, and the Dynamics of Computation |
|
In: G. Dodig-Crnkovic, R. Giovagnoli (Eds.): Representation and Reality: Humans, Animals and Machines. Studies in Applied Philosophy, Epistemology and Rational Ethics, Vol. 28, Springer, 2017. |
|
Abstract: Cognitive processes are often modelled in computational terms. Can this
still be done if only minimal assumptions are made about any sort of representation
of reality? Is there a purely knowledge-based theory of computation that explains
the key phenomena which are deemed to be computational in both living and artificial
systems as understood today? We argue that this can be done by means of
techniques inspired by the modelling of dynamical systems. In this setting, computations
are defined as curves in suitable metaspaces and knowledge is generated
by virtue of the operation of the underlying mechanism, whatever it is. Desirable
properties like compositionality will be shown to fit naturally. The framework also
enables one to formally characterize the computational behaviour of both knowledge
generation and knowledge recognition. The approach may be used in identifying
when processes or systems can be viewed as computational in general. Several
further questions pertaining to the philosophy of computing are considered. |
|
Links: BibTeX |
|
J. Vojt |
Deep neural networks and their implementation |
|
Diploma thesis, Faculty of Mathematics and Physics, Charles University, Prague, 2016, 96 p. |
|
Abstract: Deep neural networks represent an effective and universal model capable
of solving a wide variety of tasks. This thesis is focused on three different
types of deep neural networks – the multilayer perceptron, the convolutional neural
network, and the deep belief network. All of the discussed network models are
implemented on parallel hardware, and thoroughly tested for various choices of
the network architecture and its parameters. The implemented system is accompanied
by a detailed documentation of the architectural decisions and proposed
optimizations. The efficiency of the implemented framework is confirmed by the
results of the performed tests. A significant part of this thesis represents also additional
testing of other existing frameworks which support deep neural networks.
This comparison indicates superior performance to the tested rival frameworks
of multilayer perceptrons and convolutional neural networks. The deep belief
network implementation performs slightly better for RBM layers with up to 1000
hidden neurons, but has a noticeably inferior performance for more robust RBM
layers when compared to the tested rival framework. |
|
Links: BibTeX, Thesis |
|
D. Průša |
Non-Recursive Trade-offs between Two-Dimensional Automata and Grammars |
|
Theoretical Computer Science, Vol. 610/A, January 2016, pp. 121–132. |
|
Abstract: 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. |
|
Links: BibTeX, DOI |
|
J. Wiedermann, J. van Leeuwen |
Understanding and Controlling Artificial General Intelligent Systems |
|
Submitted to The 10th AISB Symposium on Computing and Philosophy: Language, cognition, and computation, AISB Convention, University of Bath, UK, 19-21 April 2017 (in review). |
|
Abstract: Artificial general intelligence (AGI) systems are advancing
in all parts of our society. The potential of autonomous systems
that surpass the capabilities of human intelligence has stirred debates
everywhere. How should ‘super-intelligent’ AGI systems be viewed
so they can be feasibly controlled? We approach this question based
on the viewpoints of the epistemic philosophy of computation, which
treats AGI systems as computational systems processing knowledge
over some domain. Rather than considering their autonomous development
based on ‘self-improving software’, as is customary in the
literature about super-intelligence, we consider AGI systems as operating
with ‘self-improving epistemic theories’ that automatically
increase their understanding of the world around them. We outline
a number of algorithmic principles by which the self-improving theories
can be constructed. Then we concentrate on the problem of
aligning the behavior of AGI systems with human values in order
to make such systems safe. This issue arises concretely when one
studies the social and ethical aspects of human-robot interaction in
advanced AGI systems as they exist already today. Necessarily, the
behavior of any such system will depend on its own world-view. We
argue that there is no ‘universal’ AGI system whose values will always
agree with the values of any other system. Finally, based on
the principles of interactive proof systems, we design an architecture
of AGI systems and an interactive scenario that will enable one
to detect in their behavior deviations from the prescribed goals. The
conclusions from our analysis of super-intelligent systems temper the
over-optimistic expectations and over-pessimistic fears of singularity
believers, by grounding the ideas on super-intelligent AGI systems in
more realistic foundations. |
|
Links: BibTeX |
|
F. Mráz, F. Otto, and D. Průša |
Some classes of rational functions for pictures |
|
RAIRO - Theoretical Informatics and Applications, vol. 50, no. 4, pp. 351-369, 2016. |
|
Abstract: With the aid of homogeneous morphisms, we turn the deterministic two-dimensional two-way ordered restarting automaton and its extended variant into devices that compute transductions ofpictures, and we study the resulting classes of transductions in detail. |
|
Links: BibTeX, DOI |
Czech 