Searching for just a few words should be enough to get started. If you need to make more complex queries, use the tips below to guide you.
Issue title: Concurrency Specification and Programming (CS&P'2002), Part 2
Article type: Research Article
Authors: Bellia, Marco | Occhiuto, Eugenia M.
Affiliations: Dipartimento di Informatica, Università di Pisa, Via Buonarroti 2, I-56127 Pisa, Italy | Dipartimento di Informatica e Scienze dell'Informazione, Università di Genova, Via Dodecaneso 35, I-16146 Genova, Italy
Abstract: MGU_{mon} and MGU_{k-rep} have a complementary role in unification in the complexity class NC. MGU_mon is the upper bound of the unification classes that fall in NC and whose inputs admit an unrestricted number of repeated variables. MGU_{k-rep} is the upper bound of the unification classes that still fall in NC but whose inputs admit an unrestricted arity on term constructors. No LogSpace reduction of the one to the other class is known. Moreover, very fast algorithms that solve the two separately are well known but no one is able to compute with both in polylog PRAM-Time. N-axioms unification extends the structure of unification inputs and brings out the notion of interleaving variable as a special repeated variable which serializes independet computations. Based on it, we define the unification class AMGU^k_{p/h} whose inputs have a fixed number of interleaving variables but admit unrestricted number of repeated variables and, at the same time, unrestricted arity for term constructors. Constructively, we prove that AMGU^k_{p/h} is in NC by introducing a new unification algorithm that works on graph contractions and solves AMGU^k_{p/h} in a polylog PRAM time of the input size. Finally, we prove that MGU_{mon}, MGU_{k-rep} , and MGU_{linear} all are LogSpace reducible to AMGU^k_{p/h}. Hence, AMGU^k_{p/h} becomes the upper bound of the unification classes that are proved to be in NC.
Keywords: N-axioms unification, PRAM algorithms, complexity classes, graph contractions, intervealing variables
Journal: Fundamenta Informaticae, vol. 55, no. 2, pp. 115-128, 2003
IOS Press, Inc.
6751 Tepper Drive
Clifton, VA 20124
USA
Tel: +1 703 830 6300
Fax: +1 703 830 2300
[email protected]
For editorial issues, like the status of your submitted paper or proposals, write to [email protected]
IOS Press
Nieuwe Hemweg 6B
1013 BG Amsterdam
The Netherlands
Tel: +31 20 688 3355
Fax: +31 20 687 0091
[email protected]
For editorial issues, permissions, book requests, submissions and proceedings, contact the Amsterdam office [email protected]
Inspirees International (China Office)
Ciyunsi Beili 207(CapitaLand), Bld 1, 7-901
100025, Beijing
China
Free service line: 400 661 8717
Fax: +86 10 8446 7947
[email protected]
For editorial issues, like the status of your submitted paper or proposals, write to [email protected]
如果您在出版方面需要帮助或有任何建, 件至: [email protected]