Wyniki wyszukiwania - BazTech

1

Reversible Regular Languages : Logical and Algebraic Characterisations

Gastin Paul, Manuel Amaldev, Govind R.

Fundamenta Informaticae

|

2021

|

Vol. 180, nr 4

333--350

EN

We present first-order (FO) and monadic second-order (MSO) logics with predicates ‘between’ and ‘neighbour’ that characterise the class of regular languages that are closed under the reverse operation and its subclasses. The ternary between predicate bet(x, y, z) is true if the position y is strictly between the positions x and z. The binary neighbour predicate N(x, y) is true when the the positions x and y are adjacent. It is shown that the class of reversible regular languages is precisely the class definable in the logics MSO(bet) and MSO(N). Moreover the class is definable by their existential fragments EMSO(bet) and EMSO(N), yielding a normal form for MSO formulas. In the first-order case, the logic FO(bet) corresponds precisely to the class of reversible languages definable in FO(<). Every formula in FO(bet) is equivalent to one that uses at most 3 variables. However the logic FO(N) defines only a strict subset of reversible languages definable in FO(+1). A language-theoretic characterisation of the class of languages definable in FO(N), called locally-reversible threshold-testable (LRTT), is given. In the second part of the paper we show that the standard connections that exist between MSO and FO logics with order and successor predicates and varieties of finite semigroups extend to the new setting with the semigroups extended with an involution operation on its elements. The case is different for FO(N) where we show that one needs an additional equation that uses the involution operator to characterise the class. While the general problem of characterising FO(N) is open, an equational characterisation is shown for the case of neutral letter languages.

2

CospanSpan(Graph) : a Compositional Description of the Heart System

Gianola Alessandro, Kasangian Stefano, Manicardi Desiree, Sabadini Nicoletta, Schiavio Filippo, Tini Simone

Fundamenta Informaticae

|

2020

|

Vol. 171, nr 1-4

221--237

EN

In this paper, we recall the basic features of the CospanSpan(Graph) algebra for the compositional description of reconfigurable hierarchical networks. In particular, we focus on compositionality and on the possibility of describing the interactions among physical/biological systems, using a parallel with communication operation not considered in the usual Kleene’s algebra. As a novel application, we give a complete compositional description in Span(Graph) of a simplified version of the heart system.

3

P Colonies Processing Strings

Cienciala L., Ciencialová L., Csuhaj-Varjú E.

Fundamenta Informaticae

|

2014

|

Vol. 134, nr 1/2

51--65

EN

In this paper we introduce and study P colonies where the environment is given as a string. These constructs, called automaton-like P colonies or APCol systems, behave like automata: during functioning, the agents change their own states and process the symbols of the string. We show that the family of ε-free languages accepted by jumping finite automata is properly included in the family of languages accepted by APCol systems with one agent and any ε-free recursively enumerable language can be obtained as a projection of a language accepted by an automaton-like P colony with two agents.

4

On the Transition Reduction Problem for Finite Automata

Dahmoune M., Abdalaoui E. H., Ziadi D.

Fundamenta Informaticae

|

2014

|

Vol. 132, nr 1

79--94

EN

In this paper we apply the concept of common follow sets (CFS) of a regular expression to homogeneous finite state automaton. Based on this concept and using particular binary trees, we devise an efficient algorithm to reduce (minimize) the number of transitions of the automaton recognizing the language L(En) denoted by the regular expression En= (1 + ε) · (2 + ε) · (3 + ε) · · · (n+ε). Experiments reveal that for small values of n, all ε –free NFAs with n+1 states and with a minimum number of transitions for L(En) are exactly those obtained by our construction. Also, the produced ε-free NFA is asymptotically minimal, in the sense that the number of transitions is equivalent to n(log2 n)2 which corresponds in the same time to the upper and the lower bound. We conjecture that our construction is not only a reduction but a minimization for L(En).

5

On Conditions for Modular Verification in Systems of Synchronising Components

Drábik P., Maggiolo-Schettini A., Milazzo P.

