Automaták, fák és logika  részletek

súgó  nyomtatás 
vissza »
 

Projekt adatai

  
azonosító
46686
típus K
Vezető kutató Fülöp Zoltán
magyar cím Automaták, fák és logika
Angol cím Automata, trees and logic
zsűri Matematika–Számítástudomány
Kutatóhely Számítástudomány Alapjai Tanszék (Szegedi Tudományegyetem)
résztvevők Ésik Zoltán
Gazdag Zsolt Zoltán
Vágvölgyi Sándor Árpád
projekt kezdete 2004-01-01
projekt vége 2008-12-31
aktuális összeg (MFt) 8.912
FTE (kutatóév egyenérték) 0.00
állapot lezárult projekt





 

Zárójelentés

  
kutatási eredmények (magyarul)
Elemi idejű exponenciális algoritmus adtunk meg reguláris szavak ekvivalenciájának eldönthetőségére. Általánosítottuk Kleene tételét végtelen szavakat is felismerő súlyozott automatákra. Kifejlesztettünk egy algebrai módszert, amellyel a CTL logika számos szegmense estén eldönthető, hogy egy reguláris fanyelv definiálható-e a szegmensben. Vizsgáltuk a faautomaták algebrai tulajdonságait, megadtuk a felismerhetőség egy algebrai jellemzését. Definiáltunk a multi-leszálló fatranszformátort és megmutattuk, hogy ekvivalens a determinisztikus reguláris szűkítésű felszálló fatranszformátorral. Meghatároztuk a lineáris multi-leszálló osztály számítási erejét. Megmutattuk, hogy az alakmegőrző leszálló fatranszformátorok ekvivalensek az átcímkézőkkel és bebizonyítottuk, hogy az alakmegőrző tulajdonság eldönthető. Megadtuk a kavics makró fatranszformációk egy felbontását és megmutattuk, hogy a különböző cirkularitási tulajdonságok eldönthetők. Ugyancsak megadtuk a felbontást erős kavics kezelés estén is. Általánosítottuk J. Engelfriet hiararchia tételét súlyozott fatranszformátorokra. Súlyozott faautomatákra definiáltuk a termátíró szemantikát és megmutattuk, hogy ekvivalens az algebari szenmatikával. Algoritmust adtunk annak eldöntésére, hogy egy polinomiálisan súlyozott faautomata véges költségű-e. Vizsgáltuk a súlyozott faautomata különböző változatait: fuzzy faautomata, multioperátor monoid feletti faautomata, Ez utóbbi esetre általánosítottuk a Kleene tételt.
kutatási eredmények (angolul)
We gave an elementary algorithm for deciding the equivalence of regular words. We generalized Kleene’s theorem to weighted automata processing infinite words. We developed an algebraic method that, for several segments of the CTL logic, can be applied to decide if a regular tree language can be defined in that segment. We examined algebraic properties of tree automata, and gave an algebraic characterization of recognizability. We defined multi bottom-up tree transducers and showed that they are equivalent to top-down tree transducers with regular look-ahead. We determined the computation power of the linear subclass. We showed that shape preserving bottom-up tree transducers are equivalent to relabelings. We proved that the shape preserving property is decidable. We gave a decomposition for pebble macro tree transducers and showed that certain circularity properties are decidable. We also gave a decomposition for the strong pebble handling. We have generalized the hierarchy theorem of J. Engelfriet to weighted tree transducers. We defined the term rewrite semantics of weighted tree transducers and showed that it is equivalent to the algebraic semantics. We gave a decision algorithm for the finite cost property of a polynomially weighted tree automata. We defined different versions of weighted tree automata: fuzzy tree automata, weighted tree automata over a multioperator monoid. For the latter we generalized Kleene’s theorem.
a zárójelentés teljes szövege http://real.mtak.hu/1536/
döntés eredménye
igen





 

