| Authors |
Title |
|
Y. Han and D. Průša |
Template-Based Pattern Matching in Two-Dimensional Arrays |
|
In: Proceedings of the 18th International Workshop on
Combinatorial Image Analysis (IWCIA 2017), Plovdiv, Bulgaria,
19-21 June 2017 (ICFHR 2016), vol. 9223 of LNCS, 2017, pp. 250-262. |
|
Abstract: We propose a framework for pattern matching in two-dimensional 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. |
|
Links: BibTeX, DOI |
|
F. Mráz and F. Otto |
Deleting deterministic restarting automata with two windows |
|
in 21st International Conference on Developments in Language Theory, DLT 2017, vol. 10396 of Lecture Notes in Computer Science, 2017, pp. 272-283. |
|
Abstract: We study deterministic restarting automata with two windows. In each cycle of a computation, these det-2-RR-automata can perform up to two delete operations, one with each of their two windows. We study the class of languages accepted by these automata, comparing it to other well-known language classes and exploring closure properties. |
|
Links: BibTeX, DOI |
|
F. Mráz and F. Otto |
On deleting deterministic restarting automata that have two windows |
|
Submitted to JALC (Journal of Automata, Languages and Combinatorics), 2017. |
|
Abstract: We study deterministic restarting automata with two windows, abbreviated as det-2-
RR-automata. In each cycle of a computation, a det-2-RR-automaton can perform
up to two delete operations, one with each of its two windows. We study the class
of languages accepted by these automata, comparing it to other well-known language
classes and exploring closure properties and algorithmic properties. |
|
Links: BibTeX |
|
I. Mrázová, P. Zvirinský |
Extraction and Interpretation of Textual Data from Czech Insolvency Proceedings |
|
Submitted to International Conference on Artificial Intelligence and Soft Computing (ICAISC 2017), in Proc. of ICAISC 2017, Part II, vol. LNAI 10246, 2017, pp. 116-125. |
|
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: BibTeX, DOI |
|
F. Otto and F. Mráz |
Automata with cyclic move operations for picture languages |
|
Special issue of RAIRO-Theor. Inf. Appl. Dedicated to NCMA 2016, 2017, Accepted on December 10, 2017. |
|
Abstract: Here we study cyclic extensions of 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 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. |
|
Links: BibTeX |
|
M. Plátek, K. Oliva, and D. Pardubská |
Analysis by reduction of analytical PDT-trees |
|
in Ninth Workshop on Non-Classical Models of Automata and Applications, NCMA 2017, Prague, Czech Republic, August 17-18, 2017, vol. 318 of books@ocg.at, Vienna, 2017, pp. 211-226. |
|
Abstract: In this paper we introduce the notion of full analysis by reduction on A-trees, and some of its
constraints. It serves as a formal tool that helps to find adequate (types of ) rules for restarting
automata describing Czech syntax. A-trees represents a formalization of trees as they are used in
the Prague Dependency Treebank (PDT). The full analysis by reduction of A-trees consists of all
minimal correct reductions using two elementary operations, namely the delete and shift. The
main focus is on the development of a formalism allowing for an exact formulation of linguistic
properties of individual parameters of analysis by reduction of trees in the PDT format. With
the help of linguistic observations we refine complexity properties of A-trees with respect to
dependency and coordination relations. We emphasize those properties in which these relations
differ. |
|
Links: BibTeX |
|
M. Plátek and F. Otto |
On h-Lexicalized Restarting Automata |
|
in 15th International Conference on Automata and Formal Languages (AFL 2017), vol. 52 of EPTCS, 2017, pp. 219-233. |
|
Abstract: Following some previous studies on restarting automata, we introduce a refined model - the h-lexicalized restarting automaton (h-RLWW). We argue that this model is useful for expressing lexicalized syntax in computational linguistics. We compare the input languages, which are the languages traditionally considered in automata theory, to the so-called basic and h-proper languages, which are (implicitly) used by categorial grammars, the original tool for the description of lexicalized syntax. The basic and h-proper languages allow us to stress several nice properties of h-lexicalized restarting automata, and they are suitable for modeling the analysis by reduction and, subsequently, for the development of categories of a lexicalized syntax. Based on the fact that a two-way deterministic monotone restarting automaton can be transformed into an equivalent deterministic monotone RL-automaton in (Marcus) contextual form, we obtain a transformation from monotone RLWW-automata that recognize the class CFL of context-free languages as their input languages to deterministic monotone h-RLWW-automata that recognize CFL through their h-proper languages. Through this transformation we obtain automata with the complete correctness preserving property and an infinite hierarchy within CFL, based on the size of the read/write window. Additionally, we consider h-RLWW-automata that are allowed to perform multiple rewrite steps per cycle, and we establish another infinite hierarchy above CFL that is based on the number of rewrite steps that may be executed within a cycle. The corresponding separation results and their proofs illustrate the transparency of h-RLWW-automata that work with the (complete or cyclic) correctness preserving property. |
|
Links: BibTeX, DOI |
|
M. Plátek, F. Otto, and F. Mráz |
On h-Lexicalized Automata and h-Syntactic Analysis |
|
in ITAT 2017 Proceedings, vol. 1885 of CEUR Workshop Proceedings, pp. 40-47. |
|
Abstract: Following some previous studies on list automata
and restarting automata, we introduce a generalized
and refined model – the h-lexicalized restarting list automaton
(LxRLAW). We argue that this model is useful
for expressing transparent variants of lexicalized syntactic
analysis, and analysis by reduction in computational linguistics.
We present several subclasses of LxRLAW and
provide some variants and some extensions of the Chomsky
hierarchy, including the variant for the lexicalized syntactic
analysis. We compare the input languages, which
are the languages traditionally considered in automata theory,
to the so-called basic and h-proper languages. The
basic and h-proper languages allow stressing the transparency
of h-lexicalized restarting automata for a superclass
of the context-free languages by the so-called complete
correctness preserving property. Such a type of transparency
cannot be achieved for the whole class of contextfree
languages by traditional input languages. The transparency
of h-lexicalized restarting automata is illustrated
by two types of hierarchies which separate the classes of
infinite and the classes of finite languages by the same
tools. |
|
Links: BibTeX |
|
M. Plátek, F. Otto, and F. Mráz |
One-Way Restarting Automata and Their Sensitivity |
|
Submitted to International Journal of Foundations of Computer Science, Special Issue for AFL 2017, 2017. |
|
Abstract: Here we establish and study some exact tools that are suitable for the lexicalized syntactic
analysis (LSA) of natural and formal languages. Motivated by the linguistic method of
analysis by reduction we are interested in correctness preserving LSA. We introduce a
suitable model of automata, the h-lexicalized one-way restarting automata (h-RRWW),
and compare the properties of their input languages, which are the languages considered
traditionally in automata theory, to the properties of the so-called basic and h-proper
languages. These languages form the basic components for LSA.
With respect to their input languages, h-RRWW-automata are not sensitive to the
size of their read/write window and they allow computations that are far from being
correctness preserving. On the other hand, for their basic and h-proper languages, hRRWW-automata
ensure that the resulting computations are completely correctness
preserving, and they yield infinite ascending hierarchies of language classes within the
regular, the context-free, and the context-sensitive languages that are based on the size
of their read/write window. |
|
Links: BibTeX |
|
D. Průša |
Complexity of Matching Sets of Two-Dimensional Patterns by Two-Dimensional On-Line Tessellation Automaton |
|
International Journal of Foundations of Computer Science, vol. 28, no. 05, pp. 623-640, 2017. |
|
Abstract: 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. |
|
Links: BibTeX, DOI |
|
D. Průša and K. Reinhardt |
Undecidability of the Emptiness Problem for Context-Free Picture Languages |
|
Theoretical Computer Science, vol. 679, pp. 118-125, 2017. |
|
Abstract: 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 -> B C, A -> B C , and S -> lambda 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. |
|
Links: BibTeX, DOI |
|
Jan van Leeuwen and Jiří Wiedermann |
Knowledge, Representation and the Dynamics of Computation |
|
in Representation and Reality in Humans, Other Living Organisms and Intelligent Machines, G. Dodig-Crnkovic and R. Giovagnoli, Eds.: Springer, 2017, vol. 28, pp. 69-89. |
|
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 such as
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 being computational in general. Several further questions
pertaining to the philosophy of computing are considered. |
|
Links: BibTeX, DOI |
|
Jan van Leeuwen and Jiří Wiedermann |
Turing Machines with One-sided Advice and Acceptance of the co-RE Languages |
|
Fundamenta Informaticae, vol. 153, no. 4, pp. 347--366, 2017. |
|
Abstract: We resolve an old problem, namely to design a ‘natural’ machine model for accepting
the complements of recursively enumerable languages. The model we present is based on nondeterministic
Turing machines with ‘one-sided’ advice. We prove that these machines precisely
accept the co-RE languages, without restriction on the advice functions that are used. We show
that for accepting a co-RE language, one-sided advice is as powerful as arbitrary advice, but
also that linearly bounded one-sided advice is sufficient. However, ‘long’ sublinear advice can
make Turing machines with one-sided advice accept more co-RE languages than ‘short’ sublinear
advice. We prove that infinite proper hierarchies of language classes inside co-RE can be devised,
using suitable increasing sequences of bounding functions for the allowed advice. The machine
model and the results dualize for the family of recursively enumerable languages. |
|
Links: BibTeX, DOI |
|
Jiří Wiedermann |
Nový pohled na výpočty a umělá inteligence |
|
in Kognícia a umelý život 2017, Trenčianske Teplice, Bratislava, 2017, pp. 190-193. |
|
Abstract: Klasický pohled na výpočty je chápe jako procesy generované počítačem, tj. soustřeďuje se na to, JAK jsou výpočty realizované. Nový pohled se zajímá o to, CO výpočty dělají, co je jejich smyslem - a to je generování znalostí. Výpočty tudíž chápeme jako procesy, které generují znalosti nad danou znalostní doménou v rámci příslušné znalostní teorie. Inteligence je pak schopnost získávat informace a transformovat je na znalosti, které jsou dále využívány pro řešení problémů. Ukážeme, že toto pojetí výpočtů umožní přirozeným způsobem definovat některé vyšší kognitivní funkce jako je zdůvodňování svých akcí, sebe-uvědomění, introspekce, porozumění znalostem, svobodná vůle, kreativita a také porozumění algoritmickým mechanismům, které stojí za rozvojem inteligence. Tento pohled je přínosný tím, že na elementárním abstraktním modelu kognitivního systému, který není zatížen žádnými technickými detaily, ukazuje, že všechny výše zmíněné kognitivní funkce souvisejí se specifickými znalostmi, které jsou generované v rámci téhož modelu. |
|
Links: BibTeX |
|
Jiří Wiedermann and Jan van Leeuwen |
Non-classical Turing machines: extending the notion of computation (invited talk) |
|
in Ninth Workshop on Non-Classical Models of Automata and Applications (NCMA 2017), vol. 329 of books@ocg.at, Vienna, 2017, pp. 29-40. |
|
Abstract: The goal of this paper is to broaden our understanding of computations based on the classical
paradigm of Turing machines. To this end we will point to models of non-classical Turing machines
that capture computational behavior of contemporary or emerging computing technologies
and that have been designed and studied by the authors. The guiding design principles of such
machines have been the currently existing or foreseeable technologies such as interactivity, nonuniform
evolution, unbounded time behavior, process cooperation, and relativistic time-space
effects. The computational behavior of these models and the fact that they mirror key aspects of
present or envisaged technologies jointly offer compelling reasons for modifying the traditional
and persisting view of computation. This change is quite a profound one: computations should
no longer be seen as finite processes whose parameters are fixed before the start of processing.
Rather, computations are potentially infinite evolutionary processes whose parameters can
change during the processing in an unpredictable way in interaction with their environment. |
|
Links: BibTeX |
|
Jan van Leeuwen and Jiří Wiedermann |
Understanding and Controlling Artificial General Intelligent Systems |
|
in Proc. of The 10th AISB, Symposium on Computing and Philosophy: Language, cognition, and computation, AISB Convention, University of Bath, UK, 2017, pp. 356-363. |
|
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 discuss 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. No general solution to this problem
is known. However, 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 AGI systems temper the over-optimistic expectations and overpessimistic
fears of singularity believers, by grounding the ideas on
super-intelligent AGI systems in more realistic foundations. |
|
Links: BibTeX |
|
R. Freund, F. Mráz, and D. Průša |
Ninth Workshop on Non-Classical Models of Automata and Applications |
|
NCMA 2017, Prague, Czech Republic, August 17-18, 2017. Vienna: Österreichische Computer Gesellschaft, 2017, vol. 329 of books@ocg.at. |
|
Abstract: |
|
Links: BibTeX |
Czech 