Fundamenta Informaticae

|

2012

|

Vol. 120, nr 3/4

259-274

EN

Property preservation is investigated as an approach to modular verification, leading to reduction of the property verification time for formal models. For modelling purposes, formalisms with multi-way synchronisations are considered. For the modular verification technique to work, a specific type of synchronisation is required for which a sufficient and necessary condition is identified. It is a requirement on the semantics of the formalism, which is restricted to permit simultaneous execution only of component moves that make reference to each other. Implications for modular verification of several well-known formalisms for concurrent systems are investigated.

6

An Improved Construction of Deterministic Omega-automaton Using Derivatives

Redziejowski R.R.

Fundamenta Informaticae

|

2012

|

Vol. 119, nr 3/4

393-406

EN

In an earlier paper, the author used derivatives to construct a deterministic automaton recognizing the language defined by an ω-regular expression. The construction was related to a determinization method invented by Safra. This paper describes a new construction, inspired by Piterman's improvement to Safra’s method. It produces an automaton with fewer states. In addition, the presentation and proofs are simplified by going via a nondeterministic automaton having derivatives as states.

7

The association automata as a mechanism for memory organization

Piech H.

Prace Naukowe Instytutu Matematyki i Informatyki Politechniki Częstochowskiej

|

2011

|

Vol. 10, nr 1

205-213

EN

The association process is one of man's attitudes of mind and is connected with its functions. It is connected with retaining, remembering and forgetting. It also refers to the stages of attitude of mind. The sequence of associations is adequate for the process of analyzing different possibilities of finding a solution. We can find many analogies to practical situations regarding current conditions and limits. We want to propose a mechanism for automatic reactions to environment changes. In this case, our automaton should react not only upon a known situation structure but also create new associations with their properties (attributes). We assume that all perceptions can be sent to all so-called nodes of association. Every association is represented by its name. Every association is evoked by a set of generators based on different sets of attributes. We introduce several new notations such as background, depth, domination or profile associations. The proposed automata can be implemented in transporting, routing, military and security strategies.

8

Association automata functioning analysis

Piech H.

Prace Naukowe Instytutu Matematyki i Informatyki Politechniki Częstochowskiej

|

2011

|

Vol. 10, nr 2

205-215

EN

In this aricle we analyze a mechanism for automatic reactions to environment changes. In this case, an association automaton should react not only upon a known situation structure but should also create new associations with their properties (attributes). We assume that all perceptions can be sent to all so-called nodes of association. Every association is represented by its name. Every association is evoked by a set of generators based on different sets of attributes. The analysis regards the life, creation and annihilation of associations and the influences on their changes in perception.

9

Resource Driven Automata Nets

Bashkin V.A., Lomazova I.A.

Fundamenta Informaticae

|

2011

|

Vol. 109, nr 3

223-236

EN

A new formalism of Resource Driven Automata Nets (RDA-nets) is presented. A RDAnet has two levels: a system level is represented by a net of active resources, describing distribution of agents/resources and their interactions; agents in an object level are finite automata, communicating via ports and shared resources of a system level. RDA-nets are assigned for modeling mobility in multi-agent systems from the resource dependence perspective. We prove that RDA-nets have the same expressive power as Petri nets and give examples of modeling agent communications, dynamics and mobility.

10

Subdirectly irreducible fibered automata, Part 2

Mućka A.

Demonstratio Mathematica

|

2011

|

Vol. 44, nr 1

1-15

EN

An earlier paper characterized all subdirectly irreducible permutational fibered automata. This paper characterizes all subdirectly irreducible fibered automata which are not permutational. The characterization is both graphtheoretical and algebraic.

11

Zastosowanie rozmytych automatów komórkowych w długoterminowym prognozowaniu przestrzennych obciążeń elektroenergetycznych

Wasilewski J.

Rynek Energii

|

2010

|

nr 1

26-31

PL

