Automata, fixed points, and logic  Page description

Help  Print 
Back »
 

Details of project

  
Identifier
75249
Type K
Principal investigator Ésik, Zoltán
Title in Hungarian Automaták , fixpontok, es logika
Title in English Automata, fixed points, and logic
Keywords in Hungarian automata, fomális nyelv, fixpont, logika
Keywords in English automata, formal language, fixed point, logic
Discipline
Computing Science (Council of Physical Sciences)50 %
Mathematics (Council of Physical Sciences)50 %
Ortelius classification: Computational models
Panel Mathematics and Computing Science
Department or equivalent Institute of Informatics (University of Szeged)
Participants Iván, Szabolcs
Starting date 2008-10-01
Closing date 2012-10-31
Funding (in million HUF) 6.000
FTE (full time equivalent) 5.20
state closed project
Summary in Hungarian
Az automaták és nyelvek elméletében számos eredmény csak a fixpont művelet néhány tulajdonságán múlik. Ilyen eredmény Kleene nevezetes tétele is, amely a véges automatákkal felismerhető nyelvek és a reguláris nyelvek ekvivalenciáját mondja ki. A projekt egyik célja a fixpontok elméletének továbbfejleszté és alkalmazása az automatákra. A vizsgálatok eredménye képpen az automaták és nyelvek axiomatikus tárgyalását kapjuk a véges és végtelen szavak, fák és formális hatványsorok felett, valamint különböző
biszimulációs szemantikákra.


A véges szavakból álló reguláris nyelvek osztályozásában fontos szerepet töltött be a nyelv varietás fogalma és az ún. Eilenberg-féle megfelelkezés. Az Eilenberg-féle megfelekezés egy-egy értelmű kapcsolatot létesít a nyelv varietások és bizonyos véges algebrai struktúrák ún. pszeudo-varietásai között. Az automaták és formális nyelvek elméletének számos mély eredménye a nyelv varietásokra és az ezekhez tartozó pszeudo-varietásokra vonatkozik. Az utóbbi időben a nyelv varietás fogalmát általánosították fákra, amelyekből álló nyelveket a konkurens rendszerek viselkedésének leírására is felhasználják. Számos programozási logikát vezettek be ilyen nyelvek specifikálására, azonban viszonylag kevés esetben sikerült a logikák kifejező erejét kielégítően jellemezni. A legtöbb bevezetésre került logika fanyelvek egy varietását határozza meg, ezért kifejező erejük meghatározása ekvivalens a megfelelő pszeudo-varietások jellemzésével. Amennyiben ez a pszeudo-varietás algoritmikusan eldönthető, a logika kifejező erejének algoritmikus leírását kapjuk. A pályázatban vizsgálni kívánjuk a fák nyelv varietásait, ill. az ezeknek megfelelő pszeudo-varietásokat a logiával kapcsolatban, és attól függetlenül is.
Summary
Several theorems in the theory of automata and languages only depend on a few equational properties of fixed point operations. This has been shown, for example, for the classical Kleene theorem equating the class of regular languages with the class of recognizable languages. One objective of the proposed research is to further develop and apply the general theory of fixed points in connection with automata so as to provide an axiomatic foundation to the theory of automata and languages over finite and infinite words, trees, and formal series, and various bisimulation based semantics of transition systems.

Language varieties and the Eilenberg correspondence have played an important role in the classification of regular languages. The Eilenberg correspondence establishes a bijection between language varieties and pseudo-varieties of certain finite algebraic structures. Many deep results of the theory of automata and languages are concerned with language varieties and their corresponding pseudo-varieties. Recently, variety theory has been extended to trees which are frequently used to describe the behavior of concurrent systems. Several programming logics have been introduced for the specification of tree languages. However, a satisfactory (algorithmic) characterization has been obtained only in a few cases. Since most of these logics determine tree language varieties, the characterization of their expressive power is equivalent to the characterization of the corresponding pseudo-variety. If this pseudo-variety is decidable, there results an effective characterization of the logic. We plan to study varieties of tree languages both in connection with logic and independently.




 

