Extensions of the Theory of Automata and Languages  Page description

Help  Print 
Back »
 

Details of project

  
Identifier
108448
Type K
Principal investigator Fülöp, Zoltán
Title in Hungarian Az automaták és formális nyelvek elméletének kiterjesztései
Title in English Extensions of the Theory of Automata and Languages
Keywords in Hungarian véges automaták, nyelvtanok, faautomaták, súlyozott automaták
Keywords in English finite automata, grammars, tree automata, weighted automata
Discipline
Mathematics (Council of Physical Sciences)100 %
Ortelius classification: Computational models
Panel Mathematics and Computing Science
Department or equivalent Department of Foundations of Computer Science (University of Szeged)
Participants Ésik, Zoltán
Fülöp, Zoltán
Gazdag, Zsolt Zoltán
Hajgató, Tamás
Iván, Szabolcs
Vágvölgyi, Sándor Árpád
Starting date 2014-01-01
Closing date 2018-12-31
Funding (in million HUF) 14.496
FTE (full time equivalent) 4.45
state closed project
Summary in Hungarian
A kutatás összefoglalója, célkitűzései szakemberek számára
Itt írja le a kutatás fő célkitűzéseit a témában jártas szakember számára.
Az elméleti kutatás célja az automaták, nyelvtanok kiterjesztéseinek
vizsgálata az algebra, logika és a kombinatórika módszereivel,
beleértve az algoritmikus kérdéseket és a felmerülő problémák
belső bonyolultságát, és figyelembe véve a hagyományosabb
kvalitatív kérdések mellett kvantitatív kérdéseket is.

Mi a kutatás alapkérdése?
Ebben a részben írja le röviden, hogy mi a kutatás segítségével megválaszolni kívánt probléma, mi a kutatás kiinduló hipotézise, milyen kérdéseket válaszolnak meg a kísérletek.
A kutatás alapkérdései az egyes automata és generatív modellek
kifejező erejének, számítási kapacitásának meghatározása, olyan
algebrai műveletek bevezetése és vizsgálata, melyek a modellek
viselkedésével szemben invariánsak, és ezzel felhasználhatók az
összetett rendszerek moduláris tervezésében.
Célunk az alapvető tulajdonságok eldönthetőségének vizsgálata
és a rájuk vonatkozó algoritmikus kérdések megválaszolása is, a
felmerülő algoritmikus kérdések osztályozása a megoldásukhoz
szükséges erőforrások mennyisége szerint.

Mi a kutatás jelentősége?
Röviden írja le, milyen új perspektívát nyitnak az alapkutatásban az elért eredmények, milyen társadalmi hasznosíthatóságnak teremtik meg a tudományos alapját. Mutassa be, hogy a megpályázott kutatási területen lévő hazai és a nemzetközi versenytársaihoz képest melyek az egyediségei és erősségei a pályázatának!
Az informatikában egyre bonyolultabb rendszerek leírására,
vizsgálatára, tervezésére, a rendszerek tulajdonságainak és a
specifikációknak való megfelelésük ellenőrzésének, valamint a
mesterséges és természetes nyelvek feldolgozásának eszközei
az automatákon és a generatív nyelvtanokon alapuló módszerek.

A kutatás ezen módszerek elméleti alapjának fejlesztéséhez járul hozzá
abból a célból, hogy az informatika új kihívásainak megfeleljenek.

A kutatás összefoglalója, célkitűzései laikusok számára
Ebben a fejezetben írja le a kutatás fő célkitűzéseit alapműveltséggel rendelkező laikusok számára. Ez az összefoglaló a döntéshozók, a média, illetve az érdeklődők tájékoztatása szempontjából különösen fontos az NKFI Hivatal számára.
A véges automaták és a generatív nyelvtanok bevezetésére mintegy 50
évvel ezelőtt került sor. Széles körűen felhasználásra kerültek áramkörök,
hardver berendezések és szoftver rendszerek tervezésében, az idegi
folyamatok modellezésében, a mesterséges és természetes nyelvek
feldolgozásában, hogy csak néhány alkalmazásukat említsük.

Az informatika egyre bonyolultabb és nagyméretű rendszereinek
fejlesztése és biztonságos működtetése egyre összetettebb matematikai
modelleket igényel, melyek vizsgálata a pályázat alapvető célkitűzése
annak érdekében, hogy a korszerű kihívásoknak is megfeleljenek.
Summary
Summary of the research and its aims for experts
Describe the major aims of the research for experts.
The aim of the proposed theoretical research is the investigation
of the extensions of the notion of automata, grammars and related
concepts, by the methods of algebra, logic and combinatorics, to
study their algorithmic properties and the inherent computational
complexity of the problems, and to consider both quantitative and
qualitative aspects, in order to contribute to the widening of the scope
of their applicability in the description and design, analysis, processing
and verification of complex systems and structured data.

