Automata, trees and logic  Page description

Help  Print 
Back »
 

Details of project

  
Identifier
46686
Type K
Principal investigator Fülöp, Zoltán
Title in Hungarian Automaták, fák és logika
Title in English Automata, trees and logic
Panel Mathematics and Computing Science
Department or equivalent Department of Foundations of Computer Science (University of Szeged)
Participants Ésik, Zoltán
Gazdag, Zsolt Zoltán
Vágvölgyi, Sándor Árpád
Starting date 2004-01-01
Closing date 2008-12-31
Funding (in million HUF) 8.912
FTE (full time equivalent) 0.00
state closed project





 

Final report

  
Results in Hungarian
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.
Results in English
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.
Full text http://real.mtak.hu/1536/
Decision
Yes





 

List of publications

  
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




 

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



Back »