Final report

  
Results in Hungarian
Megmutattuk, hogy a véges automaták (faautomaták, súlyozott automaták, stb.) viselkedése végesen leírható a fixpont művelet általános tulajdonságainak felhasználásával. Teljes axiomatizálást adtunk a véges automaták viselkedését leíró racionális hatványsorokra és fasorokra, ill. a véges automaták biszimuláció alapú viselkedésére. Megmutattuk, hogy az automaták elméletének alapvető Kleene tétele és általánosításai a fixpont művelet azonosságainak következménye. Algebrai eszközökkel vizsgáltuk az elágazó idejű temporális logikák és a monadikus másodrendű logika frágmenseinek kifejező erejét fákon. Fő eredményünk egy olyan kölcsönösen egyértelmű kapcsolat kimutatása, amely ezen logikák kifejező erejének vizsgálatát visszavezeti véges algebrák és preklónok bizonyos pszeudovarietásainak vizsgálatára. Jellemeztük a reguláris és környezetfüggetlen nyelvek lexikografikus rendezéseit, végtelen szavakra általánosítottuk a környezetfüggetlen nyelv fogalmát, és tisztáztuk ezek számos algoritmikus tulajdonságát.
Results in English
We have proved that the the bahavior of finite automata (tree automata, weighted automata, etc.) has a finite description with respect to the general properties of fixed point operations. We have obtained complete axiomatizations of rational power series and tree series, and the bisimulation based behavior of finite automata. As an intermediate step of the completeness proofs, we have shown that Kleene's fundamental theorem and its generalizations follow from the equational properties of fixed point operations. We have developed an algebraic framework for describing the expressive power of branching time temporal logics and fragments of monadic second-order logic on trees. Our main results establish a bijective correspondence between these logics and certain pseudo-varieties of finite algebras and/or finitary preclones. We have characterized the lexicographic orderings of the regular and context-free languages and generalized the notion of context-free languages to infinite words and established several of their algorithmic properties.
Full text https://www.otka-palyazat.hu/download.php?type=zarobeszamolo&projektid=75249
Decision
Yes





 