What is the major research question?
Describe here briefly the problem to be solved by the research, the starting hypothesis, and the questions addressed by the experiments.
The basic questions to be studied are the determination
of the expressive power of the considered automata
models and generative mechanisms, the introduction
of algebraic operations which are invariant with respect to the
behavior of the models and thus can be used in the
modular design of complex systems. We plan to
study the decidability and complexity of the the basic
properties and to answer algorithmic questions.

What is the significance of the research?
Describe the new perspectives opened by the results achieved, including the scientific basics of potential societal applications. Please describe the unique strengths of your proposal in comparison to your domestic and international competitors in the given field.
In informatics, automata and generative grammars are widely used in the
description, design and analysis of increasingly more complicated
systems, in the validation and verification of the systems' properties
with respect to the specification requirements. They are important tools
in the processing of both artificial and natural languages, to mention
a few applications.

The planned research contributes to the development of the
theoretical basis of these methods in order to make them
applicable for new challenges.

Summary and aims of the research for the public
Describe here the major aims of the research for an audience with average background information. This summary is especially important for NRDI Office in order to inform decision-makers, media, and others.
Finite automata and generative grammars were introduced
about 50 years ago. They have been widely used in the design
and analysis of circuits, hardware and software systems,
they serve as models of neural systems, and they are
important tools in the processing of artificial and natural languages,
to mention only a few of their applications.


The increasing size, complexity and safe operation
of the systems requires the introduction and
development of new methods and models. The aim of the research is
to develop the mathematical theory of such methods
and models in the light of the new challenges.




 

Final report

  
Results in Hungarian
Az automaták és formális nyelvek területen vizsgált számítási modellek kiterjesztéseivel foglalkoztunk. Számottevő eredményeket értünk el az alábbi területeken: formális hatványsorok (5 dolgozat), Kleene algebrák energia problémákra (2 dolgozat), véges automaták kísérő félcsoportjai (2 dolgozat), környezetfüggetlen nyelvek általánosításai (4 dolgozat), fatranszformátorok és súlyozott fatranszformátorok (3 dolgozat), faautomaták és súlyozott faautomaták (6 dolgozat), klasszikus formális nyelvek elmélete (2 dolgozat), termátíró rendszerek (2 dolgozat), megfordítható nyelvek (2 dolgozat), és egyéb vegyes eredmények (4 dolgozat). Összesen 32 publikációnk jelent meg vagy van megjelenés alatt nemzetközi fórumokon, melyek közül 21 folyóiratcikk. A folyóiratcikkek összesített impakt faktora 10.526.
Results in English
We made research on extensions of computation models in the theory of automata and formal langauges. We achieved results in the folowing topics: formal power series (5 papers), Kleene algebras for energy problems (2 papers), semigroups associated to finite automata (2 papers), generalizations of context-free langauges (4 papers), tree transducers and weighted tree transducers (3 papers), tree automata and weighted tree automata (6 papers), classical theory of formal languages (2 papers), term rewriting systems (2 papers), reversible languages (2 papers), miscellaneous related areas (4 papers). Altogether we published 32 scientific papers, out of which 21 appeared or is accepted in journals. The sum of the impact factor of the jurnal papers is 10.526.
Full text https://www.otka-palyazat.hu/download.php?type=zarobeszamolo&projektid=108448
Decision
Yes





 

