Abstract Automata and Formal Languages  Page description

Help  Print 
Back »
 

Details of project

  
Identifier
49409
Type K
Principal investigator Dömösi, Pál Béla
Title in Hungarian Absztrakt automaták és formális nyelvek
Title in English Abstract Automata and Formal Languages
Panel Mathematics and Computing Science
Department or equivalent Department of Computer Science (University of Debrecen)
Participants Battyányi, Péter
Csáki, Tibor
Egri-Nagy, Attila
Fazekas, Szilárd Zsolt
Horváth, Géza
Kovásznai, Gergely
Nagy, Benedek
Starting date 2005-01-01
Closing date 2009-12-31
Funding (in million HUF) 7.800
FTE (full time equivalent) 23.00
state closed project





 

Final report

  
Results in Hungarian
Monográfiában foglaltuk össze a véges automata hálózatok elméletének alapvető eredményeit . Megadtuk a Leticsevszkij kritérium nélküli automata-hálózatok egy új jellemzését. Megadtunk bizonyos szimbólum osztályokkal ellátott többszalagos automatákat. Megadtuk és vizsgáltuk a kutatásaink során felfedezett automataelméleti elvű új titkosítási rendszert. Új bizonyítást adtunk a Lyndon-Schützenberger tételre és a Shyr-Yu tételre. Általánosítottuk a szavak primitivitásának, illetve periodicitásának fogalmát, s megadtuk, hogy melyek azok a Marcus nyelvtanok, amelyek az adott típusú szavakból álló nyelveket képesek generálni. Sikerült találni egy iterációs lemmát azon környezetfüggetlen nyelvekre, melyek nem lineárisak. A contextuális sztringnyelvek általánosításaként bevezettük és vizsgáltuk a hypergráf contextuális nyelvek és nyelvtanok fogalmát. Automaták segítségével jellemeztük az uniómentes nyelveket. Leírtuk a különféle logikai kalkulusok és valamely levezetési rendszer szabályai szerint megadott levezetések kapcsolatait, s a különféle kalkulusok normalizálhatósági tulajdonságait. Új elvű számítási kutatásainkban az intervallum-értékű számításokat, mint új számítási modellt írtuk le. Digitális geometriai kutatásainkban digitális távolság alapján értelmezett szakaszokat, köröket, hiperbolákat és parabolákat vizsgáltunk.
Results in English
We summarized in monograph the fundamental results of theory of finite automata networks. We gave a new characterization of automata-networks having no Letichevsky criteria. We gave multi-tape automata supplied by certain symbol classes. We gave and investigated a novel cryptosystem based on automata theory discovered during our research.. We gave a new proof of Lyndon-Schützenberger Theorem and Shyr-Yu Theorem. We generalized the concept of primitivity and periodicity of words and we give the Marcus gramars which are able to generate languages consisting of given type words. It succeed in finding an iteration lemma for non-linear context-free languages. As a generalization of contextual string languages, we introduced and investigated the concept of hypergraph contextual grammars and languages. We characterized the union-free languages by automata. We described the connections of derivations given by various logical calculi and certain derivation system, moreover the normalizable properties of various calculi. In our new computation principle researches we described the intervallum-value computations as new computation model In our digital geometric researches we investigated the sessions,circles,hyperbolas and parabolas defined by a digital distance .
Full text http://real.mtak.hu/1969/
Decision
Yes





 