List of publications

  
S.L. Bloom, Z. Esik, W. Kuich: Cycle-free finite automata in partial iterative semirings, Algebraic Informatics (Eds. S. Bozapalidis, G. Rahonis,), LNCS 5725, Springer, 2009, 1--12, 2009
Z. Esik, T. Hajgato: Iteration grove theories with applications, Algebraic Informatics (Eds. S. Bozapalidis, G. Rahonis), LNCS 5725, Springer, 227--249, 2009
Z. Esik, Sz. Ivan: Context-free languages of countable words, Int. Conf. Theoretical Aspects of Computing, LNCS 5684, Springer, 185--199, 2009
S.L. Bloom, Z. Esik: Axiomatizing rational power series over natural numbers, Information and Computation, 207(2009), 793-811, 2009
Z. Esik, Z. Fulop: Automata, Formal Languages, and Related Topics, Dedicated to Ferenc Gécseg on the occasion of his 70th birthday, Inst. of Informatics, University of Szeged, ISBN 978-963-482-916-4, 2009
Zs. Gazdag, Sz. Ivan, J. Nagy-György: Improved upper bounds on synchronizing nondeterministic auttomata, Information Processing Letters, 109(17): 986-990, 2009
Z. Esik, R. Ramanujam: Selected Papers of the Conference "Computer Science Logic 2006" Szeged, Hungary, 2006, Logical Methods in Computer Science, 2009
S.L. Bloom, Z. Esik: Scattered algebraic linear orderings, 6th Workshop on Fixed Points in Computer Science, Coimbra, 2009 (Eds.: R. Matthes and T. Uustalu), Institute of Cybernetics at Tallinn, 25--29, 2009
S.L. Bloom, Z. Esik: Algebraic ordinals, Fundamenta Informaticae, 99(2010), 383--407, 2010
S.L. Bloom, Z. Esik: A Mezei-Wright theorem for categorical algebras, Theoretical Computer Science, 411(2010) 341--359, 2010
Z. Esik, Sz. Ivan: A family of temporal logics on finite trees, Publ. Math. (Debrecen), 77/3-4 (2010), 277--297, 2010
Z. Esik, P. Weil: Algebraic characterization of logically defined tree languages, Int. J. Algebra and Computation, 20(2010), 195--239, 2010
Z. Esik, Y. Gao, G. Liu, S. Yu: Estimation of state complexity of combined operations, Theoret. Comput. Sci., 410(2009), 3272--3281, 2009
E. Csuhaj-Varju, Z. Esik: Automata and Formal Languges (spec. issue), Int. J. Foundations of Computer Science, Volume 21, Number 5, 2010
E. Csuhaj-Varju, Z. Esik: Automata and Formal Languges, AFL 08 (special issue), Acta Cybernetica, Vol. 19, No. 2, 441--565, 2010
Z. Esik: Fixed Point Theory, Handbook of Weighted Automata, Springer, 2009, 29--65, 2009
Z. Esik, W. Kuich: Finite Automata, Handbook of Weighted Automata, Springer, 2009, 69--104, 2009
Z. Esik: Representing small ordinals by finite automata, Proc. Descriptional Complexity of Formal Systems, Saskatoon, Canada, 2010, EPTCS, vol. 31, 78--87, 2010
Z. Esik: Simulations of weighted tree automata, Implementaion and Application of Automata, Winnipeg, Canada, 2010, LNCS 6482, Springer, 2011, 321–330., 2011
Z. Esik, Sz. Ivan: On Muller context-free grammars, Developments in Language Theory, London, ON, 2010, LNCS, Volume 6224, Springer, 173-184, 2010
Z. Esik, A. Maletti: Simulation vs. equivalence, 6th Int. Conf. Foundations of Computer Science, FCS 2010,Las Vegas, Nevada, CSREA Press, 119--122., 2010
Z. Esik: Axiomatizing the Equational Theory of Regular Tree Languages, J. Logic and Algebraic Programming, 79(2010), 189--213, 2010
Z. Esik, T. Hajgato: Dagger extension theorem, Math. Struc. in Comp. Sci., 21(2011), 1036–1066, 2011
Z. Esik: An undecidable property of context-free linear orders, Information Processing Letters, 111(2011), pp. 107-109., 2011
Z. Esik, S. Ivan: Buchi context-free languages, Theoretical Computer Science, 412(2011), 805–821, 2011
S.L. Bloom, Z. Esik: Algebraic linear orderings, Int. J. Foundations of Computer Science, 22(2011), 491– 515, 2011
Z. Esik: Residuated Park theories, Topology, Algebra, and Categories in Logic, TACL 2011, Marseille, 2011, 37–40., 2011
Z. Esik, W. Kuich: Axiomatizing rational series, Panhellenic Logic Symposium, Ioannina, 2011, 30–34, 2011
Z. Esik: Scattered context-free linear orderings, Proc. Developments in Language Theory, Milan, 2011, LNCS 6795, Springer-Verlag, 2011, 216–227., 2011
Z. Esik: Multi-linear iterative K-semialgebras, Proc. 27th Int. Conference on Mathematical Foundations of Programming Semantics, Carnegie Mellon University, May 2011, ENTCS, 276, 159--170., 2011
Z. Esik, S. Ivan: Extended temporal logics on finite trees, Automata, Formal Languages, and Algebraic Systems, World Scientific, 2010, 47-62, 2010
Z. Esik, M. Ito, W. Kuich,: Linear languages of finite and infinite words, Automata, Formal Languages, and Algebraic Systems, World Scientific, 2010, 33–46., 2010
S. Ivan, A.Meszaros: Muller context-free grammars generating well-ordered words, Automata and Formal Languages, AFL 2011, Debrecen, Hungary, 225--240., 2011
Z. Esik, W. Kuich: A unifying Kleene theorem for weighted finite automata, C.S. Calude, G. Rozenberg, A. Salomaa (Eds.): Maurer Festschrift, LNCS 6570, pp. 76–89, 2011
Z. Esik, K. Sutner: Stephen. L. Bloom, 1940–2010, Fundamenta Informaticae, 109(2011), 369–381, 2011
Z. Esik: Equational theories for automata, Handbook of Automata, Eds.: J.-E. Pin, W. Thomas, EMS, to appear, 2011
Z. Esik, S. Ivan,: On Muller context-free grammars, Theoretical Computer Science, 416(2012), 17--32., 2012
Z. Esik: Ordinal automata and Cantor normal form, INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE 23:(1) pp. 87-98., 2012
Z. Esik, S. Okawa: On context-free languages of scattered words, Developments in Language Theory - 16th International Conference, DLT 2012: LNCS 7410, Springer, 2012, 142-153., 2012
Z. Esik, S. Ivan: Hausdorff Rank of Scattered Context-free Linear Orders, LATIN 2012: Theoretical Informatics - 10th Latin American Symposium, LNCS 7256, Springer, 2012, 291-302., 2012
Z. Esik, W. Kuich: Free iterative and iteration K-semialgebras, ALGEBRA UNIVERSALIS 67:(2) pp. 141-162. (2012), 2012
L. Aceto, A. Carayol, Z. Esik, A.Ingolfsdottir: Algebraic synchronization trees and processes, Automata, Languages, and Programming - 39th International Colloquium, ICALP 2012, LNCS 7392, Springer, 30–41., 2012
Z. Esik, D.Miller: Fixed Points in Computer Science, Proceedings 8th Workshop, FICS 2012, Tallinn, Estonia, Electronic Proceedings in Theoretical Computer Science (EPTCS), vol. 77, 2012
A. Carayol, Z. Esik: A context-free linear ordering with an undecidable first-order theory, Theoretical Computer Science - 7th IFIP International Conference, TCS 2012: LNCS 7604, Springer, 2012, 104-118., 2012
Z. Esik: Partial Conway and Iteration Semiring-Semimodule Pairs, G. Rahonis, W.Kuich, Eds., Algebraic Foundations in Computer Science, Springer, 2011., pp. 56-71., 2011
Z. Esik, T. Hajgato,: Kleene Theorem in Partial Conway Theories with Applications, W. Kuich. G.Rahonis, Eds., Algebraic Foundations in Computer Science, Springer Verlag, 2011. pp. 72-93., 2011
Z. Esik, W. Kuich: Free inductive K-semialgebras, arXiv:1009.4820v2, 2010
Z. Esik, A.Maletti: The category of simulations for weighted tree automata, Int. J. Foundations of Computer Science, 22(2011), 1845--1859, 2011
P. Domosi, Z. Esik: Special Issue -- Automata and Formal Languages (AFL 2011), International J. Foundations of Computer Science, Vol. 23, No. 6, 2012



Back »