List of publications

  
Z. Fülöp, Z. Gazdag: Weighted Languages Recognizable by Weighted Tree Automata, Acta Cybernetica, 23(3) pp 867-886., 2018
Z. Fülöp, L. Herrmann, H. Vogler: Weighted Regular Tree Grammars with Storage, Discrete Mathematics & Theoretical Computer Science, 21(1) pp.1-44., 2018
Z. Fülöp, H. Vogler: Characterizations of Recognizable Weighted Tree Langauges by Logic and Bimorphism, Soft Computing, 22 pp 1035-1046., 2018
Z. Fülöp, H. Vogler: Weighted Iterated Linear Control, Acta Informatica, to appear., 2019
Z. Fülöp, A. Maletti: Composition Closure of Linear Weighted Extended Top-down Tree Transducers, submitted., 2019
K. Gelle, S. Iván: DFS is Unsparsable and Lookahead Can Help in Maximal Matching, Acta Cybernetica, 23(3) pp. 887-902., 2018
K. Gelle, S. Iván: Recognizing Union-Find trees is NP-complete, even without Rank Info, International Journal on Foundations of Computer Science, to appear., 2019
K. Gelle, S. Iván: More on reversible languages having finitely many reduced reversible automata, International Journal on Foundations of Comnputer Science, to appear., 2019
S. Vágvölgyi: Descendants of a recognizable tree langauge for prefix constrained linear monadic term rewriting with position cutting strategy, Theoretical Computer Science, 732 pp. 60-72., 2018
S. Vágvölgyi: Intersection of the reflexive, transitive closures of two rewrite relations induced by term rewriting systems, Information Processing Letters, 134 pp. 47-51., 2018
Z. Fulop: Local Weighted Tree Languages, Acta Cybernetica, 22, 393-402, 2015
Z. Esik, S. Ivan: Operational characterization of scattered MCFLs, International Journal of Foundations of Computer Science 25(8): 1001-1016, 2014
Z, Esik, U. Fahrenberg, A. Legay: *-Continuous Kleene omega-algebras, 19th International Conference on Developments in Language Theory, DLT 2015. Liverpool, LECTURE NOTES IN COMPUTER SCIENCE 9168: pp. 240-251, 2015
Z. Esik, U. Fahrenberg, A. Legay: *-Continuous Kleene ω-Algebras for Energy Problems, Fixed Points in Computer Science, Berlin, Electronic Proceedings in Theoretical Computer Sience, vol. 191, 48-59., 2015
S. Iván, J. Nagy György: On nonpermutational transformation semigroups with an application to syntactic complexity, Acta Cybernetica 22(3): 687-701., 2016
S. Iván: Complexity of atoms, combinatorially, Information Processing Letters 116(5): 356-360., 2016
Z. Ésik, S. Iván: MSO-definable Properties of Muller Context-free Languages, Lecture Notes in Computer Science, Vol. 9777, pp. 87-97, 2016
Z. Fülöp, M. Droste, D. Götze: A Kleene Theorem for Weighted Tree Automata over Tree Valuation Monoids, Lecture Notes in Computer Science, Vol. 9618, pp. 452-463., 2016
Z. Fülöp, A. Maletti: Linking Theorems for Tree Transducers, Journal of Computer and Systems Sciences 82 (2016) 1201-1222., 2016
Z. Fülöp: Weighted Tree Automata and their Characterization by Logic, Proc. of NCMA 2016, books@ocg.at, 321, Österreiche Computer Gesellschaft, 2016
Z. Fülöp, S. Vágvölgyi: Minimization of Deterministic Top-down Tree Automata, Acta Cybernetica 23 (2017) 379-401., 2017
J. Engelfriet, Z. Fülöp, and A. Maletti: Composition Closure of Linear Extended Top-down Tree Transducers, Theory of Computing Systems, 60 (2017) 129-171., 2017
Kitti Gelle, Szabolcs Iván: Recognizing Union-Find trees is NP-complete., Inf. Process. Lett. 131 (2018) 7-14., 2018
Kitti Gelle, Szabolcs Iván: Regular Expressions for Muller Context-Free Languages., Acta Cybern. 23(1): 349-369., 2017
Kitti Gelle, Szabolcs Iván: Recognizing Union-Find Trees Built Up Using Union-By-Rank Strategy is NP-Complete., Proc. of the 19th Descriptional Complexity of Formal Systems, DCFS 2017, LNCS 10316, p. 152-163., 2017
Kitti Gelle, Szabolcs Iván: Reversible languages having finitely many reduced automata., Proc. of the 15th International Conference on Automata and Formal Languages, AFL 2017, EPTCS 252, 114-127., 2017
Z. Gazdag and K. Tichler: On the power of permitting semi-conditional grammars., Developments in Language Theory: 21st International Conference, DLT 2017, LNCS 10396, (Springer, Cham, 2017), pp. 173–184., 2017
Dmitry Chistikov, Szabolcs Iván, Anna Lubiw, Jeffrey Shallit: ractional Coverings, Greedy Coverings, and Rectifier Networks., STACS 2017: 23:1-23:14., 2017
M. Droste, Z. Esik, W. Kuich: Conway and iteration hemirings Part 1, Int. J. Algebra and Computation 24:(4) pp. 461-48, 2014
M. Droste, Z. Esik, W. Kuich: Conway and iteration hemirings Part 2, Int. J. Algebra and Computation 24:(4) pp. 483-513, 2014
Z. Esik, T. Hajgato: On the structure of free iteration semirings, J. Automata, Languages and Combinatorics, vol. 19, 57-66., 2014
E. Csuhaj-Varju, M. Dietzfelbinger, Z. Esik: Mathematical Foundations of Computer Science, Vol. 1, LNCS 8634, Springer, 2014
E. Csuhaj-Varju, M. Dietzfelbinger, Z. Esik: Mathematical Foundations of Computer Science, Vol. 2, LNCS 835, Springer, 2014
Z. Esik, Z. Fulop: 14th International Conference on Automata and Formal Languages, Electronic Proceedings in Theoretical Computer Science, vol. 151, 2014
Z. Esik, W. Kuich: On Power Series over a Graded Monoid, Computing with New Resources, Lecture Notes in Computer Science, Vol. 8808, 49-55., 2014




 

Events of the project

  
2023-08-07 09:10:36
Kutatóhely váltás
A kutatás helye megváltozott. Korábbi kutatóhely: Informatikai Intézet (Szegedi Tudományegyetem), Új kutatóhely: Számítástudomány Alapjai Tanszék (Szegedi Tudományegyetem).
2018-02-21 10:03:01
Résztvevők változása
2016-10-05 13:54:16
Résztvevők változása
2016-08-17 13:35:34
Vezető kutató váltás
Régi vezető kutató: Ésik Zoltán
Új vezető kutató: Fülöp Zoltán

A vezető kutató váltás indoka: Dr. Ésik Zoltán 2016.05.25-én elhunyt.



Back »