Közleményjegyzék

  
Fülöp Z.; Vogler, H.: Weighted Tree Transducers, J. of Automata, Languages and Combinatorics, 9: 31-54., 2004
Ésik Z.: An algebraic characterization of the expressive power of temporal logics on finite trees, Part 1, Proc. of the 1st Conference on Algebraic Informatics (October 20-23 2005, Thessaloniki) , 53-78., 2005
Fülöp Z., Muzamel L.: Recent Results on Pebble Macro Tree Transducers, Proc. of the 1st Conference on Algebraic Informatics (October 20-23 2005, Thessaloniki), 281-284., 2005
Ésik Z.: An algebraic characterization of the expressive power of temporal logics on finite trees, Part 2, Proc. of the 1st Conference on Algebraic Informatics (October 20-23 2005, Thessaloniki) , 70-100., 2005
Ésik Z.: An algebraic characterization of the expressive power of temporal logics on finite trees, Part 3, Proc. of the 1st Conference on Algebraic Informatics (October 20-23 2005, Thessaloniki) , 101-110., 2005
Ésik Z. and G. Martin: A note on Wolper's logic, Proc. of the ICALP Workshop on Semigroups and Automata (Lisboa, 2005), 61-68., 2005
Fülöp Z.; Kühnemann, A.; Vogler, H.: Linear deterministic multi bottom-up tree transducers, Theoret. Comput. Sci. 347: 276-287., 2005
Fülöp Z.; Vogler, H.: A Comparison of Several Models of Weighted Tree Automata, Technical report, Technical Univ. of Dresden, Faculty of Computer Science, 2006
Ésik Z.; Kuich, W.: A semiring-semimodule generalization of $\omega$-regular languages, I., J. of Automata, Languages, and Combinatorics, 10: 203-242., 2005
Ésik Z.; Kuich, W.: A semiring-semimodule generalization of $\omega$-regular languages, II., J. of Automata, Languages, and Combinatorics, 10: 243-264., 2005
Gazdag Zs.: Decidability of the Shape Preserving Property of Bottom-up Tree Transduecrs, International Journal of Foundations of Computer Science 17: 395-413., 2006
Fülöp Z.: An Introduction to Tree Transducers, Formal Methods in Computing (Eds. M. Ferenczi, A. Pataricza and L. Rónyai), Akadémiai Kiadó, Budapest, 2005, 199-258., 2005
Ésik Z., L. Guangwu: Fuzzy tree automata, Fuzzy Sets and Systems, 158: 1450-1460., 2007
Ésik Z.,: Fuzzy boolean sets, Int. J. Foundations of Computer Science, 18: 1197-1207., 2007
Fülöp Z., Muzamel L.: Circularity, Composition, and Decomposition Results for Pebble Macro Tree Transducers, J. Automata, Languages and Combinatorics, közlésre elfogadva., 2007
Fülöp Z., A. Maletti, and H. Vogler: A Kleene Theorem for Weighted Tree Automata over Distributive Multioperator Monoids, Theory of Computing Systems, közlésre elfogadva., 2007
Bloom, S. L.; Ésik Z.: The equational theory of regular words, Information and Computation, 197: 55-89., 2004
Fülöp Z.; Gazdag Zs.; Vogler, H.: Hierarchies of tree series tree transformations, Theoret. Comput. Sci. 314: 387-429., 2004
Fülöp Z.; Kühnemann, A.; Vogler, H.: A bottom-up characterization of deterministic top-down tree transducers with regular look-ahead, Inf. Process. Letters 90: 57-67., 2004
B. Borchardt, Z. Fülöp, Zs. gazdag, A. Maletti: Bounds for Tree Automata with Costs, J. of Automata, Languages and Combinatorics, 10: 2005, 107-157., 2005
Ésik Z.; Weil, P.: Algebraic recognizability of regular tree languages, Theoret. Comput. Sci. 340: 291-321., 2005
Gazdag Zs.: Shape Preserving Bottom-Up Tree Transducers, Journal of Automata, Languages and Combinatorics, 10 : 483--534., 2005
Ésik Z.: Characterizing CTL-like Logics on Finite Trees, Theoret. Comput. Sci., 356: 136-152., 2006
Vágvölgyi S.: Descendants of a recognizable tree language for sets of linear monadic term rewrite rules, Inf. Process. Letters 99: 111-118., 2006
Ésik Z., Iván Sz.,: Aperiodicity in tree automata, Proc. of CAI 2007, LNCS 4728, Springer, 2007, 189-207., 2007
Ésik Z., W. Kuich: On iteration semiring-semimodule pairs, Semigroup Forum, 75: 129-159., 2007




 

Projekt eseményei

  
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).



vissza »