List of publications

  
Nagy, Benedek & Vályi, Sándor: Visual reasoning by generalized interval-values and, Workshop on Visual Languages and Logic, - VL/HCC 07, IEEE Symposium, 2007
Nagy, Benedek & Dediu, Adrian-Horia: Self-assembling tilings of Boolean tree-like circuits modeled by contextual, etc., NSIP2007, IEEE, Bucharest, 150-153., 2007
Nagy, Benedek; Dediu, Adrian-Horia: Computing Trees with Contextual Hypergraph, ForLing2007-FCT2007, Budapest, Hungary, 39-53., 2007
Battyányi, Péter: Normalization properties of symmetric logical calculi, Université de Savoie, Chambéry, 2007
Dömösi, Pál; Horváth, Géza: On products of primitive words, Automata and formal languages, 112--121, Univ. Szeged. Inst. Inform., Szeged, 2005
Dömösi, Pál; Horváth, Géza: The language of primitive words is not regular: two simple proofs, Bull. Eur. Assoc. Theor. Comput. Sci. EATCS No. 87, 191--197, 2005
Dömösi, Pál: Automata Networks without any Letichevsky Criteria, Kiadvány Gécseg Ferenc akadémikus 70. születésnapja alkalmából, Univ. Szeged. Inst. Inform., Szeged, 2009
Dömösi, Pál;Horváth, Géza;Vuillon, Laurent: On the Shyr-Yu Theorem, Theoret. Comput. Sci., közlésre elfogadva, 2009
Dömösi, Pál: A Novel Stream Cipher Based on Finite Automata without Outputs, AFLAS 2008, International Workshop on Automata, Formal Languages and Algebraic Systems, megjelenés alatt, 2009
Kudlek,Manfred; Nagy,Benedek: On Distances of Languages, Pure Mathematics and Applications - PU.M.A. 17 (2006), 349-357, 2006
Szilárd Fazekas and Benedek Nagy: Scattered subword complexity of non-primitive words, Journal of Automata, Languages and Combinatorics - JALC, közlésre elfogadva, 2009
Melkó,Ervin; Nagy,Benedek: Optimal strategy in games with chance nodes, Acta Cybernetica, 18/2, 171-192, 2007
Nagy,Benedek: On 5'->3' sensing Watson-Crick finite automata, DNA 13, Lecture Notes in Computer Science - LNCS 4848, 256-262, 2008
Horváth,Géza: New Pumping Lemma for Non-Linear Context-Free Languages, Proceedings of the 9th Symposium on Algebras, Languages and Computation, Shimane University, 160-163, 2006
Nagy,Benedek;Orosz, Ágota: Simple digital objects on Z^2, ICAI 2007, 7th International Conference on Applied Informatics, Eger, Hungary, volume I. 139-146, 2007
Nicart,F.;Champarnaud,J.-M.;Csáki,T.;Gaál,T.; Kempe,A.: Multi-tape Automata with Symbol Classes, Proc. IAA'2006, LNCS 4004, 126-136, 2006
Strand, R.;Nagy, B.;Fouard, C.; Borgefors,G.: Generating Distance Maps with Neighbourhood Sequences, DGCI 2006, Szeged, Hungary, LNCS 4245, 295-307, 2006
Nagy, Benedek: Geometry of neighborhood sequences in hexagonal grid, DGCI 2006, Szeged, Hungary, LNCS 4245, 53-64, 2006
Barbaiani, M.;Bibire, C.;Dassow, J.;Delaney, A.;Fazekas, Sz;Ionescu, M.;Liu, G;Lodhi,A; Nagy,B.: The power of programmed grammars with graphs from various classes, JAMC 22, 21-38, 2006
Egri-Nagy,Attila;Nehaniv,Chrystoper,L.: Finite residue class rings of integers modulo n from the viewpoint of global semigroup theory, Semigroups and formal languages, World Scientific,66-83, 2007
Nagy, Benedek; Dediu, Adrian-Horia: Self-assembling tilings of Boolean tree-like circuit modeled by contextual hypergraph grammars, NSIP2007, IEEE, Bucharest, 150-153, 2007
Nagy, Benedek: Shadow-Pushdown Automata, WSEAS Trans. Comp. 5/11, 2565-2570, 2006
Szegedi,L.;Nagy, B.: Membrane computing and graphical operating systems, JUCS 12/9, 1312-1331, 2006
Nagy,Benedek: Reasoning by Intervals, Diagrams 2006, Fourth Int. Conf. on the Theory and Application of Diagrams, Stanford, CA, USA, 145-147. (LNCS-LNAI 4045), 2006
Dediu,Adrian-Horia;Klempien-Hinrichs,Renate;Kreowski,Hans-Jörg;Nagy,Benedek: Contextual Hypergraph Grammars - A New Approach to the Generation of Hypergraph Languages, DLT 2006, Santa Barbara, CA, USA,LNCS 4036, 327-338, 2006
Nagy,Benedek;Strand,Robin: Approximating Euclidean Distance Using Distances based on Neighbourhood Sequences in Non-Standard Three-Dimensional Grids, IWCIA 2006, 11th Int. Workshop on Combinatorial Image Analysis, Berlin, Germany, LNCS 4040, 89-100, 2006
Nagy,Benedek: Union-free languages and 1-cycle-free-path-automata, Publ. Math. Debrecen 68, 183-197, 2006
Nagy,Benedek: On the Notion of Parallelism in Artificial and Computational Intelligence, Proc. 7th Int. Symposium of Hungarian Researchers on Computational Intelligence, Budapest, Hungary, 533-541., 2006
xx: xx, xx, 2009
Nagy,Benedek;Vályi,Sándor: Solving a PSPACE-complete problem by a linear interval-valued computation, CiE 2006 Computability in Europe 2006: Logical Approaches to Computational Barriers, University of Wales Swansea, UK, 216-225, 2006
Nagy,Benedek: Left-most derivation and shadow-pushdown automata for context-sensitive languages, Proceedings of the 10th WSEAS Int. Conf.on Computers, Athens, Greece, 962-967, 2006
Dömösi, Pál: Symmetric key cryptographyc method and apparatus for information encryption and decryption, agyar Szabadalmi Hivatal, Nemzetközi PCT szabadalmi bejelentés, PCT/HU0700008, 2007
Dömösi, Pál; Horváth, Géza: Alternative proof of the Lyndon-Schützenberger theorem, Theoret. Comput. Sci. 366 (2006), no. 3, 194--198, 2006
Dömösi, Pál; Horváth, Géza; Ito, Masami; Shikishima-Tsuji, Kayoko: Some periodicity of words and Marcus contextual grammars, Vietnam J. Math. 34, no. 4, 381--387, 2006
Dömösi, Pál; Ito, Masami; Marcus, Solomon: Marcus contextual languages consisting of primitive words, Discrete Math. 308, no. 21, 4877--4881, 2008
Dömösi, Pál; Kudlek, Manfred: New iteration lemmata for regular languages, Fund. Inform. 64, no. 1-4, 151--157, 2005
Dömösi, Pál; Martin-Vide, Carlos; Mateescu, Alexandryu: On polyslender context-free languages, Publ. Math. Debrecen 66, no. 1-2, 1--15., 2005
Dömösi, Pál; Nehaniv, Chrystopher L.: Algebraic theory of automata networks. An introduction., SIAM Monographs on Discrete Mathematics and Applications, 11,SIAM, Philadelphia, PA, 2005
Nagy,Benedek: On the language equivalence of NE star-patterns, Inf. Proc. Let. 95, 396-400, 2005
Nagy,Benedek; Vályi,Sándor: Interval-valued computations and their connection with PSPACE, Theoret. Comput. Sci. 394/3, 208-222, 2008
Nicart, Florent; Champarnaud, Jean-Marc; Csáki, Tibor; Gaál, Tamás; Kempe, André: Labelling multi-tape automata with constrained symbol classes, Internat. J. Found. Comput. Sci. 18, no. 4, 847--858., 2007



Back »