Selected Publications

Scheduling

• M. A. Palis, “The Granularity Metric for Fine-Grain Real-Time Scheduling”, IEEE Transactions on Computers, 15:12 (Dec. 2005), pp. 1572-1583.
• M. A. Palis, “Competitive Algorithms for Fine-Grain Real-Time Scheduling”, Proc. 25th IEEE International Real-Time Systems Symposium, Dec. 5-8, 2004, Lisbon, Portugal, pp. 129-138.
• M. A. Palis, “On the Competitiveness of Real-Time Task Scheduling with Rate of Progress Guarantees”, International Journal of Foundations of Computer Science, 14:3 (2003), pp. 359-370.
• B. Dasgupta and M. A. Palis, “Online Real-Time Preemptive Scheduling of Jobs with Deadlines on Multiple Machines”, Journal of Scheduling, 4:6 (Nov. 2001), pp. 297-312.
• J.-C. Liou and M. A. Palis, “On the Effectiveness of Compile-Time Scheduling Approaches for Distributed Memory Multiprocessors”, Special Issue on Compiler Techniques for High-Performance Computing, Journal of Information Science and Engineering, 14:1 (1998), pp. 7-26.
• J.-C. Liou and M. A. Palis, “A Comparison of General Approaches to Multiprocessor Scheduling”, Proc. 11th International Parallel Processing Symposium, Geneva, Switzerland, April 1997, pp. 152-156.
• J.-C. Liou, M. A. Palis, and D. S. L. Wei, “Performance Analysis of Task Clustering Heuristics for Scheduling Static DAGs on Multiprocessor Systems”, Journal of Parallel Algorithms and Applications, 12 (1997), pp. 185-203.
• J.-C. Liou and M. A. Palis, “CASS: An Efficient Task Management System for Distributed Memory Architectures”, Proc.1997 International Symposium on Parallel Architectures, Algorithms, and Networks (I-SPAN'97), Taipei , Taiwan , Dec. 1997, pp. 289-295.
• M. A. Palis, J.-C. Liou and D. S. L. Wei, “Task Clustering and Scheduling for Distributed Memory Parallel Architectures”, IEEE Transactions on Parallel and Distributed Systems, 7:1 (1996), pp. 46-55.

Interconnection Networks and Routing

• B. Dasgupta and M. A. Palis, "Provably Good Algorithms for Transmission Scheduling in WDM Optical Networks", Journal of Parallel and Distributed Computing, 57:3 (1999), pp. 345-357.
• M. A. Palis, S. Rajasekaran , and D. S. L. Wei, “Packet Routing and PRAM Emulation on Star Graphs and Leveled Networks”, Journal of Parallel and Distributed Computing, 20:2 (1994), pp. 145-157.
• M. A. Palis, S. Rajasekaran, and D. S. L. Wei, "Emulation of a PRAM on Leveled Networks", Proc. 1991 International Conference on Parallel Processing, St. Charles, IL, August 1991, pp. I-418 - I-421.
• M. A. Palis, S. Rajasekaran, and D. S. L. Wei, “General Routing Algorithms for Star Graphs”, Proc. 1990 International Parallel Processing Symposium, Fullerton, CA, April 1990, pp. 597-611.

Parallel Algorithm Design

• M. A. Palis and D. S. L. Wei, “Backtracking and Branch-and-Bound on Mesh-Connected Computers with Reconfigurable Buses”, Proc. 7th IASTED-ISMM International Conference on Parallel and Distributed Computing and Systems, October 1995, pp. 243-247.
• M. A. Palis and D. S. L. Wei, “Massively Parallel Parsing Algorithms for Natural Language”, Parallel Processing for Artificial Intelligence, L. N. Kanal, V. Kumar, H. Kitano, and C. B. Suttner (editors), Elsevier Science B. V., Springer-Verlag, 1994, pp. 365-407.
• O. H. Ibarra and M. A. Palis, “An Efficient All-Parses Systolic Algorithm for General Context-Free Parsing”, International Journal of Parallel Programming, 19:4 (1990), pp. 295-331.
• M. A. Palis and D. Krecker, "Parallel Kalman Filtering on the Connection Machine" Proc. 1990 Symposium on the Frontiers of Massively Parallel Computation, College Park, MD, October 1990, pp. 55-58.
• O. H. Ibarra, T. Jiang, J. H. Chang and M. A. Palis, “Systolic Algorithms for Some Scheduling and Graph Problems”, Journal of VLSI Signal Processing, 1 (1990) pp. 307-320.
• M. A. Palis, S. Shende , and D. S. L. Wei, “An Optimal Linear-Time Parallel Parser for Tree Adjoining Languages”, SIAM Journal on Computing, 19:1 (1990), pp. 1.-31.
• O. H. Ibarra and M. A. Palis, “VLSI Algorithms for Solving Recurrence Equations and Applications”, IEEE Transactions on Acoustics, Speech and Signal Processing, ASSP-35:7 (1987), pp. 1046-1064.
• O. H. Ibarra, M. A. Palis and S. Kim, “Designing Systolic Algorithms Using Sequential Machines”, Proc. 1984 IEEE Annual Symposium on Foundations of Computer Science, Singer Island , FL , 1984, pp. 46-55.

Computational Complexity

• M. A. Palis and S. Shende , “Pumping Lemmas for the Control Language Hierarchy”, Mathematical Systems Theory, 28 (1995), pp. 199-213.
• M. A. Palis and S. Shende, “Upper Bounds on Recognition of a Hierarchy of Non-Context-Free Languages”, Theoretical Computer Science, 98:2 (1992), pp. 289-319.
• J. H. Chang, O. H. Ibarra, and M. A. Palis, “Efficient Simulations of Simple Models of Parallel Computation by Space-Bounded TM's and Time Bounded Alternating TM's”, Theoretical Computer Science, 68:1 (1989), pp. 19-36.
• O. H. Ibarra and M. A. Palis, “Two-Dimensional Systolic Arrays: Characterizations and Applications”, Theoretical Computer Science, 57:1 (1988), pp. 47-86.
• J. H. Chang, O. H. Ibarra, and M. A. Palis, “Efficient Simulations of Simple Models of Parallel Computation by Space-Bounded TM's and Time-Bounded Alternating TM's”, Proc. 15th International Colloquium on Automata, Languages and Programming, Tampere, Finland, July 1988, pp. 119-132.
• J. H. Chang, O. H. Ibarra, and M. A. Palis, “Fast Parallel Language Recognition by Cellular Automata”, Theoretical Computer Science, 41 (1985), pp. 231-246.
• J. H. Chang, O. H. Ibarra, and M. A. Palis, “On Efficient Recognition of Transductions and Relations”, Theoretical Computer Science, 39 (1985), pp. 89-106.
• O. H. Ibarra, M. A. Palis, and S. Kim, “Some Results Concerning Linear Iterative (Systolic) Arrays”, Journal of Parallel and Distributed Computing, 2 (1985), pp. 182-218.