W niniejszym referacie przedstawia się nową oryginalną metodę długoterminowego prognozowania rozkładu przestrzennego zapotrzebowania na moc i energię elektryczną w aglomeracjach miejskich. Proponuje się podejście "od szczegółu do ogółu" (ang. bottom-up) do problemu prognozowania przestrzennego. Podejście takie nie uwzględnia zmien-nych objaśniających modelu o charakterze globalnym (wielkoobszarowym). Identyfikuje się jedynie predyktory o charakterze lokalnym, a następnie znajduje się optymalną postać modelu prognostycznego, który jest oparty na technice rozmytych automatów komórkowych. Zaprezentowano uogólniony model prognostyczny, identyfikację jego parametrów oraz testową (wygasłą) prognozę przestrzenną zapotrzebowania na energię elektryczną dla jednej z dzielnic m. st. Warszawy - Białołęki. Dokonano także analizy błędów prognozy wygasłej w celu określenia jakości zaproponowanej metody prognostycznej.

EN

This paper deals with a new original method of spatial electric load forecasting for urban agglomerations. A bottom-up approach is proposed which does not take into account the global exogenous varieties. Only local exogenous varieties affecting the spatial electric load distribution in a forecasting model are identified. For this purpose a technique of fuzzy cellular automata is used. The forecasting model as well as identified model parameters have been presented. Additionally, a test prediction of spatial electric load forecasting has been carried out in order to verify the proposed forecasting method.

12

A minimization algorithm of 1-way quantum finite automata

Siedlecka-Lamch O.

Metody Informatyki Stosowanej

|

2010

|

nr 4 (24)

73-79

EN

A minimization of finite automata is important for designing of computer's hardware and software. A finite automata can be a model of any system with finite number of states. A limitation of number of states will save resources and time. In this article 1-way quantum finite automata is presented. We describe its characteristics, behaviour and languages accepted by it. This type of automata can be in future exploited to design and checking the behaviour of quantum systems, in lexical anaiyzer of a compiler, that will be used on quantum computers, or in verification systems. Also in this case Iimitation of states will save resources. The article holds formulated definition of indistinguishableness relation for 1-way quantum finite automata, on base of which minimization algorithm was created. Additionally, the algorithm 's complexity analysis and example of behaviour is holded.

13

Metoda tworzenia funkcji równań zależnościowych w systemach SRK

Maciejewski M., Zabłocki W.

Logistyka

|

2010

|

nr 4

CD-CD

PL

W publikacji przedstawiono metodę tworzenia funkcji i równań zależnościowych na podstawie równań stanu opisujących system srk jako układ przełączający. Analiza systemu srk jako układu przełączającego pozwala wyróżnić w strukturze tego układu szereg automatów składowych odwzorowujących przebiegi, jak i obiekty sterowane. Do opisu tych automatów zastosowano równania stanu. Metoda ta umożliwiła sformułowanie funkcji i równań zależnościowych, które można zastosować do celów algorytmizacji. Ponadto zastosowanie tej metody pozwala zbadać własności tych automatów a tym samym i systemu srk.

EN

In the publication a method of creating the function and interlocking equations was presented on the basis of equations of the state describing the ATC system as the switching machine. Analysis of the ATC system as the switching machine lets single the row of automaton in the structure of this system as components reflecting of the rout process, as controlled objects. Equations of the state were used to the description of these machines. This method enabled to formulate the interlocking function and equations whom it is possible to apply to purposes of the algorithmization. Moreover applying this method allows to examine properties of these automaton hence and of ATC system. The required property of these automaton is among others their observability.

14

On the Borel Complexity of MSO Definable Sets of Branches

Bojańczyk M., Niwiński D., Rabinovich A., Radziwończyk–Syta A., Skrzypczak M.

Fundamenta Informaticae

|

2010

|

Vol. 98, nr 4

337-349

EN

An infinite binaryword can be identified with a branch in the full binary tree. We consider sets of branches definable in monadic second-order logic over the tree, where we allow some extra monadic predicates on the nodes. We show that this class equals to the Boolean combinations of sets in the Borel class Σ over the Cantor discontinuum. Note that the last coincides with the Borel complexity of ω-regular languages.

