Hostname: page-component-745bb68f8f-5r2nc Total loading time: 0 Render date: 2025-02-02T03:41:32.307Z Has data issue: false hasContentIssue false
  • English
  • Français

Computing with relational machines

Published online by Cambridge University Press:  15 July 2015

GÉRARD HUET  and
BENOÎT RAZET
GÉRARD HUET
Affiliation:
INRIA Paris-Rocquencourt Center, France Email: [email protected]
BENOÎT RAZET
Affiliation:
Computer Science Department, Bucknell University, Lewisburg, PA 17837, USA Email: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We propose a relational computing paradigm based on Eilenberg machines, an effective version of Eilenberg's X-machines suitable for general non-deterministic computation. An Eilenberg machine generalizes a finite-state automaton, seen as its control component, with a computation component over a data domain specified as a relational algebra, its actions being interpreted as binary relations over the data domain. We show various strategies for the sequential simulation of our relational machines, using variants of the reactive engine. In a particular case of finite machines, we show that bottom-up search yields an efficient complete simulator.

Relational machines may be composed in a modular fashion, since atomic actions of one machine can be mapped to the characteristic relation of other relational machines acting as its parameters.

The control components of machines can be compiled from regular expressions. Several such translations have been proposed in the literature, which we briefly survey.

Type
Paper
Information
Mathematical Structures in Computer Science , Volume 27 , Special Issue 5: Computing with Lambda-terms. A Special Issue Dedicated to Corrado Böhm for his 90th Birthday , June 2017 , pp. 807 - 826
Copyright
Copyright © Cambridge University Press 2015 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Allauzen, C. and Mohri, M. (2006). A unified construction of the Glushkov, follow, and Antimirov automata. In: Proceedings of the 31st International Symposium on Mathematical Foundations of Computer Science (MFCS 2006). Springer Lecture Notes in Computer Science 4162 110–121.CrossRefGoogle Scholar
Antimirov, V. (1996). Partial derivatives of regular expressions and finite automaton constructions. Theoretical Computer Science 155 (2) 291–319.CrossRefGoogle Scholar
Berry, G. and Sethi, R. (1986). From regular expressions to deterministic automata. Theoretical Computer Science 48 (1) 117–126.CrossRefGoogle Scholar
Böhm, C. (1966). The CUCH as a formal and description language. In: Steel, T. B. (ed.) Formal Description Languages for Computer Programming, North Holland 179–197.Google Scholar
Brüggemann-Klein, A. (1993). Regular expressions into finite automata. Theoretical Computer Science 120 (2) 197–213.CrossRefGoogle Scholar
Brzozowski, J. A. (1964). Derivatives of regular expressions. Journal of the ACM 11 (4) 481–494.CrossRefGoogle Scholar
Champarnaud, J-M., Nicart, F. and Ziadi, D. (2006). From the ZPC structure of a regular expression to its follow automaton. International Journal of Algebra and Computation 16 (1) 17–34.CrossRefGoogle Scholar
Champarnaud, J-M. and Ziadi, D. (2001). From c-continuations to new quadratic algorithms for automaton synthesis. International Journal of Algebra and Computation 11 (6) 707–736.CrossRefGoogle Scholar
Champarnaud, J-M. and Ziadi, D. (2002). Canonical derivatives, partial derivatives and finite automaton constructions. Theoretical Computer Science 289 (1) 137–163.CrossRefGoogle Scholar
Eilenberg, S. (1974). Automata, Languages, and Machines, vol. A, Academic Press.Google Scholar
Fischer, S., Huch, F. and Wilke, T. (2010). A play on regular expressions: Functional pearl. In: Proceedings of the 15th ACM SIGPLAN International Conference on Functional Programming, ICFP'10, New York, USA 357–368.Google Scholar
Huet, G. (1980). Confluent reductions: Abstract properties and applications to term rewriting systems. Journal of the ACM 27 (4) 797–821.CrossRefGoogle Scholar
Huet, G. (2002). The Zen computational linguistics toolkit: Lexicon structures and morphology computations using a modular functional programming language. In: Tutorial, Language Engineering Conference LEC'2002.Google Scholar
Huet, G. (2005). A functional toolkit for morphological and phonological processing, application to a Sanskrit tagger. Journal of Functional Programming 15 (4) 573–614.CrossRefGoogle Scholar
Huet, G. and Razet, B. (2006). The reactive engine for modular transducers. In: Futatsugi, K., Jouannaud, J.-P. and Meseguer, J. (eds.) Algebra, Meaning and Computation, Essays Dedicated to Joseph A. Goguen. Springer-Verlag Lecture Notes in Computer Science vol. 4060 355–374.CrossRefGoogle Scholar
Ilie, L. and Yu, S. (2003). Follow automata. Information and Computation 186 (1) 140–162.CrossRefGoogle Scholar
Kozen, D. (1994a). A completeness theorem for Kleene algebras and the algebra of regular events. Information and Computation 110 (2) 366–390.CrossRefGoogle Scholar
Kozen, D. (1994b). On action algebras. In: van Eijck, J. and Visser, A. (eds.) Logic and Information Flow, MIT Press 78–88.CrossRefGoogle Scholar
Landin, P. (1966). The next 700 programming languages. CACM 9 (3) 157–166.CrossRefGoogle Scholar
Pratt, V. (1991). Action logic and pure induction. In: Proceedings of the European Workshop on Logics in AI (JELIA '90), Springer-Verlag 97–120.Google Scholar
Razet, B. (2008). Finite Eilenberg machines. In: Ibarra, O. and Ravikumar, B. (eds.) Proceedings of the CIIA 2008. Springer-Verlag Lecture Notes in Computer Science 5148 242–251.CrossRefGoogle Scholar
Razet, B. (2009). Machines d'Eilenberg Effectives, Ph.D. thesis, University Denis Diderot (Paris 7).Google Scholar
Razet, B. (2011). Simulating finite Eilenberg machines with a reactive engine. In: proceedings second workshop on mathematically structured functional programming (MSFP 2008). Electronic Notes in Theoretical Computer Science 229 (5) 119–134.CrossRefGoogle Scholar
Thompson, K. (1968). Programming techniques: Regular expression search algorithm. CACM 11 (6) 419–422.CrossRefGoogle Scholar