SeLeCt - struktury, učení a kognice

Publikace

Autori Název
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.
Abstrakt: 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.
Odkazy: 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.
Abstrakt: 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.
Odkazy: 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.
Abstrakt: 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.
Odkazy: 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.
Abstrakt: 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.
Odkazy: 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.
Abstrakt: 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.
Odkazy: 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.
Abstrakt: 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.
Odkazy: 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.
Abstrakt: 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.
Odkazy: 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.
Abstrakt: 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.
Odkazy: 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.
Abstrakt: 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.
Odkazy: 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.
Abstrakt: 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.
Odkazy: 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.
Abstrakt: 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.
Odkazy: 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.
Abstrakt: 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.
Odkazy: 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.
Abstrakt: 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.
Odkazy: 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.
Abstrakt: 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.
Odkazy: 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.
Abstrakt: 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.
Odkazy: 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.
Abstrakt: 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.
Odkazy: 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.
Abstrakt:
Odkazy: BibTeX

Poslední úprava: Neděle, 18.2.2018