Search results for "Theoretical Computer Science"

Quantum inductive inference by finite automata

2008

AbstractFreivalds and Smith [R. Freivalds, C.H. Smith Memory limited inductive inference machines, Springer Lecture Notes in Computer Science 621 (1992) 19–29] proved that probabilistic limited memory inductive inference machines can learn with probability 1 certain classes of total recursive functions, which cannot be learned by deterministic limited memory inductive inference machines. We introduce quantum limited memory inductive inference machines as quantum finite automata acting as inductive inference machines. These machines, we show, can learn classes of total recursive functions not learnable by any deterministic, nor even by probabilistic, limited memory inductive inference machin…

Complexity of probabilistic versus deterministic automata

2005

FPGA-based embedded Logic Controllers

2014

In general case, reconfigurable logic controllers (RLC) are included into reactive digital embedded systems, carrying out control for several processes proceeding concurrently. The paper presents a practical application of a formal, rule-based specification language in Gentzen sequent logic, which is used as an intermediate textual description of a control interpreted Petri net. On the other hand exactly the same description serves also as logic design expressions, related with different versions of functionally equivalent concurrent state machine models, considered on Register Transfer Level. The symbolic rule-based specification of Petri net-based embedded Logic Controllers (LCs) can be s…

Finite automata on timed ω-trees

2003

AbstractIn the last decade Alur and Dill introduced a model of automata on timed ω-sequences which extends the traditional models of finite automata. In this paper, we present a theory of timed ω-trees which extends both the theory of timed ω-sequences and the theory of ω-trees. The main motivation is to introduce a new way of specifying real-time systems and provide tools for studying decidability problems in related fields. We focus on the decision problems and their applications in system verification and synthesis.

Research of a Cellular Automaton Simulating Logic Gates by Evolutionary Algorithms

2003

This paper presents a method of using genetic programming to seek new cellular automata that perform computational tasks. Two genetic algorithms are used : the first one discovers a rule supporting gliders and the second one modifies this rule in such a way that some components appear allowing it to simulate logic gates. The results show that the genetic programming is a promising tool for the search of cellular automata with specific behaviors, and thus can prove to be decisive for discovering new automata supporting universal computation.

Metamodel Specialization for DSL Tool Building

2016

Most of domain-specific tool building and especially diagram editor building nowadays involves some usage of metamodels. However normally the metamodel alone is not sufficient to define an editor. Frequently the metamodel just defines the abstract syntax of the domain, mappings or transformations are required to define the editor. Another approach [8] is based on a fixed type metamodel, there an editor definition consists of an instance of this metamodel to be executed by an engine. However there typically a number of functionality extensions in a transformation language is required. The paper offers a new approach based on metamodel specialization. First the metamodel specialization based …

Cancellation, pumping and permutation in formal languages

1984

The Intersection of $3$-Maximal Submonids

2020

Very little is known about the structure of the intersection of two $k$-generated monoids of words, even for $k=3$. Here we investigate the case of $k$-maximal monoids, that is, monoids whose basis of cardinality $k$ cannot be non-trivially decomposed into at most $k$ words. We characterize the intersection in the case of two $3$-maximal monoids.

MLOG: a strongly typed confluent functional language with logical variables

1994

Poirriez, V., MLOG: a strongly typed confluent functional language with logical variables, Theoretical Computer Science 122 (1994) 201-223. A new programming language called MLOG is introduced. MLOG is a conservative extension of ML with logical variables. To validate our concepts, a compiler named CAML Light FLU0 was implemented. Numerous examples are presented to illustrate the possibilities of MLOG. The pattern matching of ML is kept for X-calculus bindings and an unification primitive is introduced for the logical variables bindings. A suspension mechanism allows cohabitation of pattern-matching and logical variables, Although the evaluation strategy for the application is fixed, the or…

An Approach to the Concept of Soft Fuzzy Proximity

2014

The purpose of this paper is to introduce the concept of soft fuzzy proximity. Firstly, we give the definitions of soft fuzzy proximity and Katsaras soft fuzzy proximity, and also we investigate the relations between the soft fuzzy proximity and slightly modified version of Katsaras soft fuzzy proximity. Secondly, we induce a soft fuzzy topology from a given soft fuzzy proximity by using soft fuzzy closure operator. Then, we obtain the initial soft fuzzy proximity from a given family of soft fuzzy proximities. So, we describe products in the category of soft fuzzy proximities. Finally, we show that a family of all soft fuzzy proximities on a given set constitutes a complete lattice.