15

5'→3' Watson-Crick AutomataWith Several Runs

Leupold P., Nagy B.

Fundamenta Informaticae

|

2010

|

Vol. 104, nr 1/2

71-91

EN

5'→3' WK-automata are Watson-Crick automata whose two heads start on opposite ends of the input word and always run in opposite directions. One full reading in both directions is called a run. We prove that the expressive power of these automata increases with every additional run that they can make, both for deterministic and non-deterministic machines. This defines two incomparable infinite hierarchies of language classes between the regular and the context-sensitive languages. These hierarchies are complemented with classes defined by several restricted variants of 5'→3' WK-automata like stateless automata. Finally we show that several standard problems are undecidable for languages accepted by 5'→3' WK-automata in only one run, for example the emptiness and the finiteness problems.

16

Subdirectly irreducible fibered automata

Mućka A.

Demonstratio Mathematica

|

2010

|

Vol. 43, nr 4

739-753

EN

A permutational automaton is a fibered automaton with one-element event set or an empty state space. This paper characterizes all subdirectly irreducible permutational automata.

17

Bisimulation Minimisation of Weighted Automata on Unranked Trees

Högberg J., Maletti A.

Fundamenta Informaticae

|

2009

|

Vol. 92, nr 1-2

103-130

EN

Several models of automata are available that operate unranked trees. Two well-known examples are the stepwise unranked tree automaton (suta) and the parallel unranked tree automaton (puta). By adding a weight, taken from some semiring, to every transition we generalise these two qualitative automata models to quantitative models, thereby obtaining weighted stepwise unranked tree automata (wsuta) and weighted parallel unranked tree automata (wputa); the qualitative automata models are reobtained by choosing the BOOLEAN semiring. The weighted versions have applications in natural language processing, XML-based data management and quantitative information retrieval. We address the minimisation problem of wsuta and wputa by using (forward and backward) bisimulations and we prove the following results: (1) for every wsuta an equivalent forward (resp. backward) bisimulation minimal wsuta can be computed in time O(mn) where n is the number of states and m is the number of transitions of the given wsuta; (2) the same result is proved for wputa instead of wsuta; (3) if the semiring is additive cancellative or the BOOLEAN semiring, then the bound can be improved to O(mlog n) for both wsuta and wputa; (4) for every deterministic puta we can compute a minimal equivalent deterministic puta in time O(mlog n); (5) the automata models wsuta, wputa, and weighted unranked tree automaton have the same computational power.

18

The graphs of fibered automata

Mućka A.

Demonstratio Mathematica

|

2008

|

Vol. 41, nr 1

23-32

EN

Fibered automata can be described by their transition diagrams, certain edge-labelled digraphs. We describe digraphs that are unlabelled transition diagrams of fibered automata.

19

Finite state automata built on DNA

Nowak K., Plucienniczak A.

Biocybernetics and Biomedical Engineering

|

2008

|

Vol. 28, no. 4

3-19

EN

This paper describes a non-deterministic finite-state automaton based on DNA strands. The automaton uses massive parallel processing offered by molecular approach for computation and exhibits a number of advantages over traditional electronic implementations. This device is used to analyze DNA molecules, whether they are described by specified regular expression. Presented ideas are confirmed by experiment performed in a genetic engineering laboratory.

20

Continuous Separation of Game Languages

Arnold A., Niwiński D.

Fundamenta Informaticae

|

2007

|

Vol. 81, nr 1-3

19-28

EN

We show that a family of tree languages W(i,k) , previously used by J. Bradfield, and by the first author to show the strictness of the Rabin-Mostowski index hierarchy of alternating tree automata, forms a hierarchy w.r.t. the Wadge reducibility. That is, [formula] if and only if the index [...] is above (i,k) . This is one of the few separation results known so far, concerning the topological complexity of non-deterministically recognizable tree languages, and one of the few results about finite-state recognizable non-Borel sets of trees.