SOME TECHNICAL NOTES

What is this about? This server allows a user to specify one of 4 questions about properties of regular languages and provides an answer to the specified question. See further below how to describe properties.

Online computation vs Program generation: When a user specifies a question to solve and the required input, I-LaSer either computes the answer in real time, if the user clicks on "Submit Request", or it produces a zip file containing a self contained Python3 executable file, if the user clicks on "Generate Program". In the latter case, the executable file can produce the answer on the user's local machine.
No limits on online computations: This is the I-LaSer local web interface. All computations are done on the local computer, so there are no time or complexity limits on the calculations.

Properties. Examples of language properties are: prefix code, infix code, 1-substitution-error-detecting language [ShyThi,Shyr,JuKon]. These are examples of independences (independent properties). Roughly speaking, a language satisfies an independence if every subset of the language also satisfies that independence. Many independent properties have the following characteristic: a language L satisfies the property P if there are NO different words u,v in L such that v can result by performing a certain word operation on u--this word operation is what defines the property P. For example, prefix codes are defined by the word operation of removing any nonempty ending of the word u; and 1-substitution-detecting languages are defined by the operation that changes exactly 1 symbol in the word u. Transducers can conveniently be used to realize many such operations, and we say that each such transducer describes a property. The method of trajectories is more limited in describing independences, but the descriptions are much simpler. I-LaSer supports the following independent properties.


Implementation: Based on FAdo, a package of Python libraries, which includes modules for automata, transducers, and code properties.

Some References

[AAAMR] Andre Almeida, Marco Almeida, Jose Alves, Nelma Moreira, and Rogério Reis (2009): FAdo and Guitar: tools for automata manipulation and visualization. In S. Maneth, editor, CIAA 2009: Fourteenth International Conference on Implementation and Application of Automata, volume 5642 of Lecture Notes on Computer Science, pages 65-74, Sydney, Australia, July 2009. Springer-Verlag.
[Dass] Jürgen Dassow. Comment following the presentation in [DuKon].
[Dom] M. Domaratzki (2004): Trajectory-Based Codes. Acta Informatica, vol. 40, n. 6-7 (2004) 491-527.
[DuKon] K. Dudzinski and S. Konstantinidis (2010): Formal descriptions of code properties: decidability, complexity, implementation. International Journal of Foundations of Computer Science 23:1 (2012), 67--85. Presented at DCFS 2010.
[FAdo] FAdo: Tools for Formal Languages manipulation.
[Gol] Solomon W. Golomb (1970): A class of probability distributions on the integers. Journal of Number Theory 2 (1970) 189–192.
[JuKon] H. Jürgensen and S. Konstantinidis (1997): Codes. In G. Rozenberg, A. Salomaa (eds): Handbook of Formal Languages, vol. I, 511-607. Springer-Verlag, Berlin, 1997.
[KaKoKo] Lila Kari, Stavros Konstantinidis, Steffen Kopecki (2018). Transducer descriptions of DNA code properties and undecidability of antimorphic problems. Inform. Comput. 259(2): 237-258 (2018). Also presented in: DCFS 2015, University of Waterloo, Canada.
[KoMaMoRe] Stavros Konstantinidis, Mitja Mastnak, Nelma Moreira, Rogério Reis (2022, 2023): Approximate NFA universality and related problems motivated by information theory. Theor. Comput. Sci. (2023). Also: Approximate NFA universality motivated by information theory. LNCS 13439: DCFS 2022 142-154, Debrecen, Hungary, August 29-31, 2022.
[KoMeMoRe] Stavros Konstantinidis, Casey Meijer, Nelma Moreira, Rogério Reis (2016,2018): Symbolic Manipulation of Code Properties”. J. Autom. Lang. Comb. 23 (2018). Also: Implementation of Code Properties via Transducers. Lecture Notes in Computer Science 9705, 21st International Conference on the Implementation and Application of Automata (CIAA 2016), Seoul, Korea, Republic of (189-201). Also: Symbolic manipulation of code properties. arXiv:1504.04715v1, 2015.
[KoMoRe] Stavros Konstantinidis, Nelma Moreira, Rogério Reis (2016, 2018): Randomized generation of error control codes with automata and transducers. RAIRO Theor. Informatics Appl. 52(2-3-4): 169-184 (2018). Also: Generating Error Control Codes with Automata and Transducers. 8th Workshop on Non-Classical Models of Automata and Applications, Debrecen, Hungary, OCG Proceedings.
[Shyr] H.J. Shyr. Free monoids and languages. Hon Min Book Company, Taichung, Taiwan, 1991.
[ShyThi] H.J. Shyr and G. Thierrin. Codes and binary relations. Seminaire d'Algebre Paul Dubreil, Paris 1975--1976 (29\`eme Ann\'ee), Lecture Notes in Mathematics, 586, 1977, 180--188.